알고리즘 문제풀이 (58) 썸네일형 리스트형 [ 백준 1495 ] 기타리스트 (C++) https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net dp 문제다. 처음 문제를 읽고 떠로으는 생각은 bfs였지만 시간복잡도가 대충 O(2^n)이 나와서 시간 초과를 받게 될게 뻔했다. 남은건 dp 뿐이었다. 근데 나는 dp가 너무 어렵다... 아이디어가 생각이 나지 않아 아이디어만 참고했다. 그래서 50점짜리 풀이라고 해야하나.... 이중 for문으로 풀 수 있는 문제다. 우선 이 문제의 아이디어는 다음과 같다.. [ 백준 1890 ] 점프 (C++) https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 두 개의 배열을 사용해서 풀었다. 1. int m[100][100] 이동배열 문제의 입력값을 저장한다. map[1][2]는 1행, 2열에서 오른쪽, 아래로 이동 가능한 칸 수다. 2. long visit[100][100] 도달 가능 경로 배열 visit[3][4]의 값은 3행 4열로 도달할 수 있는 경우의 수를 뜻한다. 만약에 값이 0이면 아직 한 번도 방문하지 않았다는 뜻이다. 그냥 .. [ 백준 15486 ] 퇴사 2 (C++) https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 다이나믹 프로그래밍 문제다. Dp는 먼저 점화식을 세운 뒤에 코드를 짜는게 편하다. 개인적으로 Dp 문제를 풀 때 Dp 값이 무엇을 뜻하는지 아는 게 정말 중요하다고 생각한다. 이 문제의 경우 dp[i]는 무엇을 뜻할까? dp[i] 란 i일동안 누적한 최대 이익을 말한다. 예를 들어 dp[13] = 64 이라면 13일까지의 최대 이익은 64라는 뜻이다. 초기 dp 값.. [ 백준 17086 ] 아기상어 2 (C++) https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net bfs로 금방 해결할 수 있는 문제다. 아이디어는 매우 간단하다. 아래를 구현할 수 있으면 된다. 모든 칸마다 안전 거리를 구하고, 최대값을 계속 갱신한다! 나는 문제를 풀기 위해 세 개의 배열을 사용했다. int init[50][50] → 초기 입력값 (변하지 않음) int use[50][50] → bfs 탐색할 때 사용하는 배열 (계속 바뀜) int visit[50.. [ 백준 14226 ] 이모티콘 (C++) https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 숨바꼭질2 문제와 거의 똑같은 문제다. 경로가 겹칠 수 있으므로 방문 처리는 pop과 동시에 해준다. 큐에 들어가는 원소는 총 아래의 세가 정보를 담고 있어야 한다. 1. 모니터 속 이모티콘 개수 (monitor) 2. 클립보드 이모티콘 개수 (board) 3. 시간 (time) 나는 obj라는 구조체를 선언해 세 가지 정보를 담았다. typedef struct{ int monitor; int bo.. [ 백준 13913 ] 숨바꼭질 4 (C++) https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질2 문제와 거의 비슷한데 경로까지 출력해야되는 문제다. parent 배열을 만들어 경로를 역추적 하는 것이 핵심이다. 부모를 찾는 아이디어는 합집합 찾기와 비슷하다. parent[현재 위치] = 이전 위치 // 목적지에 도달한 경우 pre1 = parent[to] parent[pre1] = pre2 { pre2 - pre1 - 목적지 } 경로가 성립한다 위.. [ 백준 13549 ] 숨바꼭질 3 (C++) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 그냥 bfs로 풀면 된다. 움직일 수 있는 경우의 수는 세 가지이므로 세 가지 조건에 대해 방문처리를 해주고 큐에 push 해주면 된다. 다만 조건문의 순서가 중요하다. 순서가 정답 코드와 동일해야 정답처리된다. 현재 위치를 Now라고 했을 때 조건문의 순서는 아래와 같다. 1. Now * 2 1 → 2 로 이동하는 경우를 생각해보자. 아래 두 가지 방법이 있다... [ 백준 12851 ] 숨바꼭질 2 (C++) https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 고민하다가 못 풀어서 정답을 봤다. 근데 대부분의 코드가 비슷했다. 다들 누군가의 코드를 참고했나...? 약간 발상의 전환이 필요한 문제다. 일반 bfs와 달랐던 점은 두 개였다. 1. 큐에 push 할 때 현재 위치 외에 time이라는 변수 추가 2. 방문처리의 위치 나는 기존에 bfs 문제를 풀 때 방문처리를 범위 조건문 안에서 해줬다. 그러니깐 새로운 원.. 이전 1 2 3 4 5 6 ··· 8 다음