결국 빛나리라

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net > 문제 풀이 아이디어 DP로 풀 수 있는 문제이다. 해당 문제에서 dp에는 최대 병사 인원 수가 들어간다. 푸는 논리는 다음과 같다. - 우선 dp를 병사 수만큼 1로 초기화한다. - 1 번째 병사는 0 번째 병사보다 전투력이 작으므로 연산을 수행한다. (0 번째 병사의 인원수 +1) 과 (1번째 병사의 인원 수) 중 큰 값을 dp[1]에 넣어준다. - 2 번째 병사는 0 번째 병사보..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net > 문제 풀이 아이디어 bfs와 최단거리 유형으로 풀 수 있다. - 시작점인 1을 큐(q)에 넣고 최단 거리정보를 나타낸 dist 리스트의 시작점엔 0을 넣는다. - 1에서 갈 수 있는 노드는 2와 3이므로 이들을 q에 차례로 넣는다. 동시에 최단거리는 (0+1)로 dist의 각 인덱스에 추가해준다. - 2에서 갈 수 있는 ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net > 다이나믹 프로그래밍 아래 그림과 같은 규칙을 생각하면 풀 수 있었던 문제이다. 규칙을 코드로 작성하면 다음과 같다. + 계단의 개수가 하나인 경우에 if절을 넣어주지 않으면 dp[2]를 구하는 과정에서 인덱스 에러가 나기 때문에 if문을 통해 하나인 경우를 고려해주어야 한다.

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net > 정렬 sort 메소드를 사용하고 파라미터인 key를 이용해 첫번째 정렬기준을 튜플에서 0번째 요소로, 두번째 정렬기준을 1번째 요소로 잡아주면 풀 수 있다. 또한 입력값을 받을 때 sys.stdin.readline을 사용해야 시간초과가 나오지 않는다.

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net > 그리디 알고리즘 각 사람이 기다리는 시간을 더할 때 작은 값부터 더하면 최종 합은 최솟값이 되므로 입력받은 시간 리스트를 정렬한 후 반복문을 사용해 합을 구하면 된다. time은 사람들이 각각 기다리는 시간이고 이를 최종 합인 result에 더해준다.

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net > 큐 각 큐의 원소와 원소에 해당하는 순서를 함께 튜플로 묶어 큐에 추가함으로써 찾고자 하는 원소가 어디에 위치하는지 알 수 있도록 하는 것이 중요한 키포인트였다. 그리고 큐의 첫번째에 나와있는 튜플이 큐의 최댓값과 같다면 해당 튜플을 큐에서 빼주고 순서를 하나씩 증가시키면서 반복문을 진행하다가 찾고자 하는 원소가 나오면 반복문을 중단한다. 해당 원소가 몇번째에 큐에서 나오게됐는지를 알려주는 순서를..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net > 동적계획법 문제의 원리만 깨우치면 코드 작성은 그렇게 복잡하지 않은 문제였다. 4개의 타일로 만들 수 있는 모든 가짓수를 세려본다고 할 때 우리는 다음 그림과 같이 바로 이전 3개 타일의 경우의 수에 1을 붙이는 경우와 그 이전 2개 타일의 경우의 수에 00을 붙이는 경우를 생각해볼 수 있다. 단 숫자를 추가할 땐 뒤쪽에만 숫자를 붙여야 중복되는 수가 나오지 않는다는 것을 기억하자. 결과적으로 4개..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net > 큐 활용 다음 그림은 문제에 나와있는 예시를 대상으로 생각한 아이디어를 그려본 것이다. 1번에서 k-1번, 즉 시작 번호에서 두 번 이동해야하는데 이동하면서 거쳐가는 숫자들은 모두 뒤로 빼준다(

https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net > 정렬 정렬 기본 개념을 묻는 문제로 sort함수와 join을 사용해 해결가능하다.

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net > dfs 활용 연결되어있는 격자들에 방문처리하고 개수를 카운트한다는 점에서 dfs 알고리즘을 사용하였다. 먼저 격자 정보들을 2차원 배열형태로 입력한다. 아래 코드로 값을 입력받으면 숫자들이 모두 문자형태로 들어간다는 것을 기억하자. 그리고 격자에 방문했는지 여부를 보여주는 visited 배열과 격자의 상하좌우로 움직이기 위한 dx, dy 배열도 선언해준다. 행, 열 정보를 파라미터로 넣은 dfs..