https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 아이디어 1. 가중치가 있는 그래프 다익스트라 아니면 플로이드 두 개를 생각했다. 두정점 v1, v2를 지나는 최단경로는 각각의 최단경로들을 더한 것과 같으므로 다익스트라를 여러 번 사용하면 된다. '1 -> N' = '1 -> v1' + 'v1 -> v2' + 'v2 ->N' 같이 계산해서 두 정점을 지나는 최단경로를 구한다. 루트는 1 -> v1 -..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 아이디어 1. 구현이 먼저 문제를 보고 N최대가 20이고 이동도 5번 하므로 문제가 말한 그대로 구현하면 되겠다고 생각. 상, 하, 좌, 우 이동 중에 '좌'로 이동하는 것부터 구현하면 나머지도 쉽게 만들 수 있다. 만들수록 변수나 if문이 많아져 다시 밀고 처음부터 작성했다. 너무 많은 변수는 필요 없다. 이건 다른 구현 문제도 마찬가지라고 생각. '이동시킬 블록'과..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 아이디어 1. 백트래킹 이미 N과 M 문제를 풀어봐서 바로 떠올랐다. 깊이가 M이 될 때마다 주어진 숫자들을 탐색하면 된다. 이 문제에서는 순열, 중복되지 않은 숫자들을 나열해야 하므로 이미 추가된 숫자가 있으면 continue로 넘겨준다. 전체 코드 N, M = map(int, input().split()) numbers = [int(x) for x in input().split()] ..

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 =..