백트래킹을 제대로 배울 수 있는 기본 문제.(사실 기본 문제라고 하기엔 처음엔 너무 어려웠다....) 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 의 조건문을 넣..

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