s0n9h2

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 사용 언어 Python3 풀이 과정 조건이 진짜 많아서 풀기 까다로웠던 문제... 조건을 정리해보니 다음과 같았다. # 처음 아기상어 크기는 2 # 1초에 상하좌우로 한 칸씩 이동 # 자기보다 큰 물고기가 있는 칸은 지나갈 수 없음 # 자기보다 작은 크기의 물고기만 먹을 수 있음 # 자기랑 같은 크기면 지나갈수만 있음 # 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가 ..

문제 https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 사용 언어 Python3 풀이 과정 '구현 + 다이나믹 프로그래밍'을 주제로 스터디 팀원들이 골랐던 문제인데 DP라고 생각해서 더 어려웠던 것 같다. 처음에 내가 DP를 이용해 푼 코드는 다음과 같다. from sys import stdin input = stdin.readline N = int(input()) sequence = list(map(int, input().split())) maxl..

문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 사용 언어 Python3 풀이 과정 부모 자식간의 관계 그래프를 가지고 촌수를 계산하는 문제였다. 나는 처음에 부모: [자식 리스트]와 같은 일방향 그래프를 만들어놓고 자식들 숫자 두 개만 주어지면 어떻게 찾아가지 하는 고민을 했는데, 따라서 자식: [부모 리스트] 그래프도 만들어 양방향 그래프를 만들어주어야 문제를 풀 수 있었다. 그래프를 만들 때 처음에는 이중 리스트를..

문제 https://www.acmicpc.net/problem/6523 6523번: 요세푸스 한 번 더! 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 세 숫자 N, a, b가 공백으로 구분되어져 있다. (2 ≤ N ≤ 109, 0 ≤ a, b < N) 또, 첫 사람이 술을 마시 www.acmicpc.net 사용 언어 Python3 풀이 과정 👏👏👏👏👏 일단 박수 👏👏👏👏👏 내가 골드 I 문제를 풀다니!! (사실 난이도 기여하신 분들이 많이 없어서 진짜 그 정도같진 않지만...) 그래도 기분이 좋자나~!~!! 사실 이 문제는 요세푸스 문제를 풀었을 때 바로 도전했던 문제인데.. 연산량이 적은 테스트케이스는 출력값이 잘 나왔지만 나머지 두 개는 계속 시간초..

문제 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 사용 언어 Python3 풀이 과정 처음에는 어제 동전 1 푸는 법을 공부했다고 그래도 거의 비슷하게 아래와 같이 풀었다. # 원하는 만큼 고객을 늘리기 위한 투자 비용의 최솟값 from sys import stdin input = stdin.readline goal, cities = map(int, input().split()) dp = [0] * (goal + 1) costDict =..

문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 사용 언어 Python3 풀이 과정 NC에서 본 코딩 테스트 문제에 동전 문제가 생각나는 동적 계획법 문제가 있었어서 풀어봤다. 그런데 내가 기억한 문제랑은 다른 유형이었지만 암튼 이것도 점화식 세우기(문제 감 잡기) 너무 어려웠음... 문제의 포인트는 다음과 같았다. 1. 시간 제한이 0.5초, 메모리 제한도 4MB 2. 사용한 동전의 구성이 같으면 순서는 무시한다. 1번 조건 때문에 메모이..

문제 https://www.acmicpc.net/problem/13910 13910번: 개업 해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 www.acmicpc.net 사용 언어 Python3 풀이 과정 일단 푼 시간도 진짜 오래 걸렸는데 푸는 과정에서 문제를 잘못 봐서 두 번이나 함정에 빠졌다... 1. 해빈이는 양손잡이이기 때문에 한 번에 두 개의 웍만 사용할 수 있다. 2. 정확한 짜장면의 수만큼 요리할 수 있는 경우가 없을 경우 -1 출력 나는 1번을 안 보고 아래와 같이 모든 조합의 합을 구했고 당연히 이중 for문으로 시간이 오래 걸릴 수밖에 없었다. 내가..

문제 https://www.acmicpc.net/problem/15828 15828번: Router 인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 www.acmicpc.net 사용 언어 Python3 풀이 과정 실버 IV인 만큼 문제를 읽고 한 줄씩 그대로 구현했더니 어렵진 않은 문제였다. 그런데 다른 스터디원들 이야기를 들어보니 50점을 맞은 분들이 꽤 있었고 시간초과가 이유일 것 같다는 추측이어서 그 분들의 코드와 비교해보면 크게 아래 두 가지의 차이점이 있었다. 1. input() 대신 sys.stdin.readline() 사용 2. list, queue 자료..

