https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 아이디어 1. 보석을 가방에 어떻게 담을 건가. 단순히 이중 반복문으로 비교하면 시간 초과가 난다. 다시 문제를 읽고 문제에 있는 힌트를 보고 감을 잡았다. 먼저 보석 리스트와 가방 리스트를 오름차순으로 정렬하고 각 가방을 기준으로 보석이 가방에 넣을 수 있는지 확인한다. 가방에 넣을 수 있는 보석 중 가치가 가장 큰 걸 넣어주면 된다...
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 시리즈 마지막 숨바꼭질 1 먼저 풀어보는 게 좋다. 아이디어 1. bfs 큐에 x +1, x - 1, x * 2를 조건에 맞으면 추가해준다. 큐에 위치와 시간 그리고 지나온 길도 같이 넣어준다. 도착하면 도착 시간과 경로를 리턴 후 출력. 전체 코드 from collections import deque N, K = map(int,input().split(..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 1. bfs 이미 숨바꼭질 1과 3을 풀어서 대충 알고 있다. x - 1, x + 1, x * 2 큐에 넣어주면서 탐색하면 됨. 경우의 수를 어떻게 구할지 생각만 하면 된다. 2. 경우의 수 쭉 탐색을 하다가 맨 처음 동생한테 도착한 시간을 저장하고 이후 동생한테 도착했을 때 저장해둔 시간과 같다면 경우의 수를 +1 해준다. 전체 코드 from col..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 아이디어 1. 반복문 문제 느낌이 진실을 아는 사람이 좀비같이 감염시키는 것이라 생각 그래서 진실을 아는 사람과 같이 있는 사람들을 진실을 아는 사람으로 바꿨다. 근데 이러면 진실을 아는 사람들이 바뀌어서 전체 파티를 또 탐색해야 하고 이를 계속 반복해야 해서 실패했다. 2. 그래프 그러다가 동시에 한 번에 해야 된다는 것을 깨닫고 그래프를 사용하기로 결정 각 파티마다 있는 사람들을 두 명씩 양방향으로 이어..
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 아이디어 1. 조합 단순하게 리스트에 있는 값 중에서 두 개를 뽑아 계산하는 코드를 짰다. 시간 초과 발생 생각해보니까 조합이면 100000C2인데 1초로는 택도 없다. 2. 문제에 오름차순이 힌트 미리 정렬이 되어있으니까 이걸 이용하라는 의미로 해석 이분 탐색과 비슷하게 좌우에서 하나씩 좁혀가며 최솟값(0에 가까운 값)을 찾기로 결정. 코드 설명 while l < r: cur_value =..
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..