알고리즘
-
[백준 2580] 스도쿠알고리즘/Brute Force 2019. 12. 25. 21:58
문제 바로가기 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..
-
[백준 15989]1,2,3 더하기 4알고리즘/Dynamic Programming 2019. 12. 18. 09:57
문제 바로가기 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; } ... } 대략적인 재귀 함수의 탈출 조건을 생각하면 위와 같이 구성 할 수 있다. 하지만 재귀 함수를 통해 구현하면..
-
[백준 1644] 소수의연속합알고리즘/Brute Force 2019. 12. 16. 18:04
문제 바로가기 Type : 브루트포스 접근 n 이하의 모든 소수를 저장한 배열을 만든다. 소수 배열을 만들때는 에라토스테네스의 체를 활용 한다 에라토스테네스의 체 2부터 n 까지의 소수를 구하는 방법 이다. x의 배수는 x를 약수로 가진다는 원리를 이용 한다. 2부터 n까지 순회 하며 만약 숫자가 소수 라면 (숫자 + 숫자) ~ n 까지 순회 소수[숫자]는 false 숫자 = 숫자 + 숫자 부분 합 문제와 동일하게 투포인터 알고리즘을 활용하여 소수 만으로 n을 만들 수 있는 경우의 수를 구한다 주의할 점 (1)인덱스 초과 에러를 방지 하기 위해 탐색 범위를 n 이 아닌 vector의 size로 지정 해야 한다 (2)n이 1로 주어질때는 만들 수 있는 소수가 없기 때문에 소수 배열에 접근하려고 할때 인덱스..
-
[백준 1806]부분합알고리즘/Brute Force 2019. 12. 16. 18:04
문제 바로가기 Type : 브루트포스 접근 완전 탐색으로 구현하면 시간초과 발생하는 문제 o(n^2) 분할정복을 하면 중간값을 계산하지 못해 틀리는 문제 특정 구간을 정하여 작업을 수행할 수 있는 투포인터 알고리즘을 활용 해야 하는 문제이다. 투 포인터 알고리즘은 시간복잡도가 o(n)이다 투포인터 알고리즘 이란? 두개의 피봇(start, end)을 적절히 움직여 배열의 특정 구간을 지정하는 것이다 end를 한칸 뒤로 옮긴 후에는 sum에 arr[end]를 더해준다 start를 한칸 뒤로 옮긴 후에는 sum에서 arr[start]를 빼준다 투포인터 알고리즘 진행 방식 start, end를 0으로 초기화 한다. sum 은 배열의 첫번째 원소로 초기화 한다. start가 end 이하이며 end가 n 미만 일동..
-
[백준 15988]123 더하기 3알고리즘/Dynamic Programming 2019. 12. 16. 10:14
문제 바로가기 Type : Dynamic Programming 접근 재귀 탐색만으로는 시간 초과가 발생 하는 문제이다. 접근을 달리하여 완전 동적 계획법으로 문제를 풀어야 한다. 주요 포인트 함수의 배열화 함수의 배열화란 예상되는 함수의 결과값을 배열에 미리 저장해두어 계산해나가는 방식을 말한다. 주로 Bottom UP 방식에서 활용 된다. 이번 문제처럼 재귀트리가 무수히 많이 발생하는 경우에는 작은 값부터 배열을 채워나가는게 효율적이다. 100 만번 * 3 => 1초이내 해결가능 함수의 배열화 응용 1, 2, 3 더하기를 좀 더 깊이 생각해보면 숫자 n을 만드는 경우의 수는 갯수(n-1) + 갯수(n-2) + 갯수(n-3) 과 같다 1로 시작 하면서 n을 만드는 경우 2로 시작 하면서 n을 만드는 경우..
-
[백준 12101]123 더하기2알고리즘/Dynamic Programming 2019. 12. 16. 10:13
문제 바로가기 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..
-
[백준 15558] 점프게임알고리즘/BFS 2019. 12. 13. 17:29
문제 바로가기 Type : BFS 접근 문제에 주어진 조건을 잘 지키면서 일반적인 BFS와 유사한 탐색을 진행 한다. 조건 1. 시간이 지날때마다 한칸이 사라지므로 시도횟수가 n을 넘어서면 안된다. 조건 2. x>=n 이다. 배열의 시작은 0부터 시작되므로 n과 동일하기만 해도 범위를 벗어난 것이다. 조건 3. 시간이 지나 사라지거나 0이 표시된 위치로는 접근 할 수 없다. 조건 4. 이미 방문한 곳은 다시 방문 할 수 없다. 구조체 선언 위치 (y, x)와 시간(time)을 저장할 수 있는 구조체를 선언한다. 탐색 진행 탐색이 끝나거나 게임에 성공할때까지. 큐로부터 walker 객체를 꺼낸다 문제에 주어진 동작에 따라 3가지의 새로운 walker 객체를 만든다. 만약 새 walker의 x가 n보다 크거..
-
[백준 9095]123 더하기알고리즘/Dynamic Programming 2019. 12. 13. 10:11
문제 바로가기 Type : Dynamic Programming 접근 0부터 시작하여 1,2,3을 각각 더해 n까지 도달할 수 있는 경우를 재귀탐색 한다 f(0) -> f(0+1) + f(0+2) + f(0+3) f(1) -> f(1+1) + f(1+2) + f(1+3) f(2) -> f(2+1) + f(2+2) + f(2+3) ... 만약 n이라는 숫자가 정확하게 만들어 졌다면 true 그렇지 않다면 false를 반환 한다. 일반 재귀 함수 int find(int num){ if(num == n){ return true; } if(num > n){ return false; } return find(num+1) + find(num+2) + find(num+3); } 문제에선 최대 값이 11이므로 메모이제이..