All
문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다. 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다..
문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다. 출력 친구 관..
문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. 예제 입력 1 3 1 2 3 1 3 2예제 출력 1 2 1 3 나의 풀이 중위 순회는 (왼쪽 트리) - 부모 노드 - (오른쪽 트리) 로 나눌 수 있고, 후위 순회는 (왼쪽 트리) - (오른쪽 트리) - 부모 노드 로 나눌 수 있다. 따라서 후위 순회에서 마지막에 나오는 부모 노드의 정보를 가지고 중위 순회에서 왼쪽..
문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자..
문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다..
문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7예제 출력 1 4 6 1 3 1 4예제 입력 2 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12예제 출력 2 1 1 2 3 3 4 4 5 5 6 6 나의 풀이 연결에 대한 정보를 가지고 트리를 양방향 그래프로 생각하고 인접리스트를 만들어주었다...
어느 순간부터 vs code 내의 터미널과 에디터에서 입력 시 멈추는 것과 같은 렉이 발생을 하여 해결법을 찾아보았다. Renderer Type 변경 Code - Preferences - Setting 또는 cmd + , 으로 설정화면으로 이동한다. Renderer 를 검색한다. 아마 auto 가 기본값으로 설정이 되어있을 것이다. 이 값을 dom으로 변경하고 렉이 걸리는지 확인해본다. canvas로 렌더링을 하는 과정에서 그래픽카드에 부하를 주는 경우가 발생한다고 한다.
나의 풀이 해당 문제는 participant의 최대가 100,000으로 O(n^2)이상의 시간 복잡도가 나오면 안되는 문제이다. 필자는 딕셔너리를 이용하여 풀이를 하였다. 우선, participant의 모든 선수들을 반복하며 {이름: 개수} 형태로 저장하고 각 선수의 숫자를 세어준다. 이후 completion을 반복하며 해당하는 이름의 숫자를 1씩 감소를 시킨다. 그리고 마지막으로 딕셔너리를 반복하며 value가 0이 아니라면 return을 해주면 문제를 해결할 수 있다. 허나 다른 사람의 풀이를 보니 유용한 모듈이 있어 글을 쓰게 되었다. collections에 보면 Counter라는 오브젝트가 있다. 이 오브젝트는 리스트에 있는 요소들의 개수를 자동으로 딕셔너리 형태로 갖는다. 예를 들면, ['..
해당 문제는 2019 카카오 개발자 겨울 인턴십에서 1번으로 나왔던 문제이다. 나의 풀이 필자는 board가 2차원 배열로 주어진 것을 collum별로 스택에 나누어 담아 놓고 크레인이 움직일 때 2차원 배열을 반복하며 찾는 과정을 없애는 방향으로 풀이를 진행하였다. 따라서 초기에 N개 만큼의 deque()를 담는 list를 만들어두고 board의 모든 행을 거꾸로 탐색하여 해당 deque()에 0이 아니라면 append를 해놓았다. 또한, bucket이라는 deque()도 생성해두었다. 이후, 주어지는 moves를 반복하며 해당하는 deque()가 비어있지 않다면 pop을 하였다. 그리고나서 bucket이 비어있지 않다면 가장 위에 있는 인형과 같은지를 비교하고 같다면 bucket에서 pop을 진행하고..
