본문 바로가기

전체 글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.
1111. IQ Test (Python) 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 풀이 방정식을 통하여 a와 b를 구하고 각 숫자에 * a + b를 했을 때 다음 숫자가 나오는지를 확인하면 된다. 1, 4, 13, 40 예를 들어 위의 예제에서 1a + b = 4와 4a + b =13의 방정식을 사용하여 a와 b를 구한다. 두 식을 빼면 3a = 9가 나오고 여기에서 a=3이 됨을 알 수 있다. 이를 통해 b는 1이 된다. 이제 앞에서 부터 차례대로 * 3 + 1을 하여 다음 숫자가 나오는지 확인한다. 문제를 풀 때 몇 가지 예외 처리를 해줘야 한다. N이 1인 경우 -> 뒤에 아무 숫자나 올 수 있으므로 '.. 2022. 5. 19.
2981. 검문 (Python) 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 풀이 입력 받은 각 수 들의 차이에 대하여 최대 공약수를 구한다. 위의 예제를 보자. 입력으로 받은 [5, 17, 23, 14, 83]에 대하여 자신의 앞에 있는 숫자와의 차이를 구하면 [12, 6, 9, 69]가 나온다. 이제 이 숫자들에 대하여 차례대로 최대 공약수를 구한다. 12와 6의 최대 공약수를 구하면 6이 나온다. 다시 이 6과 9의 최대 공약수를 구하면 3이 나온다. 다시 3과 69에 대하여 최대 공약수를 구하면 3이 나온다. 최종적으로 입력으로 받은 숫자들에 대.. 2022. 5. 19.
9370. 미확인 도착지 (Python) 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라를 사용하는 문제인데 문제에서 주어진 g와 h 교차로 사이에 있는 도로를 지나가는 길을 포함하는 최소 경로가 있는지에 대해서 추가적으로 판단하는 작업이 필요하다. 보통 우선순위 큐에 넣을 때 (출발점에서의 거리, 다음 출발 노드)와 같은 형태로 넣어주는 데 이렇게 해서는 특정 길을 지났는지를 판단할 수 없다. 추가적으로 g와 h 도로를 지나간 경로인지를 판단하기 위한 플래그 값이 필요하다. 위의 그림을 보면 1번에서 4번으로 가는 최소 경로 .. 2022. 5. 17.

티스토리툴바