백트래킹

[백준 17135] 캐슬 디펜스 (C++)

17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 오랜만에 풀어본 백준! 백트래킹을 사용한 완전탐색 문제였다. 주의해야할 궁수의 공격 특징은 다음과 같다. 모든 궁수는 동시에 공격하며 같은 대상을 공격할 수 있다. (같은 적이 여러 궁수에게 공격당할 수 있다.) 적과의 거리가 D이하이면 공격한다. 가장 가까운 적을 공격한다. (가장 가까운 적이 어렷일 시 가장 왼쪽의 적을 공격한다.) 1번과 3번 특징 때문에 궁수의 위치에 따라서 잡을 수 있는 적의 수가 달라질 수 있다는 것을 눈치채야 한다. 궁수가 적절히 배치되어 적을 ..

[백준 16637] 괄호 추가하기 (C++)

16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 꿀 조건 1. 괄호 안에는 연산자 하나만 들어갈 수 있다. 꿀 조건 2. 중첩된 괄호는 사용할 수 없고, 항상 올바른 수식만 주어진다. 모든 괄호 안에는 정직하게 정수1, 연산자, 정수2 의 형태로 구성되어있다. 이 점을 활용해서 백트래킹을 사용한 브루트 포스로 현재 연산자를 둘러싸는 괄호를 추가하는 경우, 그냥 넘어가는 경우 모두에 대해서 수식의 값을 확인하면 답을 구할 수 있다. 현재 연산자가 괄호로 둘러싸일 경우, 바로 다음 연산자(현재인덱스+2..

[프로그래머스 level2] 피로도 (C++)

현재 피로도에 따라서 최대로 탐험할 수 있는 던전의 수를 구하는 문제이다. 던전 탐험에 필요한 피로도가 2차원 배열로 주어지고, 던전 탐험 순서에 따라서 탐험할 수 있는 던전의 개수가 달라질 수 있으므로 백트래킹을 사용한 완전 탐색으로 구현했다. 매 dfs 호출마다 지금까지 탐험한 던전의 최대 갯수를 갱신해준다. (cnt는 매개변수로 가지고 있다.) answer = max(answer, cnt); 현재 던전에서 다음 던전으로 이동하는 부분이다. 주의할 점은 다음 던전으로 이동하기 위해서 현재 피로도가 다음 던전에 필요한 피로도보다 많아야 한다는 점이다. for(int i = 0; i < dungeons.size(); i++){ if(visited[i]) continue; if(nowHp < dungeon..

[프로그래머스] level2 단체사진 찍기 (C++)

2017 카카오코드 본선 사람이 8명 뿐이다. 모든 사람을 줄세우는데 O(8!) 만큼의 시간이 걸릴 것이다. 따라서 백트래킹으로 모든 경우를 탐색해도 시간내에 충분히 풀린다. 백트래킹 부분 void sorting(int cnt, int &answer, vector &data, map &m){ if(cnt == 8){ if(is_valid(data, m)){ answer++; } return; } for(int i = 0; i < 8; i++){ if(visited[i]) continue; visited[i] = cnt+1; sorting(cnt+1, answer, data, m); visited[i] = 0; } } 중요한 부분은 visited배열의 정의이다. visited배열의 인덱스는 사람의 번호이다..

[프로그래머스] level2 수식 최대화 (C++)

풀이 주어진 표현식을 숫자와 연산자로 나눈 후 각각 다른 배열에 넣어준다. 기본적인 백트래킹을 사용해 '*+-'로 구성된 연산자의 순서를 정해준다. 백트래킹의 마지막 부분에 도달해 연산자의 순서가 정해지면 표현식을 순서대로 계산한다. 현재 표현식의 연산자(forj)와 우선순위에 따른 연산자(fori)가 동일한 경우에 값을 계산해서 적절한 위치에 값을 갱신해준다. 그리고 사용한 연산자와 숫자는 erase메서드를 사용해서 지워준다. 여기서 주의할 점은 벡터를 for문으로 순회하는 도중에 원소가 지워지면 인덱스에 문제가 생길 수 있다. 따라서 현재 인덱스를 지워진 원소의 개수만큼 빼줘야 한다. 계산된 값을 비교하면서 최댓값을 저장해둔다. #include #include #include using namespa..

[백준 1941] 소문난 칠공주 (C++)

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에 단순 dfs로 갔다가 ㅓㅏㅗㅜ 모양으로 탐색이 불가능해서 바로 접었다. bfs로 다시 도전하는데 정점간의 상태정보를 공유할 수가 없어서 방법을 생각하다가 모든 경우의 수가 최대 25C7 = 48만으로 충분히 탐색 가능함을 깨닫고 dfs를 사용해서 상태 정보를 기록하고 구한 상태들이 서로 이어져 있는 경우를 찾는 방식으로 시도를 했다. 2차원 배열을 1차원 배열로 바꿔서 편하게 백트래킹을 할 수도 있었지만 굳이 내가 2차원 배열을 유지하면서 백트래킹을 해보려는..

[백준 3980] 선발 명단 (C++)

3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 백트래킹 인원수가 최대 11명이고 자신이 원하는 포지션 최대 5개 중 하나에 들어갈 수 있으므로 O(5^11 - @)의 시간복잡도가 가능하다고 생각한다. 포지션은 11개인데 11명의 선수가 원하는 포지션을 5개씩 가지고 있다면 중복되는 경우가 아주 많아서 백트래킹에서 걸러지게된다. 따라서 절대 O(5^11) 시간은 나올 수 없고 그보다 훨씬 적은 시간이 들 것으로 예상했다. 백트킹을 수행하면서 현재 선수가 원하는 포지션 중 하나에 들어갈 수 있다면 현재 선수의 스탯을 더하고 다음 선수로 넘..

[백준 1339] 단어수학 (C++)

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 브루트 포스 - 순열 (연습) 7달 전에 그리디를 사용해서 풀었었는데 이번엔 백트래킹 완전탐색을 이용해서 풀었다. 모든 단어를 입력받고 단어에 사용된 알파벳(최대 10개)를 중복 없이 걸러내기 위해서 중복을 허용하지 않는 자료구조인 set을 사용했다. 10개의 알파벳에 9~0까지의 숫자를 매칭해주고 모두 매칭이 된 경우 (cnt == 알파벳의 개수) 최대 10개의 단어를 매핑테이블(table[27])을 이용해 모두 숫자로 바꾸고 각각을 더해주었다. 매칭은 ..

[백준 2529] 부등호 (C++)

2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 브루트 포스 - 순열 (연습) 어제 푼 카카오 2021 하반기 공채 1차 코테 4번문제 (양궁) 과 비슷한 문제이다. 정렬이 잘못되었다고 하는데 나는 아직도 어디가 틀렸는지 감이 오지않는다. 경험삼아 쳐본 코테 덕분에 나 자신을 돌아보고 실력이 얼마나 부족한지 다시 생각해보는 계기가 되었다. 지금까지 하고싶은 알고리즘 공부, 재밌어보이는 문제, 내가 자신있는 파트의 문제 위주로 풀었고 자기 만족을 위해서 알고리즘 문제를 풀어왔다면, 남은 1년은 시험 공부하는 ..

[백준 2026] 소풍 (C++)

2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 백트래킹, 브루트 포스 소풍에 참여할 후보들을 nums배열에 차곡차곡 담아준다. 새로운 친구를 추가하려고 할 때 -> 새 친구는 지금까지 nums배열에 담긴 친구들과 모두 친구여야 한다. 이렇게 친구를 추가해 나가면서 nums배열의 길이가 K가 되면 지금까지 구한 친구들의 목록을 출력하고 exit한다. 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 ..