📌문제 유형: 그래프 탐색 (BFS)https://www.acmicpc.net/problem/14940   📌 풀이  전형적인 BFS 문제이다. 단, 시작점이 (0,0) 이 아니라 2 값을 갖고 있는 위치부터라는 점! 따라서 먼저 2의 값을 가진 위치를 찾아야 한다.  그 뒤에 모든 지점까지의 최단거리를 출력하라고 한다. 최단거리는 BFS로 구할 수 있다.  이때 움직일 수 있는 방향이 상하좌우이므로, dx/dy를 선언해 bfs() 안에서 for문을 통해 한 지점이 갈 수 있는 상하좌우 4곳을 살펴볼 수 있도록 한다. 이때 갈 수 있는 곳은 queue에 담는다.  여기서 포인트는, 거리 값을 visited에 누적합으로 표현한다는 점이다.  1. 모든 지점에 대해 visited[i][j] = -1로 초..

📌 문제 유형: DPhttps://www.acmicpc.net/problem/1463   📌 풀이 문제를 읽으면서 딱 눈에 들어오는 것은, 시간 제한이 0.15초 밖에 안된다는 점이다. 그리고 N이 1~10^6이라면, 완전탐색으로는 시간 초과가 날 것이라는 걸 느끼게 된다.  이 상태에서 문제를 좀 더 살펴보자.  3으로 나누어 떨어질 때, 2로 나누어 떨어질 때, 둘 다 아닐때 이렇게 3가지 경우에 대해 연산을 제한해 두고 있다. 이 3개의 연산을 적절히 사용해 연산 횟수를 MIN로 만드려고 한다. 드는 생각들! 1. 3의 배수일 때 (2의 배수는 아님)2. 2의 배수일 때 (3의 배수는 아님) 3. 둘 다 아닐 때 - 1을 뺀다. 4. 6의 배수일 때 ==> 이 경우가 추가되어 고려될 수 있다. ..

📌 문제유형: DP https://www.acmicpc.net/problem/1003   📌 풀이  이 문제에서 포인트는 !!! 시간 제한이 0.25초 밖에 안된다는 점이다. 따라서 재귀함수로 작성하게 되면, 1시간초과에 걸리게 된다.  그 해결 방법은 동적 계획법(DP)에 있다.  즉, 메모제이션을 활용해야 한다. 메모제이션이란 앞서 계산했던 값을 저장해두어, 추후 다시 필요하게 될 때 다시 계산하는 것이 아니라 이미 계산된 값을 불러오는 것이다.  위의 문제는, n에 대한 피보나치 수열이 계산될 때 0과 1이 몇 번씩 필요로 되는가에 있다.  DP를 풀 때 1. 하나의 예제를 가지고 직접 손으로 적어보면서 실마리를 찾는다. 2. 규칙성을 찾아본다. 3. 이를 점화식으로 세워본다. (앞에서 #를 선..

https://www.acmicpc.net/problem/17219   📌 풀이 한 줄씩 공백으로 split()해서 받고, 딕셔너리 타입으로 저장해 둔다. N+2줄부터는 key 값으로 value 찾기니까 쉽다!  N, M = map(int, input().split())pwd = {}for _ in range(N): site, pw = map(str, input().split()) pwd[site] = pwfor _ in range(M): toFind = input() print(pwd[toFind])

https://www.acmicpc.net/problem/11047  풀이  동전 구하기는 그리디 알고리즘에서 유명한 문제이다.  해당 문제에서 내림차순으로 정렬해 나누기를 반복했을 때 정답이 될 수 있는 이유는 arr 값들끼리 배수의 관계에 있기 때문이다.  만약 arr = [100, 400, 500, 100] 인데, 800원을 만들 수 있는 동전의 최소 개수는 아래의 코드 기반으로 하면 4개가 된다. (500원 1개, 100원 3개) 하지만 이론 상으로는 400원 2개로 끝이 난다.  따라서, 그리디 문제를 풀 때는 1. 완전탐색을 고민해보고 2. 반례가 없는지 꼭 확인해봐야 한다.  N, K = map(int, input().split())arr = []for _ in range(N): arr..

https://www.acmicpc.net/problem/11399    풀이 앞쪽의 인출 시간이 짧아야 대기시간도 덩달아 짧아진다. 즉 arr을 오름차순으로 정렬하고, 대기시간은 앞선 인출시간의 누적 합이고 시간의 총합은 i번째 사람의 대기시간 + 인출시간이므로 누적 합을 이용하면 된다.  (이때 n번 사람에 몇 분의 인출이 필요한지 딕셔너리 d로 정의를 해두었는데, 복기해보니 큰 쓸모는 없다.)  N = int(input())d = {}arr = list(map(int, input().split()))for i in range(N): d[i+1] = arr[i]d_sorted = dict(sorted(d.items(), key=lambda x:x[1]))total = 0wait = 0for t ..