주녘공부일지

https://www.acmicpc.net/problem/17070핵심 아이디어 및 정답 코드- 파이프를 옮길 수 있는 경우의 수를 구하는 문제- 접근 방식에 따라 DFS, DP로 풀 수 있음 맨 위에부터 DP, DFS(도착지에서 탐색), DFS(출발지에서 탐색)1. DFS 풀이https://godgjwnsgur7.tistory.com/47 [Algorithm C#] BFS, DFS ( + Back Tracking )1. BFS(Breadth First Search) - 너비 우선 탐색최단 경로, 임의의 경로를 찾고 싶을 때, 등에 사용- 큐(FIFO) 사용 // 큐를 이용 public void BFS(int index) { Node root = nodes[index]; Queue queue = new ..

https://www.acmicpc.net/problem/9375핵심 아이디어 및 정답 코드- 해당 옷을 입지 않은 경우의 수를 같이 구하면 한번에 구할 수 있음- 의상 종류 개수 + 1을 전부 곱하면, 아무것도 입지 않은 경우의 수가 포함되므로 마지막에 1을 빼줌 + 처음에 DFS로 접근했다가 시간 초과를 경험함ㅠ; 정답 코드#include #include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int totalCount; cin >> totalCount; for (int i = 0; i m; int count; cin >> count; for (int j = 0; j > str..

A* 알고리즘이란?다익스트라 알고리즘에서 동적 계획법(DP)을 적용시켜 확장한 최단 경로 탐색 알고리즘- 탐색이 가능한 모든 노드 중 현재 최적이라고 판단되는 노드를 탐색1.  A* 알고리즘의 개념- 닫힌 목록 : 탐색이 끝난 노드들의 집합 ( 다시 탐색 X )- 열린 목록 : 탐색이 가능한 노드들의 집합 ( 닫힌 목록과 인접한 노드 )g(x) : 시작점을 기준으로 한 비용h(x) : 도착점까지의 예상 비용 // 휴리스틱 함수f(x) = g(x) + h(x) - 휴리스틱 함수 h(x)에 따라 성능이 변함  -> h(x) 이 g(x) or 0 인 경우 다익스트라 알고리즘과 동일 + 휴리스틱 함수란?현재 노드에서 목표 노드까지의 예상 비용을 구하는 함수 -> ex. 맨해튼 거리 함수, 유클리디안 거리 함수2..