📌 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 ..

📌 최대점수 구하기(냅색 알고리즘) 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는 데 걸리는 시간이 주어지게 된다. 제한 시간 M 안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 한다. (해당 문제는 해당 시간이 걸리면 푸는 걸로 간주한다. 한 유형당 한 개만 풀 수 있다.) 입력설명 첫 번째 줄에 문제의 개수 N(1

📌 동전교환(냅색 알고리즘) 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 입력설명 첫 번째 줄에는 동전의 종류개수 N(1

📌 최대 부분 증가수열(LIS) N개의 자연수로 이루어진 수열이 주어졌을 때, 그중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 문제이다. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가 수열을 만들 수 있다. 입력설명 첫째 줄은 입력되는 데이터의 수 N(1= 0; j--) { if (arr[j] < arr[i] && max < dy[j]) { max = dy[j]; } } dy[i] = max + 1; } answer = Math.max(...dy); return answer; } let arr = [2, 7, 5, 8, 6, 4, 7, 12,..

📌 02 - 돌다리 건너기(DP) 철수는 학교에 가는데 개울을 만났다. 개울은 N개의 돌로 다리를 만들어 놓았다. 철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있다. 철수가 개울을 건너는 방법은 몇가지일까? 📝 소스 코드 참고) 계단오르기 function solution(n) { let answer = 0; let dy = Array.from({ length: n + 2 }, () => 0); dy[1] = 1; dy[2] = 2; for (let i = 3; i

📌 01 - 계단오르기(동적 계획법) 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 📝 풀이 방법(DFS, DP) DFS 알고리즘을 사용하여 문제를 풀어보았다. 정답은 훌륭하게도 잘 나온다 👍 하지만 n의 값이 커진다면...❓ 연산 횟수가 기하급수적으로 증가하게 된다. 이를 해결할 수 있는 방법으로 동적 계획법(dynamic programming, DP)이 존재한다. function solution(n) { let answer = 0; function DFS(sum) { if (sum > n)..

📌 07 - 섬나라 아일랜드(BFS 활용) N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 문제이다. 만약 위와 같다면 섬의 개수는 총 5개이다. 섬나라 아일랜드(DFS) 문제와 같지만 이번에는 BFS 알고리즘을 이용해 풀어보았다. 영역을 탐색하는 문제의 경우에는 본인에게 편한 방법을 이용하여 풀면 될 것 같다..🤔 📝 풀이 방법 이중 for 문을 돌면서 1이 나온다면 섬을 발견한 것이므로 배열에서 해당 좌표를 0으로 재할당하고 answer++을 한다. 또한, 넓이 우선 탐색을 위해 큐에 해당 좌표를 추가한다. while 문을 돌면서 큐에서 shift 한 좌표에 대해 ..

📌 06 - 섬나라 아일랜드(DFS 활용) N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 문제이다. 만약 위와 같다면 섬의 개수는 총 5개이다. 📝 풀이 방법 미로 탐색 문제와 유사한 문제이므로 참고하면 좋을 듯하다. 이중 for 문을 돌면서 1이 나온다면 섬을 발견한 것이므로 배열에서 해당 좌표를 0으로 재할당하고 answer++을 한다. 해당 좌표에 대해 DFS를 돌면서 상하좌우와 대각선으로 연결된 좌표가 있는지 탐색한다. 연결된 좌표가 있다면 0으로 재 할당하고 연결된 좌표로 이동한다. 더 이상 연결된 좌표가 없다면 DFS 함수를 모두 종료하고 이중 for 문을..