i.am.developer

Artificial Intelligence: A Modern Approach 참고 Uniform Cost Search Breadth First Search와 비슷한 알고리즘이지만 조금의 차이가 있다. POP을 한 다음 Goal Test를 수행. Path cost $g(n)$ 순으로 POP 수행. Time Complexity: $O(b^{1+c^/\epsilon})$, Space Complexity: $O(b^{1+c^/\epsilon})$ $c^*$: Optimal Cost. $\epsilon$: 작은 양의 상수. 수도코드 출처: Artificial Intelligence: A Modern Approach A* 탐색 A* 탐색은 node를 $f(n) = g(n) + h(n)$을 이용해 탐색한다. $g(n..

스택과 큐 스택과 큐는 데이터를 저장하는 동적인 자료구조이다. 스택은 LIFO(last in first out) 구조이고 큐는 FIFO(first in first out) 구조이다. 큐 데이터가 FIFO의 흐름을 갖고 있다. 줄 서는 것을 생각하면 된다. 먼저 온 사람이 먼저 들어간다.데이터의 삽입은 뒤(rear), 데이터의 삭제는 (front)에서 이루어진다. 종종 head, tail이라 한다. 항목이 큐에 삽입될 때는 Enqueue, 상목이 큐에서 제거될 때는 Dequene. 빈 큐에 Dequeue하려는 것은 Underflow, 가득 찬 큐에 Enqueue하려는 것은 Overflow이다. 큐의 앞부분을 front, 혹은 head라고 하고 뒷부분을 rear 혹은 tail이라 한다. 큐는 공간낭비를 방지..

스택과 큐 스택과 큐는 데이터를 저장하는 동적인 자료구조이다. 스택은 LIFO(last in first out) 구조이고 큐는 FIFO(first in first out) 구조이다. 스택 스택은 접시가 쌓인 걸 상상하면 된다. 접시를 꺼내는 순서는 맨 위에 놓인 접시가 가장 먼저 나온다. 접시를 꺼내는 순서는 맨 위에 놓인 접시가 가장 먼저 나온다. 항상 맨위의 접시를 꺼낸다는 순서를 생각하면 Last In First Out, LIFO의 구조이다. 스택에 무언갈 넣는 것을 PUSH연산이라고 한다. 반대로 꺼내는 것, 삭제(Delete)는 POP연산이다. 빈 스택에서 POP하려는 것을 Undeflow, 가득 찬 스택에서 PUSH하는 것을 Overflow라고 한다. 가장 최근에 Insert한 요소의 인덱스를..

유튜브의 권오흠 교수님 강의를 참고했습니다. 멱집합이란 어떤 집합의 모든 부분 집합의 집합이다. 우선 부분집합이 뭔지 생각해보자. data = {a,b,c,d} 라는 집합이 있을 때, 이 집합의 모든 부분집합의 개수는? 16개이다. n개의 원소를 가진 집합의 부분집합의 개수는 2^n개이다. 예를 들어 {a,b,c,d}의 모든 부분집합을 나열하려면 1. {a} 를 제외한 {b, c, d}의 모든 부분집합들을 나열하기 2. {a, b,c,d}의 모든 부분집합에 {a}를 추가한 집합들을 나열하기 위 두가지 작업이 이루어지면 된다. 즉, {a,b,c,d}의 부분집합은 아래의 두 집단으로 구성된다. {a}를 포함한 집합 ⇒ 2^3개 {a}를 포함하지 않는 집합 ⇒ 2^3개 => 둘이 합하면 2^4개! 이걸 계속 ..

너비 우선 검색 기법은 그래프를 검색하거나 원형 구조(archetype)을 검색할 때 유용합니다. 개념은 단순하지만 깊게는 Prim's Minimum-Spanning-Tree 알고리즘이나 다익스트라의 Single source shortest path까지도 BFS와 관련된 알고리즘입니다. CLRS의 수도 코드 Graph G for each vertex u in G.v u.color = WHITE u.d = INF u.p = NIL s.color = GRAY s.d = 0 s.p = NIL Queue Q Enqueue(Q, s) while Q is not empty() u = Dequeue(Q) for each v In G.adj[v] if v.color == WHITE v.color = GRAY v.d =..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2≤n≤1000, 2≤m≤1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다. www.acmicpc.net 간단한 풀이 이 문제는 BFS를 이용해 푼다는 것을 알아야 한다. 정석적인 BFS를 이용해서 풀면 된다. 신경써야 하는 점은 범위를 헷갈리지 말아야 한다. M과 N을 헷갈려서 몇번을 틀렸는지 모르겠다...ㅎ....

https://www.acmicpc.net/problem/14941 14941번: 호기심 첫 줄에는 질문의 개수 n이 주어진다. 다음 줄 부터 차례대로 함수의 입력 a, b가 주어진다. (1 ≤ a ≤ b ≤ 10^5) 또한 남규는 호기심이 많기 때문에 매우 많은 질문을 한다. 따라서 질문의 수 n은 최대 10^5 개 이다. www.acmicpc.net 맨 처음 이 문제를 읽었을 땐, 엄청 쉬운 문제라고 생각했다. 하지만 풀다보니 시간초과로 도저히 풀리지 않았던 문제이다. 알고리즘 공부를 시작한 지 어느정도 시간이 지나고 나서 다시 이 문제를 보니, 두 가지 알고리즘 기법만 알면 쉽게 풀 수 있다는 걸 깨달았다. 내가 생각하는 이 문제의 골자는 시간복잡도를 줄이는 것이다. 그것을 해결하기 위한 방법은 소..

DFS 깊이 우선 순회 출발점 S에서 시작한다. 현재 노드를 Visited로 표시하고 인접한 노드들 중 Unvisited 노드가 존재하면 그 노드로 간다. 2번을 계속 반복한다. 만약 Unvisited 이웃 노드가 존재하지 않으면 직전 노드로 되돌아간다. 다시 2번을 반복한다. 시작노드 S로 돌아오고 더이상 갈 곳이 없으면 종료한다. DFS 수도코드 DFS(G, v) : Graph G와 Vertex v Visited[v]