https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 아이디어 1. 시간 초과 처음에는 x, y값이 나올 때까지 1씩 더해가며 count를 했다. 숫자가 반복되면 -1을 출력하게 했다. 생각이 너무 쉬웠는지 시간 초과가 발생했다. 다른 방법을 사용하기로 결정 코드 설명 def find_K(M, N, x, y): K = x while K

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어 1. 플로이드 와샬 예전에 가중치가 있는 플로이드 와샬을 푼 경험이 있어서 이번에는 간단하게 해결했다. 기존 알고리즘에서 약간만 변형하면 됨 코드 설명 for k in range(N): for i in range(N): for j in range(N): if adj_matrix[i][k] == 1 and adj_matrix[k][j] == 1: adj_matrix[i][j] = 1 k는 거쳐가는 노드, i는 시작 노드, j는 도착..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아이디어 1. 최소 경로 bfs 지도와 최소 경로가 필요하다는 것을 보고 bfs를 사용하기로 결정. 여유로운 시간과 n크기를 보고 bfs를 여러 번 해도 괜찮겠다고 생각했다. 그래서 가장 가까운 먹이를 찾을 때마다 bfs를 사용하기로 했다. 2. 가장 가까운 물고기 a. 물고기까지 이동이 가능한지 check b. 그 물고기를 먹을 수 있는지 c. 가능한 물고기들을 리스트에 담아두고 lamb..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 아이디어 1. 그리디와 dp 처음에는 n을 넘지 않는 최대 제곱수를 n에 빼가면 되지 않을까 생각했다. 이렇게 하면 예외가 생긴다. 예를 들어 12는 그리디로 생각하면 9, 1, 1, 1이지만 정답은 4,4,4로 3개가 최소 개수다. 다시 문제 내용을 보고 dp로 풀기로 결정 DP[n] = (n이라는 수를 만드는데 필요한 수의 개수) 코드 설명 k = 1 whi..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 너무 어렵다에요 아이디어 1. DP 문제를 보고 dp문제인 것도 알고 'DP [k] = 합이 k가 되는 경우의 수'라는 것도 알았다. 근데 점화식 아이디어가 떠오르지 않아 검색의 힘을 빌렸다. 일주일 뒤에 또 풀어봤는데 또 까먹었다. 이해를 못 했다는 뜻이다. 이번 기회에 제대로 이해하고 넘어가기로 함. 코드 설명 DP = [0] * (k + 1) DP[0] = 1 for c in coins:..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 메모리 제한(4MB)이 있는 dp문제 아이디어 1. 메모리 제한 매우 적은 메모리 제한을 보고 dp를 사용하기로 결정 단순히 문제에 주어진 N값만 보고 배열을 만들기엔 4MB로는 턱없이 부족하다. 따라서 임시로 저장해주는 변수를 따로 만들어 사용 코드 설명 max_arr = [int(x) for x in sys.stdin.readline().rstrip().split()] min_arr = copy.copy(m..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 아이디어 1. bfs 주사위를 선택(1 ~ 6)할 수 있는 점과 최단 횟수를 구해한다는 점에 bfs를 선택 뱀과 사다리만 잘 체크해주면 되는 문제. 코드 설명 deq = deque() deq.append([1, 0]) visited[1] = True while deq: po, count = deq.popleft() if po == 100: print(..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 오랜만에 부분점수가 있는 문제 아이디어 1. 가장 먼저 떠오른 건 슬라이싱 단순하게 생각해서 그냥 Pn 크기만큼 잘라서 탐색했다. 아이디어가 너무 쉬운만큼 부분점수 50점만 줬다. 2. 시간 초과를 피하려면 이번에 알게 됐는데, 파이썬에서 arr [a:b]의 시간 복잡도는 O(b - a)라고 한다. 슬라이스를 최대한 덜 쓰고 반복..