분류 전체보기

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제는 DFS를 통한 백트레킹으로 해결할 수 있다. 알고리즘은 다음과 같다. vector에 N만큼의 입력 값을 삽입하고, 삽입이 끝나면 sort를 통해 오름차순으로 정렬한다. DFS를 0번 인덱스 부터 수행한다. 방문하지 않은 인덱스라면 방문 표시를 하고 cnt자리에 i번째 인덱스를 삽입한다. (DFS의 값) num은 필요하지 않은 값이지만 넣어버렸다.(실수) #include #inc..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 DFS를 통한 백트레킹을 통해 해결할 수 있다. 알고리즘은 다음과 같다. N과 M (2)와 다르게 2자리를 출력할 때 같은 숫자를 출력해야한다. 따라서 dfs의 visited 배열을 빼고 순회하면 같은 숫자인 수열도 뽑을 수 있다. #include using namespace std; int N, M; int arr[9] = { 0, }; int visited[9] = { 0, }; ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이 문제는 Dynamic Programming을 사용해서 해결해야한다. 알고리즘은 다음과 같다. 계단은 1 step과 2 step으로 이동할 수 있다. dp[0]은 1번째 계단으로 한다. 또한 dp[1]은 2 step으로 이동했을 때와 1step으로 이동했을 때의 최대값으로 한다. dp[2]는 1번째 계단에서 2 step으로 이동했을 때와 2번째 계단에서 1step으로 이동했을 때의 최대값으로 한다. 위 알고..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이 문제는 Dynamic Programming을 사용해서 해결할 수 있다. 주요 알고리즘은 다음과 같다. N개의 집에 대해 RGB의 비용을 입력받는다. 이때 1번째 집은 0번째 집. 즉, 0과 비교하여 R G B의 최소 값을 house 배열에 저장한다. R G B의 최소 값을 구할 때 R의 경우 이전 값의 G와 B의 최소 값과 더한다. (인접한 경우 같은 색을 칠하면 안된다)..

Dynamic Programming이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말. Dynamic Programming이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요는 없다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 한다. Dynamic Programming 방법 모든 작은 문제들은 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 저장해 두어야 한다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 저장한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복이 일어나는 경우. 같은 문제는 구할 때마다 정답이 같다. 위 와같은 조건을 만족하는 경우에만 동..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 DFS를 통해 해결해야한다. 알고리즘은 다음과 같다. DFS를 1부터 0번째 수열을 먼저 검사한다. (모든 수열은 1부터 시작함) M의 자리까지 DFS를 수행하였다면, 배열을 출력하고 DFS를 종료한다. DFS를 수행할 num부터 N까지 반복을 수행하며, 방문하지 않은 수라면 배열에 i를 저장한다. i를 통해 수열의 순서 번호를 증가시키며 DFS를 수행하고, 방문 표시를 초기화한다. ..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이 문제는 우선순위 큐를 사용해서 해결할 수 있다. 알고리즘은 다음과 같다. 내림차순과 오름차순으로 정렬해주는 우선순위 큐를 선언한다. 큐의 요소는 값과 삽입 순서를 넣는다. 우선순위 큐 생성 방법 priority_queue 비교 연산자에는 less과 greater이 있다. 자료형에 pair를 사용하는 경우 정렬 시 첫번째 값을 통해 먼저 정렬하고, 값이 같을 경우 두번째 값을 통해 정렬 구현..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 이 문제는 deque를 이용해서 해결해야 한다. R 연산의 경우 deque의 특성인 앞뒤 빼기가 가능하다는 점을 통해 boolean 타입의 변수를 통해 reverse 상태면 D연산 시 뒤를 빼도록 하고 reverse상태가 아니면 D 연산 시 앞을 빼도록 한다. 입력 배열의 형태가 [1,2,3] 과 같은 형태이므로 이 값을 deque에 삽입하기 위해 숫자를 빼내야한다. 이를 위해 문자열의 길이만큼 배열을 순회하고 현재 문자열의 요소가 숫자인 경우 민 문..