문제 https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 사용 언어 Python3 풀이 과정 처음에는 막 항상 끝이 PAP로 끝나야 하니까 그런 조건들을 생각하다가... 절대 모든 조건을 고려할수도 없고 그렇게 푸는 문제가 아닌 것 같아서 더 생각해봤다. 그런데 문제 조건에서 다음과 같이 명시했으므로 1. P는 PPAP 문자열 2. PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열 반대로 PPAP를 다시 P로 바꿔도 PPAP 문자열이 된다는 사실을 깨달아야 했다. 저 로직을 깨..

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 사용 언어 Python3 풀이 과정 비슷한 로직으로 첫 번째 시도는 틀렸지만 두 번째에 뜬 맞았습니다! DFS랑 BFS 개념을 여러번 공부중인데 그래도 문제에 적용하는게 왜 어려운지 나는.... 공부 방법을 바꿔서 더 많은 문제의 예시를 좀 따라 쓰고 안 보고 다시 쳐보는 연습을 해야겠다. 제출 답안 # 입력 변수 받기 N, M, V = map(int, ..

문제 https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 사용 언어 Python3 풀이 과정 또다른 동적 프로그램 문제였다. 처음 아이디어는 금방 생각 했는데 코드로 구현하는데는 좀 오래걸렸던 것 같다. 특히 경우의 수를 제대로 나누는 것이 어려웠는데, 일단 0으로 시작하는 경우만 걸러주고 이후에 해독이 안되는 코드는 자동으로 걸러지도록 경우를 나누었다. if code[0] == 0: # 0으로 시작하면 잘못된 코드 else: # 이후 한 자리, 아니면 두 자리로 ..

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 사용 언어 Python3 풀이 과정 또다른 동적계획법 문제! 처음에는 아래 제출 방식대로 제출했다가 아래와 같이 수정해봤는데 append를 사용하는게 조금은 더 시간이 걸리는 것을 확인했다. from sys import stdin input = stdin.readline n = int(input()) sequence = list(map(int, input().split())) maxSum = [] fi..

문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 사용 언어 Python3 풀이 과정 1로만들기 첫 번째 문제와 비슷하게 풀고 getpath 함수를 하나 추가해주었다. 사실 원래 풀던 방식으로는 path를 기록하는게 너무 어렵고 감이 안와서 다른 분의 코드를 참고해서 풀었다. def getpath(x): global path current = x while current != 0: print(current, end=' ') current = path[current] 나한텐 살짝 어렵긴 했지만 ㅠㅠ 공부했다 치고 맞았습니다!! 음 메모리랑 시간은 ..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사용 언어 Python3 풀이 과정 처음엔 아래와 같이 또 재귀로 모든 경우의 수를 나눠 연산하려 했는데 숫자가 커지니 recursion error를 냈다.. 재귀 처음엔 어렵더니 계속 쓰게 되는데 DFS가 아니라면 안쓰도록 노력해봐야겠다. if x in count: return count[x] else: if x % 3 == 0 and x % 2 != 0: # 3의 배수만일 때 count[x] = 1 + min(makeOne(x//3), makeOne(x-1)) elif x % 2 == 0 and x %..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 사용 언어 Python3 풀이 과정 동적 계획법 문제는 점화식을 구하는 것이 중요하다는 걸 다시 한 번 깨달은 문제. 그리고 그 점화식을 구할 때에는 대개 마지막 경우의 수가 어떻게 되는지 생각해 보는게 쉽게 접근하는 방법인 것 같다. 1, 2, 3 숫자만 써서 합이 정수 n이 되는 조합을 만든다고 할 때, 마지막 더하기의 경우는 x + 1 = n x + 2 = n x + 3 = n 위 세 가지 경우밖에 없기 때문에 경우의 수는 n - 1을 구하는 경우, n - 2를 구하는 경우, n - ..

문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 사용 언어 Python3 풀이 과정 요세푸스 순열의 규칙을 생각해서 나름 쉽게 풀었다. 그런데 출력 형식을 간단하게 구현하는데 고민을 많이 했다. 처음에는 다음과 같이 구현했는데 76ms가 나왔고, 후에 다른 사람들의 답안을 참고하여 출력 형식만 바꿔줬더니 72ms가 되었다. from sys import stdin N, K = map(int, stdin.readline().split()) table = [x for x in range(1, N + 1)] Josephus = [] id..

문제 https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 사용 언어 Python3 풀이 과정 이진트리의 전위 순회-중위 순회-후위 순회는 학부시절부터 공부했던 것이지만 이걸 코드로 구현한다 하더라도 각각을 구현했지 두 가지 트리 정보로 나머지 순회를 구하는 것은 처음이라 어떻게 풀어야 할 지 막막했다. 그래도 전위 + 중위 > 후위나 중위 + 후위 > 전위는 쉬운 편이고 전위 + 후위 > 중위가 생각할 점이 훨씬 많은 것 같아 나중에 따..