분류 전체보기282 2263. 트리의 순회 (Python) https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 입력으로 주어진 인오더와 포스트오더를 사용하여 재귀를 통해 프리오더를 구할 수 있다. 포스트오더는 리스트의 마지막에 있는 숫자가 현재 트리의 부모 노드에 해당한다. 이를 통해서 현재 트리의 부모 노드 숫자를 알 수 있다. 이제 이 숫자를 인오더 리스트의 어느 위치에 있는지를 찾는다. 인오더의 위치를 기준으로 왼쪽에 있는 숫자 리스트가 현재 트리의 왼쪽 서브 트리에 해당하고, 오른쪽에 있는 숫자 리스트가 현재 트리의 오.. 2022. 5. 27. 5639. 이진 검색 트리 (Python) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 트리 클래스를 사용하여 실제로 트리를 구성하여 출력하는 방법과 입력으로 주어진 전위 순회 결과에서 재귀를 사용하여 후위 순회 결과를 얻는 방법으로 문제를 해결할 수 있다. 전자는 Tree 클래스를 만들고 루트 노드의 값으로 트리 객체를 하나 생성한다. 그 후 Tree 클래스의 insert 메서드를 사용하여 트리에 값을 넣어준다. insert 메서드는 부모 노드의 값과 새로 삽입되는 값을 비교하여 작을 경우 왼쪽 트리에 값을 삽입하고 클 경우 오.. 2022. 5. 26. 1865. 웜홀 (Python) 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 벨만 포드 알고리즘을 사용하여 음의 사이클이 존재하는지를 확인하면 된다. 벨만 포드 알고리즘은 링크참고하자. 문제에는 시작 정점이 따로 주어져 있지 않다. 그렇기 때문에 웜홀의 정보를 입력받을 때 도착 지점에 대한 리스트를 Set을 활용하여 저장하였다. 웜홀의 정보를 입력받을 때 S에서 E로 웜홀을 통해서 가면 시간이 줄어들기 때문에 도착 지점인 E가 음의 사이클을 가질 수 있는 후보 지점이라고 생각했다. 이렇게 후보 지점들을 시작 지점으로 설.. 2022. 5. 24. 2011. 암호코드 (Python) 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 풀이 2차원 dp를 사용하여 문제를 해결했다. dp[n][m]의 의미는 다음과 같다. dp[n][m] : 입력으로 주어진 숫자의 N번째 자리의 숫자를 M 자릿수(M은 1 또는 2) 사용했을 때의 경우의 수 글로 풀어 쓰자니 조금 이상한데.. 예로 들면 문제의 예제처럼 25114가 입력으로 주어지고 현재 N이 4라고 생각해보자. 입력으로 주어진 숫자의 4번째 자리의 수는 1이다. 이제 이 4번째 숫자를 한 자릿수로(M = 1) 생각하면 1에 해당하는 A 문자로 바꿀수 있고 이는 앞.. 2022. 5. 22. 2831. 댄스 파티 (Python) 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 풀이 남성 리스트에서 음수 값을 가진 사람과 여성 리스트에서 양수 값을 가진 사람끼리 비교하고 남성 리스트에서 양수 값을 가진 사람과 여성 리스트에서 음수 값을 가진 사람끼리 비교한다. 두 개의 포인터를 사용하여 하나는 음수 값을 가진 리스트의 맨 앞쪽을 가리키게 하고 하나는 양수 값을 가진 리스트의 맨 뒤쪽을 가리키게 한다(두 리스트는 정렬된 상태여야 한다). 그 후 각 포인터가 가리키는 값을 더한다. 이때 나오는 값에 따라서 다음의 작업을 한다. 합이 음.. 2022. 5. 21. 2565. 전깃줄 (Python) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 최장 증가 부분 수열을 활용하여 해결할 수 있다. 최장 증가 부분 수열에 관한 설명은 여기를 참고하자. A 전봇대의 1번부터 N번까지 연결되어 있는 B의 전깃줄 번호를 한 배열 안에 담아둔다. 그 배열 안에서 최장 증가 부분 수열의 길이를 구하고 이를 N에서 빼주면 없애야 하는 전깃줄의 최소 개수를 구할 수 있다. 코드 import heapq from bisect import bisect_left if __name__ == '__main__': N = int(in.. 2022. 5. 21. 이전 1 ··· 4 5 6 7 8 9 10 ··· 47 다음
