알고리즘 (3) 썸네일형 리스트형 DP 알고리즘 (1) 알고리즘 공부를 하면서, 언젠가는 이해를 하고 구현을 해봐야지 했던 것이 다이나믹 프로그래밍 DP였다. 큰 문제를 작은 문제의 결과값을 이용해서 계속 풀어나가는 알고리즘인데, 대표적인 문제로는 피보나치수열을 DP배열에 저장하면서 푸는 방법이 있다. 가장 중요한 것이, 점화식을 빨리 찾아내는 것이라고 생각한다. 백준 18427번 문제를 풀어보았다. 이 문제는 몇번째 학생의 높이가 h일때의 경우의수를 계속 더해가면서, 내가 구하고자 하는 n번째 학생 h높이일 때 최종적으로 다 더한 경우의 수를 DP배열에서 반환해주면 된다. 이 문제에서는 경우의 수를 더해가는 것이 중요했는데 예제를 기준으로 보면 처음 DP테이블 초기화는 이렇게 했다. dp[i][0] ~ dp[i][h] 까지 채우면서, i가 N까지 반복을 한.. DFS, BFS 알고리즘 (1) DFS의 경우 스택, BFS의 경우 큐를 이용해서 이해하는게 편함 방문했다는 걸 표시하는 배열, 그래프 정보가 있는 배열이 필요 작은 순으로 방문을 한다는 기준 DFS 1. 시작 노드 스택에 삽입, 방문처리 2. 인접 노드중 가장 작은수 방문처리, 스택에 삽입 3. 2번 반복, 더 이상 방문 가능한 노드가 없을 시 스택 pop 4. 스택 top으로 이동, 3번 반복 (스택을 쓴다는걸 재귀로 이해해서 구현) BFS 1. 시작 노드 큐에 삽입, 방문처리 2. 큐의 front를 pop, 인접 노드들 모두 큐에 삽입 후 방문처리 3. 2번 반복 백준 1260번 https://www.acmicpc.net/problem/1260 #include #include #include #include #include usi.. 매개변수 탐색 알고리즘(1) 매개변수 탐색 https://m42-orion.tistory.com/70 참고해서 공부했음 어떤 시점까지 조건을 만족하지만, 그 후로는 조건을 만족하지 않는 경우, 조건을 만족하는 최대값 찾기 어떤 시점까지는 조건을 만족하지 않지만, 그 후로는 조건을 만족하는 경우, 조건을 만족하는 최소값 찾기 매개변수(param)와 결정함수(fn(param)) 1.매개변수 param 조건에 만족하는 최소/최대값 찾기 -> 검사하는데 사용하는 매개변수 param 검사범위(left, right)에서 중간 값 2.결정함수 fn(param) param이 조건을 만족하면 true, 만족하지 않으면 false 반환값에따라 검사범위 변경 조건을 만족 -> param의 값에 따라 문제에서 주어진 조건을 만족? 문제에서 원하는 조건 .. 이전 1 다음