Seung's Learning Record

난이도 : 실버1 소요시간 : 1h 17m 사용한 풀이법 : DP 풀이 과정 풀이과정(백트래킹) 각 요소[i][j]는 대해서 [i+1][j],[i+1][j+1]만 더할 수 있음 해당 위치에서 이동가능한 경로를 인자로 해서 함수 재귀 진행 인자가 n과 같아지면 결과갑 리스트에 삽입 모든 경우의 수 탐색 후 리스트의 max를 출력하면 정답!! 이긴 한데 메모리 초과 뜸 풀이과정(DP) 위에꺼에서 아래꺼를 더하는 방식이 아닌 아래꺼에서 위에 값을 참조해오는 것으로 변경 =>메모리 손실 방지 참조 방식은 총 3가지 행의 첫번째 인자일 경우, 바로 위 행의 첫번째 인자값에 더하면 됨 ([i-1][0]) 행의 마지막 인자일 경우, 바로 위 행의 마지막 인자값에 더하면 됨 ([i-1][-1]) 행의 중간일 경우, 바..

난이도 : 실버2 소요시간 : 58분 사용한 풀이법 : 백트래킹 풀이 과정 1. 현재 원소 위치와 총합을 매개변수로 하는 func()정의 2. 현위치 변수가 n과 같고, 총합이 s와 같은 경우에 카운트 후 리턴 3. 조건 미 충족 시, func() 재귀 4. 재귀는 다음 위치의 수를 더하는 경우와, 더하지 않는 경우 두가지로 진행 5. S가 0일 때, 모두 더하지 않은 경우를 카운트에서 제외시켜야 함. 작성 코드 #include using namespace std; int n, s; int arr[30]; int cnt = 0; void func(int cur, int tot){ if(cur == n){ if(tot == s) cnt++; return; } func(cur+1, tot+arr[cur]);..

브루트 포스? 브루트 포스(brute force)의 사전적 의미는 '무식한 힘'이다. 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 '해가 하나 이상 존재한다.'는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 복잡한 알고리즘없이 빠르고 쉽게 구현이 가능하다는 장점이 있지만, 알고리즘의 실행시간이 오래걸리며 메모리 효율성이 떨어진다는 단점이 있다. 종류 선형 구조 : 순차탐색 비선형 구조 : 백트래킹, DFS, BFS 선형 구조 - 순차탐색 순차 탐색(Sequential Search)는 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로..