Daehyunii's Dev-blog

23.1 동적 프로그래밍 동적 프로그래밍이란 복잡한 문제를 간단한 하위 문제의 모음으로 분리해서 각 하위 문제들을 풀어서 그 답을 저장하고 활용하는 방식으로 문제를 해결하는 문제 해결 방식이다. 즉, 문제를 해결하는데 사용할 수 있는 접근 방법 중 하나이다. 대부분의 문제를 동적 프로그래밍으로 해결 할 수는 없지만, 동적 프로그래밍으로 해결할 수 있는 문제들에 대해 동적 프로그래밍으로 문제를 해결하는 경우 성능에 있어서 아주 큰 차이를 가져온다. 다시 말해 대부분의 문제에 적용할 수 있는 것은 아니지만 사용할 수 있는 경우에는 코드의 속도를 정말 많이 올릴 수 있다. 23.2 동적 프로그래밍 활용 가능 상황 동적 프로그래밍을 사용할 수 있는지를 확인하기 위해서는 두 가지 조건을 확인해야 한다. 1) 반복..

21.1 그래프 순회 그래프 순회란 말 그대로 모든 노드, 즉 그래프에 있는 모든 정점을 다 방문한다는 말이다. 트리의 경우에는 찾고자하는 노드에 접근하는 길은 루트에서 출발해서 도착하는 한 가지 방법밖에 없다. 하지만 트리와 다르게 그래프를 순회하는 경우에는 루트가 따로 없기 때문에 코드를 구현할 때는 시작점을 정해줘야 한다. 또한 그래프의 한 노드에서 다른 노드로 가는 방법은 유일한 하나의 방법만 존재한다는 보장이 없다. 22.2 깊이 우선 그래프 순회(DFS) 앞서 배운 이진 탐색 트리의 DFS와 동일한 개념이다. 하지만 그래프에서는 루트가 없기 때문에 하나의 정점을 지정하고 시작해야 한다. 그리고 그래프에서의 깊이 우선 그래프 순회는 한 인접점을 찾고 이어서 인접점을 또 찾는다는 의미이다. 다시 ..

20.1 그래프 그래프란 유한하고 변할 수 있는 꼭지점(노드)의 집합으로 구성된 데이터 구조이다. 이 꼭지점들의 집합에 순서가 없는 경우에는 무방향 그래프, 순서가 있는 경우에는 유방향 그래프라고 한다. 즉, 그래프는 노드와 노드들의 연결을 모은 것이다. 그러므로 트리도 그래프의 일종이다. 다만 트리는 몇 가지 규칙이 추가되어 부모와 자식노드로 구성되고 시작점인 루트가 존재하는 것이다. 하지만 그래프에는 부모 노드라는 것이 없고, 시작점도 없다. 다 동일한 노드일 뿐이다. 또한 그래프는 트리나 연결 리스트 같은 수준의 패턴이 없다. 자유로운 형식의 노드가 있고 그 사이에 연결만 있을 뿐이다. 또한 트리는 한 노드에서 다른 노드로 가는 경로가 딱 한 가지만 존재해야 하지만 그래프는 수 개의 경로가 존재할 ..

19.1 해시 테이블(해시 맵) 해시 테이블이란 키와 값을 쌍으로 저장하는 자료 구조를 말한다. 많은 프로그래밍 언어에 내장되어 있는 자료 구조이다. python은dictionaries, Java Script는 Object와 Maps, Java는 Go, Scala 그리고 Maps, Juby는 Hashes로 알려져 있다. 이 처럼 언어마다 해시 테이블이 내장되어 있고 해시 테이블은 추상적인 개념이기 때문에 여러 가지 방법으로 코딩할 수도 있다. 해시 테이블은 일반적인 배열과는 다르다. 배열은 인덱스를 가지지만 해시 테이블은 순서를 가지지 않는다. 해시 테이블이 좋은 이유는 새로운 값을 추가하거나 제거하는데 아주 빠르고 데이터 그 자체가 해시 테이블 방법에 따라 저장되는 것이 편한 경우가 많다. 19.2 해..

