백트래킹 이란? 완전 탐색을 하던 도중, 현재의 탐색이 무의미한 경우 되돌아가는 알고리즘을 의미한다. 말 그대로 모든 경우의 수에 대해서 탐색을 하던 도중, 조건과 맞지 않을 경우에 대해서는 탐색을 하지 않고 돌아간다는 뜻이다. 유명한 문제로 N-Queens 문제가 존재한다. 특징 모든 경우의 수를 탐색하지 않기 때문에 완전탐색보다 시간적으로 효율적이다. 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야 하기 때문에, 재귀를 사용해야 하는 경우가 많다. 조건에 맞지 않는 다면, 이전의 어떤 지점으로 돌아갈 지 정하는 것이 중요하다. 가지치기를 어떻게 구성하느냐에 따라 코드의 효율이 달라진다. 주로 백트래킹을 구현하다 보면, void함수와 전역 변수를 쓰면 쉽게 풀리는데 이는 다른 알고리즘에서 자중하..

문제 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 문제 설명 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 풀이 방식 처음엔 (모든 색종이의 넓이 - 중복된 넓이) 이런 방식을 통해 답을 구하려고 하였다. 하지만 이 방법이 간과한 부분은 n장의..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 오름차순의 수열을 구하는 프로그램을 작성해야 한다. 풀이 방식 A = { 70, 30, 50, 60, 70, 0, 10} 다음과 같은 수열이 있다고 하자. brute force식으로 구해보면 다음과 같다. 어떻게 해도 이 블로그 보다 설명을 잘 할 수 없으니 모르겠다면 참고 하도록 하자. 백준 11053번 가장 긴 증가하는 부분 수열 파..

문제 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 N개의 자연수와 자연수 M이 주어 졌을때, 다음 조건을 만족하는 길이가 M인 수열을 모두 구하면 됨. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 개인적으로 문제를 파악하기엔 중복 순열을 구하되, 비내림차순 조건을 만족하면 되겠다고 생각하고 문제를 푼 것 같다. 풀이 방식 내가..

문제 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 설명 아래와 같은 조건으로 나열하면 된다. 1. 길이가 짧은 것 부터 2. 길이가 같다면 사전 순으로 3. 중복은 제거한다. 풀이 방식 알고리즘 적으로 적어둘만 한건 없는 것 같다. 솔루션 #include #include #include using namespace std; bool compare(string a, string b) { if (a.length() != b.length()) return a.length() < b.length(..

문제 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 설명 봄보니 (Bomboni) 게임. N x N 크기의 랜덤한 사탕으로 채워져있는 판이 있다. 사탕 색이 다른 인접두 칸을 고른 뒤, 두 칸의 사탕을 교환한다. 마지막으로, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다. (뭐, 대충 옛날 애니팡 같은 게임 규칙.) 풀이 방식 이 문제는 brute force 방식 즉, 모든 방법을 다 탐색해야 한다. 1. 우선 (i, j)와 (i, j+1)의 위치를 바꾼다. 2. 그 다음엔 모든 row에 대해서 조..

문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 설명 스택의 특성에 따라 수열을 만들 것이다. 하지만 이 수열에 push 하는 순서는 반드시 오름차순을 지켜야 한다. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 판단하고, 어떤 순서로 push와 pop을 수행해야 하는지 알아내라. 풀이 방식 우선 문제의 이해가 조금 어려웠다. 예시를 들어 설명하자면, 예제의 size가 8인 스택에 수열을 ..

코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 내 코드 #include #include #include // prices_len은 배열 prices의 길이입니다. int* solution(int prices[], size_t prices_len) { // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요. int* answer = (int*)malloc(sizeof(int)*prices_len); int index = ..