거창한 시작

https://www.acmicpc.net/problem/16197 알고리즘 종류 완전탐색 사고 과정 1. 코인1과 코인2를 담는 객체가 필요하다. 2. BFS를 활용하여 코인의 이동을 구현한다. 이때 재방문을 방지하기 위해서 isVisited[][][][]를 활용한다. 3. 각 코인이 범위 내에서 벽을 만났는지, 범위 내에서 이동했는지, 범위 밖으로 나갔는지 확인한다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 6..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 알고리즘 종류 구현 사고 과정 1. 회전시키기 - 격자 모양으로 이동하기 위해서 2^L 만큼 이동한다. - 격자 모양의 좌측 상단 위치에서 차례대로 회전한다. - 아래 이미지처럼 주황색(원본 배열)에서 빨강색(임시 배열)으로 옮기고 다시 주황색으로 옮길 것이다. 시계방향 90도 회전은 (i, j) => (j, 길이-1 - i) 이다. 이때, 격자 모양의 초기 위치(격자마다 좌측..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 알고리즘 종류 구현 사고 과정 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 ..

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 알고리즘 종류 구현 사고 과정 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62..

www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 알고리즘 종류 완전탐색 사고 과정 2가지 경우가 있습니다. 1. 100에서 + 또는 -을 눌러서 채널 N에 도착하는 경우 2. 채널 N에 근접한 채널에 도착해서 + 또는 -을 누르는 경우 저는 채널 N에 근접한 채널을 찾기 위한 방법을 생각해서 코딩을 했지만 보증된 방법이 아니었습니다. 그래서 완전탐색으로 모든 채널에서 N에 + 또는 -로 이동한 횟수를 찾아서 최솟값을 찾으면 됩니다. 구현(C+..

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 알고리즘 종류 자료구조 분리집합 사고 과정 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #..

www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 알고리즘 종류 자료구조 스택 사고 과정 왜 스택으로 풀 수 있을까요? 문제에서 제시된 오큰수의 정의를 보면, Ai의 오른쪽에서 Ai보다 큰 수들 중에 가장 왼쪽에 있는 수 라고 합니다. A2의 오큰수는 A6의 7이 됩니다. 그런데 A2만 7이 오큰수이지는 않습니다. A3, A4, A5도 7이 오큰수 입니다. 이는 마치, 스택에 3,5,2,3,4가 있는 상태에서 7보다 작은 수는 모두 꺼내서 오큰수를 7이라고 명명하는 것과 같..

www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 알고리즘 종류 자료구조 부분 집합 사고 과정 문제에서 제시된 예시를 가지고 손으로 풀이를 해보고 있었습니다. 파티에서 참가하는 사람들을 하나로 묶고 그중에서 한 명이 진실을 알면 파티에 갈 수 없다고 생각했습니다. 즉, 부분 집합을 만들면 될 것 같았습니다. 1. 인접 리스트(party)로 파티에 들어갈 사람들을 담습니다. 그리고 for문으로 파티를 돌면서 부분 집합을 만듭니다. 2. 파티를 for문으로 돌면서 부모(대표..

www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 알고리즘 종류 자료구조 우선순위 큐 사고 과정 1. 최솟값과 최댓값을 저장할 우선순위 큐 2개가 필요합니다. 2. 최댓값을 저장한 우선순위 큐에서 최댓값을 제거하면, isVisited 배열에 해당 숫자를 제거했다고 표시합니다. 이렇게 표시하여 최솟값 우선순위 큐에서 해당 숫자를 처리할 수 있습니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21..

www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 알고리즘 종류 자료구조 우선순위 큐 사고 과정 1. 강의실을 배정하기 위해서 시작 시간을 기준으로 오름차순 정렬을 합니다. 2. 수업 시간을 하나씩 가져옵니다. 현재 수업의 시작 시간이 이전 수업의 끝나는 시간보다 크다면 빈 강의실이므로 우선순위 큐(pq)에서 꺼냅니다. 꺼낸 강의실 번호를 저장합니다. 3. 빈 강의실이 있다면, 그 곳에 현재 수업을 배정합니다. 빈 강의실이 없다면, 강의실을 하나 추가합니다. 구현(C++) 1 2 3 4 5 6 7 8 9 1..