-내 생각 완전 탐색(브루트 포스) 알고리즘 분류에 있는 문제이다. 브루트 포스 알고리즘은 모든 경우의 수를 탐색하는 알고리즘이므로 문제에서 3장의 카드를 뽑는다 했으므로, 3장의 카드에 들어올 수 있는 모든 경우의 수를 따져보고자 했다. 이때, 3장의 카드는 5, 6, 7이나 6, 5, 7 이나 어차피 최종적으로 모두 합친 값으로 m과 비교해야하기 때문에 탐색을 위한 반복문 3개 중 두 번째와 세 번째 반복문은 항상 앞의 반복문보다 +1 된 상태로 시작하게 한다. 또한 끝나는 부분은 세 장은 세 자리의 숫자를 의미하므로 첫 번째 반복문은 2번째, 3번째 자리의 숫자만큼 공간이 있어야 하므로 끝까지 비교하지 않고 끝에서 -2 한 인덱스 까지만 비교하게 하며 2번째 반복문 역시 마찬가지다. 문제에 대한 해..

-다이나믹 프로그래밍이란? 솔직히 여러 블로그나 강의를 봤을 때 드는 예시가 대표적으로 피보나치 수열이라 개념의 이해자체는 쉬웠다. 분할 정복 방식과는 다른 형태로 어떤 큰 문제가 작은 문제로 나눠질 때 또 이 큰 문제가 더 큰 문제의 작은 문제일 때, 동시에 해당 값들에 변화가 없을 때 사용한다고 한다. 즉 피보나치 수열에서 f(3) = f(2) + f(1) 이고, f(4) = f(3) + f(2)이므로 f(3)에서의 f(2)와 f(4)에서의 f(2)는 값이 변하지 않는 중복되는 연산이다. 이러한 중복 연산들을 메모이제이션 기법으로 별도로 기록해두고 (캐시같은 개념) 필요할 때 마다 가져다 사용하면 되는 것이다. 즉, f(3)의 결과를 최초로 실행할 때 저장해 둔 후, f(4)를 구할 때 f(3)을 구..

-이진트리란? 트리의 한 종류로써 대표적인 비선형 자료구조의 형태로 1개의 데이터에 대해 0, 1, 2개의 자식 노드를 가지는 트리를 말한다. 이진트리는 일반적으로 탐색을 할 때 많이 사용하는데 그 이유는 특정 데이터를 탐색하고자 할 때 좌, 우로 나뉘어서 탐색하기 때문에 한쪽을 일방적으로 제외할 수 있어 빠른 탐색속도를 가지게 된다. 이진트리의 구현은 일반적으로 배열과 노드를 이용해 구현이 가능하지만, 완전 이진트리를 제외하고는 배열을 사용할 때 많은 메모리 낭비가 발생하기 때문에 노드로 구현하는 것이 좋다. -이진트리의 순회방식 이진트리의 순회방식으로는 3가지가 존재하는데 1)전위순회, 2)중위순회, 3)후위순회이다. 이는 탐색하는 순서에 따라 구분되며 D를 현재의 노드, L을 왼쪽 자식노드,R을 오..

-내 생각 알고리즘 초보자로서 그리디 알고리즘에 진입하고 나서부터 무언가 굉장히 헷갈리고 자신감이 사라졌다.. 문제를 이해하는데 많은 시간이 걸리지 않았지만, 어떻게 해결해야 할지 너무 막막해서 곧장 다른 분들의 블로그를 통해 문제를 정확하게 이해할 수 있었다. 똑같은 크기의 2차원 배열 A, B가 일치할 때까지의 변환 연산의 횟수를 구하는 것이 핵심인데 변환 연산은 3X3의 고정된 크기로만 변환이 가능하다. 처음에 다른 블로거 분들의 설명을 봤을 때는 '왜 (0,0)부터 뒤집기 시작하지?' 생각했는데, 생각해보면 3X3으로 고정되어있기 때문에 뒤집은 똑같은 3X3의 공간을 다시 뒤집는 바보 같은 짓(정말 똑같은 공간, 걸치는 공간은 몇 번이든 뒤집어질 수 있다.)을 제외하면 결국에는 각 원소가 뒤집어 ..

- 크루스 칼(Kruskal) 알고리즘이란? 크루스 칼 알고리즘이란, 각 정점을 최소 비용으로 연결시키는 최소 비용 신장 트리를 만드는 대표적인 알고리즘으로 일반적인 그래프에서 각 정점을 연결하는 간선에 비용을 추가해 최소 비용으로 모든 정점을 순환하는 그래프로 만드는 것이다. 크루스칼 알고리즘으로 그래프를 구현할 때 비용은 최소가 되어야 하기 때문에 두 정점과 그 간선에 소모되는 비용을 하나의 클래스로 정의하여 비용을 기준으로 오름차순 정렬을 한 후 가장 적은 비용부터 차례대로 정점을 연결해 나가면 된다. 또한 각 정점에서 사이클이 발생하지 않고, 간선의 수가 정점의 수 -1 개가 연결될 때까지 진행한다. 정점의 수 -1 개의 간선이 연결되면 모든 정점이 연결될 수 있기 때문이다. 이때 사이클의 발생여..

-Union Find 알고리즘이란? 서로소 집합 알고리즘과 같은 개념으로 여러 개의 노드가 존재하는 그래프에서 두 노드가 연결되어있는지 판별하는 알고리즘이다. 구현에 필요한 자료구조로는 1) 모든 정점들의 부모 정점을 표현하기 위한 배열이 필요하다. 다음과 같이 6개의 독립적인 노드가 존재한다고 할 때 배열을 이용해서 원소에 해당 노드의 부모 노드를 표시하게 된다. 현재는 모두 독립된 노드이기 때문에 자기 자신을 부모로 삼는다고 할 수 있다. 1 2 3 4 5 6 1 2 3 4 5 6 이와 같은 상태에서 만약 1번 정점과 2번 정점이 연결을 수행하게 되면 두 정점을 합치는 Union작업이 수행되게 되는데, 이 과정을 거치고 나면 아래와 같이 2번 정점의 원소를 부모 정점인 1로 바꿔주게 된다. 이 과정에..

-깊이 우선 탐색(DFS)이란? 그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. 그중 깊이 우선 탐색은 아래와 같은 순서를 따른다. 시작 정점(V)을 방문한다. V에 인접한 정점들 중 방문하지 않은 정점을 방문하며 스택(Stack)에 삽입한다. 인접한 정점이 없는 정점까지 2번을 반복한다. 이후 인접한 정점이 없는 경우 다시 스택에서 pop() 후 2~3번을 반복한다. 즉 깊이 우선 탐색의 경우에는 인접한 정점이 없는 정점에 도달할 때까지 인접한 정점을 반복해서 방문하며 Stack에 넣는 작업을 한다. 깊이 우선..

-너비 우선 탐색(BFS)란? 그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. (또한 너비 우선 탐색은 두 정점 사이의 최단 거리를 구하거나 임의의 경로를 구할 때 사용한다고 하는데, 필자도 현재까지는 단순한 구현과 개념의 이해정도 수준에 그치기 때문에 후에 추가적으로 작성할 예정이다.) 그중 너비 우선 탐색은 아래와 같은 순서를 따른다. 시작 정점(V)을 방문한다. V에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하며 큐(Queue)에 삽입한다. 인접한 정점을 모두 방문했다면, 큐에 삽입했던 정점을 반환..