Algorithm/Baekjoon117 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. 이전 1 ··· 4 5 6 7 8 9 10 ··· 20 다음
