01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] 두 개의 문자열 A와 B가 주어졌을 때 문자열 A를 편집하여 문자열 B를 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 삽입 (Insert) : 특정한 위치에 하나의 문자를 삽입합니다. 삭제 (Remove) : 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체 (Replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열..

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] 못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴 수라고 가정합니다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,...} 순으로 이어지게 됩니다. 이때, n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다. [입력조건] 첫째 줄에 n이 입력됩니다. (1

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들..

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보..

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이..

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세..

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] N 가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. [입력 조건] 첫째 줄에 N, M이 주어진다. (1 ≤ N ≤ 100, 1 ..

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. [입력 조건] 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000) [출력 조건] 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최솟값을 출력한다. 첫째 줄..

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 ..

01 당장 좋은 것만 선택하는 그리디 02 아이디어를 코드로 바꾸는 구현 03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS 04 기준에 따라 데이터를 정렬 05 범위를 반씩 좁혀가는 탐색 06 다이나믹 프로그래밍 07 가장 빠른 길 찾기 08 다양한 그래프 알고리즘 [문제] 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지이다. x가 5로 나누어 떨어지면, 5로 나눈다. x가 3으로 나누어 떨어지면, 3으로 나눈다. x가 2로 나누어 떨어지면, 2로 나눈다. x에서 1을 뺀다. 정수 x가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하시오. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 26 -..