백트래킹을 제대로 배울 수 있는 기본 문제.(사실 기본 문제라고 하기엔 처음엔 너무 어려웠다....) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen 문제 풀이시 Check Point 상하, 좌우, 대각선에서 좌우의 경우 DFS에서 Level 단위(column)로 내려가기 때문에 고려할 필요가 없다. [check 함수 1번째 조건문] 대각선의 경우 for loop를 돌며 0에서 현재 있는 좌표까지 x 좌표의 차의 절대값과 y 좌표의 차의 절대값이..

완전 탐색과 백트래킹을 활용한 기본 문제. https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 사람 허파 뒤집는 문제였다..진심 부분 수열의 합 문제 풀이 Check point 1. 재귀함수를 사용하여 푸는 문제. 현재 인덱스에 있는 값을 더하는 경우와, 더하지 않고 다음 인덱스로 넘어가는 경우를 나누어 구현 2. 리스트 내의 숫자에 따라 모든 조합을 확인하지 않을 수 있으므로 depth == N 의 조건문을 넣..

불쌍한 준석이를 도와주기위해 풀었던 문제... Union Find 알고리즘을 활용하여 푸는 문제로, 각각의 정점을 입력 받을 때 친구비가 가장 적게 드는 정점으로 부모노드를 지정하여 합집합을 만든 후 순차적으로 정점을 탐색하며 해당 정점의 부모노드가 탐색되지 않은 부모노드일 경우 check 한 이후 cost를 더해가면 된다. 다른 사람 풀이도 참고를 했는데, 결과적으로 중요한건 합집합을 모두 완성한 후 해당 노드가 탐색하지 않은 노드일 경우(같은 집합이 아닌 경우) 해당 cost를 더해주는 것이 중요하다. 나는 check 배열을 선언해 해당 정점이 탐색하지 않은 정점일 경우 cost에 더해주었다. 혹은 탐색하지 않은 정점일 경우 cost를 더해준 이후 0으로 합집합을 만들어주는 방식도 있다. 또한 친구비..

ㅂ크루스칼 알고리즘과 Union Find 알고리즘을 연습하기 좋은 문제다. https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘은 Greedy 알고리즘의 일종으로, 트리의 간선을 오름차순으로 정렬한 후 가중치가 가장 적은 간선부터 cycle이 생기기 전까지 차례로 합집합으로 만들어나가는 알고리즘이다. cycle의 생성 유무는 Union-Find 알고리즘으로 확인할 수 있다. 간선 정보를..

대표적인 탐색 기본 문제이다. 기본적으로 투포인터나 이분 탐색 알고리즘을 통해 찾을 수 있지만, 본 문제는 이분탐색 알고리즘을 활용해 풀었다. 참고로 이분 탐색과 투포인터 알고리즘의 차이점은 다음과 같다. 이분 탐색(이진 탐색) 투포인터 시간복잡도 O(log N) O(N) 방식 mid를 사용해 연산마다 탐색해야하는 데이터를 절반으로 줄임(log N) 양 끝단(혹은 첫 인덱스에서)시작하여 한칸씩 이동하며 적절한 값을 찾음 조건 데이터가 정렬된 상태에서 가능 상관 없음 투포인터 알고리즘의 경우 양끝단(혹은 첫 인덱스)에서 시작하여 한칸씩 이동하며 알맞은 값을 찾기 때문에 구간 합을 구할 때 유용하게 사용할 수 있다. 이분탐색 알고리즘은 특정한 값을 찾고자 할때 인덱스의 중간값을 사용하여 찾고자하는 값과 비교..

기존 문제인 숨바꼭질 문제와 유사하지만, 최단 시간에 도착한 경로의 개수를 찾아야된다는 점에서 차이가 있다. https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 따라서 해당 노드와 탐색 깊이를 모두 저장할 수 있는 pair 자료형 queue를 선언해 while loop를 실행한다. 최단 시간을 찾은 이후에도 계속해서 최단시간을 만족하는 경로를 추가해야하기때문에, Queue에 들어온 도착 노드가 최단 시간을 만족..