18.1 이진 힙 이진 힙은 이진 검색 트리와 마찬가지로 트리의 한 종류이다. 그러므로 트리에 적용되는 규칙들이 다 동일하게 적용되지만 추가적으로 적용되는 규칙들이 있다. 힙에도 여러가지 종류가 있지만 지금 알아 볼 내용은 힙의 한 종류인 이진 힙이다. 이진 힙은 다시 최소 힙과, 최대 힙으로 구분된다. 최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 자식 노드로 저장되는 왼쪽/오른쪽의 순서는 상관없이 한 레벨 아래에 있는 즉, 자식 노드보다는 항상 부모 노드가 크다.(오른쪽/왼쪽 순서는 중요하지 않고 데이터를 저장할 때 왼쪽부터 값이 저장된다.) 최소 이진 힙은 최대 이진 힙과 반대로 부모 노드는 항상 자식 노드보다 작은 값을 가진다. 자식 노드로 저장되는 왼쪽/오른쪽의 순서는 마..

17.1 트리 순회 트리 순회는 말 그대로 어떤 트리에서든지 사용할 수 있는 개념이다. 예를 들어 이진 탐색 트리든지, 그냥 이진 트리든지 그 외의 어떤 트리들에도 다 사용이 가능한 순회 방법이다. 즉 트리의 특성을 가지고 있다면 트리 순회를 할 수 있다. 트리를 순회하는 방법에는 많은 방법이 존재하고 대표적으로 너비 우선 탐색(Breadth First Search)과 깊이 우선 탐색(Deapth First Search)가 있다. 어떤 탐색 방법이든 모든 노드들을 순회하는 것은 동일하다. 17.2 너비 우선 탐색 너비 우선 탐색(Breadth First Search)은 트리의 같은 레벨에 있는 모든 노드를 거쳐가며 순회를 하는 방식이다. /* 트리) 10 / \ 6 15 / \ / \ 3 8 12 20 ..

16.1 트리란? 이진 검색 트리는 이진 트리의 한 종류이고, 이진 트리는 트리 자료 구조의 한 종류이다. 그렇다면 트리란 무엇일까? 트리란, 연결 리스트처럼 노드로 이루어진 데이터 구조이다. 하지만 연결 리스트와 다르게 부모-자식 관계를 가진다. 리스트는 선형 자료 구조이다. 말 그대로 하나의 줄로 이어져 있는 것처럼 보인다. 하지만 트리는 여러 갈래의 줄로 연결될 수 있기 때문에 비선형 자료 구조이다. 주의해야 할 점은 노드들이 자신보다 더 낮은 곳에 있지 않은 다른 노드를 가리키는 경우에는 트리 자료 구조가 아니다. 즉, 노드가 형제 노드를 가리키는 경우, 자식이 부모를 가리키는 경우에는 트리 자료 구조가 아니다. 트리에서는 모든 노드들이 루트노드에서 멀어지는 방식으로 연결된다. 루트는 하나이어야 ..

15.1 스택(Stack) 스택이란 후입선출 원칙을 따르는 데이터 구조를 일컫는 말이다. 즉, 나중에 들어온 데이터가 먼저 제거되는 방식의 자료 구조를 스택이라고 말한다. 설거지를 하기 위해 싱크대에 쌓인 그릇 중 가장위에 있는 그릇을 하나씩 설거지해 나간다고 생각하면 쉽다. 스택을 코딩하는 방법은 여러가지가 있고 연결 리스트를 사용해서 구현할 수도 있다. 즉, 스택이라는 개념은 후입선출 원칙을 지키는 자료 구조들을 말하는 추상적인 개념이다. 15.2 배열로 스택 구현하기 배열을 만들고 해당 배열에 데이터를 추가할 때 push() 메서드를 활용하고, 제거할 때 pop() 메서드만을 사용하거나 shift(), unshift() 메서드만을 사용한다면 배열을 스택으로 사용하는 방법이 된다. 후입선출 원칙을 지..