넘어지고 일어나기 넘어지고 일어나기

문제 바로가기 Type : 백 트랙킹 Queen 이란? 상,하, 좌, 우 대각선으로 모두 움직일 수 있는 체스의 말을 뜻한다. 나의 접근 공격 범위를 1부터 n까지 증가 시키며 첫 Queen의 위치를 (y, x)로 둔다. 공격 범위 1 첫 Queen의 위치 : (0, 0) 첫 Queen의 위치 : (0, 1) 첫 Queen의 위치 : (0, 2) ... 공격 범위 2 첫 Queen의 위치 : (0, 0) 첫 Queen의 위치 : (0, 1) 첫 Queen의 위치 : (0, 2) ... ... 주어진 위치와 공격범위를 대상으로 n개의 queen을 놓을 수 있는지 검사한다. 주어진 위치에는 반드시 Queen을 놓는다. 공격 거리를 점차 증가 시킨다. y, x가 어느것과도 겹치지 않으면 Queen을 놓는다. ..

문제 바로가기 Type : 브루트포스 + 백트랙킹 접근 빈 칸을 채워 나갈때 존건에 부합하는지 검사 한다 (퇴각 검사) 가로 및 세로 줄의 모든 숫자는 중복없이 고유 해야 한다 위치에 속한 3x3 영역 내의 숫자도 중복없이 고유 해야 한다. 위치 판별 y와 x를 각각 3으로 나눈다 => 0, 1, 2 중 하나의 숫자가 나온다 영역 시작 점 = 3 * 몫 영역 종료 점 = 3 * (몫+1) 완전 탐색 및 종료 조건에 부합하는 모든 수를 채우면 테이블을 출력하고 종료 한다. 플로우 차트 빈칸에 채워질 숫자가 고유한지 검사하는 isUnique 구현 코드 #include #include using namespace std; int table[9][9]; vector emptyPoints; bool isUniqu..

문제 바로가기 Type : Dynamic Programming 접근 중복된 원소를 걸러내는 방법을 아는 것이 주요 포인트 중복을 방지하기 위헤 조건을 걸어야 한다 이 문제에선 맨 처음 숫자보다 작거나 큰수의 경우만 경우의 수로 합산한다 예를 들어 1 + 3 과 3 + 1 이 있을때 1 + 3 은 추가될 수 없다 재귀 함수로 생각 해보기 int find(int num, vector arr){ if(num == n){ if(arr.size() > 1 && arr[1] > arr[0]){ return false; } return true; } if(num > n){ return false; } ... } 대략적인 재귀 함수의 탈출 조건을 생각하면 위와 같이 구성 할 수 있다. 하지만 재귀 함수를 통해 구현하면..

문제 바로가기 Type : 브루트포스 접근 n 이하의 모든 소수를 저장한 배열을 만든다. 소수 배열을 만들때는 에라토스테네스의 체를 활용 한다 에라토스테네스의 체 2부터 n 까지의 소수를 구하는 방법 이다. x의 배수는 x를 약수로 가진다는 원리를 이용 한다. 2부터 n까지 순회 하며 만약 숫자가 소수 라면 (숫자 + 숫자) ~ n 까지 순회 소수[숫자]는 false 숫자 = 숫자 + 숫자 부분 합 문제와 동일하게 투포인터 알고리즘을 활용하여 소수 만으로 n을 만들 수 있는 경우의 수를 구한다 주의할 점 (1)인덱스 초과 에러를 방지 하기 위해 탐색 범위를 n 이 아닌 vector의 size로 지정 해야 한다 (2)n이 1로 주어질때는 만들 수 있는 소수가 없기 때문에 소수 배열에 접근하려고 할때 인덱스..

문제 바로가기 Type : 브루트포스 접근 완전 탐색으로 구현하면 시간초과 발생하는 문제 o(n^2) 분할정복을 하면 중간값을 계산하지 못해 틀리는 문제 특정 구간을 정하여 작업을 수행할 수 있는 투포인터 알고리즘을 활용 해야 하는 문제이다. 투 포인터 알고리즘은 시간복잡도가 o(n)이다 투포인터 알고리즘 이란? 두개의 피봇(start, end)을 적절히 움직여 배열의 특정 구간을 지정하는 것이다 end를 한칸 뒤로 옮긴 후에는 sum에 arr[end]를 더해준다 start를 한칸 뒤로 옮긴 후에는 sum에서 arr[start]를 빼준다 투포인터 알고리즘 진행 방식 start, end를 0으로 초기화 한다. sum 은 배열의 첫번째 원소로 초기화 한다. start가 end 이하이며 end가 n 미만 일동..

문제 바로가기 Type : Dynamic Programming 접근 재귀 탐색만으로는 시간 초과가 발생 하는 문제이다. 접근을 달리하여 완전 동적 계획법으로 문제를 풀어야 한다. 주요 포인트 함수의 배열화 함수의 배열화란 예상되는 함수의 결과값을 배열에 미리 저장해두어 계산해나가는 방식을 말한다. 주로 Bottom UP 방식에서 활용 된다. 이번 문제처럼 재귀트리가 무수히 많이 발생하는 경우에는 작은 값부터 배열을 채워나가는게 효율적이다. 100 만번 * 3 => 1초이내 해결가능 함수의 배열화 응용 1, 2, 3 더하기를 좀 더 깊이 생각해보면 숫자 n을 만드는 경우의 수는 갯수(n-1) + 갯수(n-2) + 갯수(n-3) 과 같다 1로 시작 하면서 n을 만드는 경우 2로 시작 하면서 n을 만드는 경우..

문제 바로가기 Type : 다이나믹 프로그래밍, 탐색 접근 1,2,3 더하기 1에서 약간의 응용이 들어간 문제다. 재귀 탐색 부분에서 수를 추가할때마다 vector에도 숫자를 추가 해준다 탐색 함수를 호출할 때 숫자를 추가한 vector를 넘겨 준다 1,2,3 으로 n을 만들 수 있을때 2차원 vector에 vector를 추가 한다. 문제에 주어진대로 정렬을 한다 만약 2차원 배열의 길이가 k를 넘는다면 -1, 그렇지 않다면 결과 출력 구현 코드 #include #include #include #define MAX 12 using namespace std; int arr[12]; //2차원 배열 vector lists; int n, k; bool comp(vector a, vector b){ int id..

문제 바로가기 Type : BFS 접근 핵심 원리 나머지에 0과 1을 덧붙이면 몫에도 동일한 수가 덧붙여 진다 나머지에 0과 1을 덧붙인 후 다시 n을 나누면 몫에 0과 1을 덧붙여 나눈것과 동일한 결과 예를 들어 10 % 7 = 3 일때 나머지가 30 이면 몫이 100 나머지가 31 이면 몫이 101 BFS 탐색을 통해 몫에 0 혹은 1을 덧붙여 나가면 오버플로우가 발생 한다 나머지가 0이 될때까지 나머지에 0혹은 1을 덧붙여 나가는 탐색을 진행 한다 BFS 트리의 루트까지 찾아가 역순으로 어떤 수를 덧붙였는지 출력한다 자료 구조 map numByRemain : 나머지를 만들기 위해 어떤 수를 덧붙였는지 저장 (라벨링) int parents[] : BFS 트리의 부모 정보를 담기 위한 배열 bool v..