모항이코딩한다

강의 초반부에서는 트리에 대한 기본적인 설명을 해주었다. 특히 적어둘 만한 것으로는 이진 트리에 관한 내용이 있었다. 학교 수업에서 배웠으나 잊고 있었던 내용인데, 이 기회에 확실히 기억해둬야겠다. 포화, 완전 이진 트리의 인덱스 포화 이진 트리와 완전 이진 트리는 그 정의로 인해 반드시 인덱스가 특정한 규칙을 띤다. 루트의 인덱스를 1로 하고 각 레벨의 왼쪽부터 차례대로 번호를 매기면 각 노드의 인덱스는 다음의 그림과 같이 된다. 이때 요소들은 반드시 다음의 규칙을 따른다. 부모의 인덱스를 i라 할 때, 왼쪽 자식의 인덱스는 2i 이고 오른쪽 자식의 인덱스는 2i+1 이다. 이진 트리의 순회법 이진 트리의 순회법에는 3가지가 있다. 전위 순회(Preorder) : 루트 - 왼쪽 서브트리 - 오른쪽 서브..

잊기 쉬운 용어 인접 리스트와 인접 행렬을 헷갈리지 말자 내가 자주 쓰는 그 방식은 인접 리스트임 인접 행렬은 다차원 배열을 사용하는 방식임 DFS DFS는 본래 스택의 성질을 이용한 탐색법이다. 나는 재귀로 구현해왔지만, 사실 이것도 스택의 원리와 똑같다. 재귀라는 것은 시스템 상에 스택이 쌓이고 빠지면서 실행되기 때문이다. 스택을 사용하여 DFS를 하는 방법은 다음과 같다. 일단 시작 정점의 번호를 스택에 넣는다. 그리고 스택의 top에 있는 정점에 대하여 다음을 반복한다. 스택 top에 있는 정점이 이미 방문한 정점이라면 그냥 빼내서 버리고, 아직 방문하지 않은 정점이라면 빼냄과 동시에 그 정점의 자식들을 스택에 차곡차곡 쌓는다. 이 과정을 반복하다 보면 스택이 완전히 비는 시점이 온다. 그때는 모..

이분탐색과 분할정복 모두 문제를 쪼개어 해결하는 방식임. 쪼갠다는 것은 무엇인가 문제의 크기가 크면 어렵다. 문제를 작은 부분 문제들로 나누어 풀면 쉬워진다. 문제를 쪼개고, 부분 문제들을 풀고, 그 결과를 병합한다. 문제를 쪼개는 것 & 결과를 병합하는 것의 비용이 크지 않다면 쪼개어 푸는 게 이득이다. 이분탐색의 간단한 설명 주어진 값들을 오름차순으로 정렬했다고 하자. 이 정렬된 리스트 내에서 특정 값 N의 위치를 이분탐색법으로 찾아보자. 중앙값을 콕 찝는다. 중앙값이 N보다 큰지 작은지 확인한다. 중앙값이 N보다 작다면 중앙값의 다음부터 리스트 끝까지의 범위에 N이 있다. 반대로 중앙값이 N보다 크다면 리스트의 처음부터 중앙값 이전까지의 범위에 N이 있다. 이러한 점검을 반복해나가면서 N이 있을 수..

완전탐색 Brute Force 방식을 가리킨다. 존재하는 모든 경우의 수를 다 탐색하는 풀이법이다. 완전탐색으로 풀 만한 문제는 어떤 문제? 가능한 모든 경우의 수가, 다 살펴볼 수 있을 정도로 적은 문제 하나의 경우마다 따져야 할 것이 분명한 문제 어떤 상태를 구성한 후에 그 상태가 특정 조건을 만족하는지 검토해야 하는 문제 사실 모든 알고리즘 문제는 완전탐색(노가다)으로 풀 수 있다. 시간복잡도와 공간복잡도가 문제일 뿐이다. 따라서, 알고리즘 문제를 풀 때 일단 완전탐색 식의 풀이법을 구상해본 뒤에 비벼볼 만 하다면 그대로 제출해보고 그렇지 않다면 완전탐색 식의 풀이법을 최적화함으로써 풀이법을 강구해볼 수 있다. 백트래킹 완전탐색처럼 해를 구하기 위한 경우들을 각각 다 탐색을 하는데, 그 과정에서 해..

선형 자료구조, 그 중에서도 스택, 큐, 덱에 대한 강의였다. 수업 첫머리에서는 동적 배열 자료구조가 무엇이며 어떻게 capacity를 할당하는지를 설명하고, 컴퓨터구조 수업에서 배울 수 있는 Temporal Locality와 Spatial Locality에 관하여 간단히 설명하였다. 세 가지 자료구조의 개념을 짚고, 관련된 문제를 풀어보는 강의였다. 정리할 내용은 많지 않다. 스택 선입후출, 후입선출 방식의 자료구조 큐 선입선출, 후입후출 방식의 자료구조 덱 Double-ended queue 배열의 앞쪽 끝과 뒤쪽 끝에서 모두 데이터를 넣고 꺼낼 수 있는 자료구조

그리디 알고리즘의 개념 부분적인 최적 전략을 반복적으로 취하는 알고리즘이다. 당장 눈앞에 놓인 것들 중 제일 이득인 선택지를 골라잡아가며 해결하는 방식도 그리디 알고리즘 중 하나이다. 어떤 문제가 그리디인가? 각각의 부분 문제의 최적해들이 전체 문제의 최적해의 일부인 문제. 그리디 문제를 풀 때 고려해야 하는 것 전체 문제를 어떻게 쪼개어 부분 문제들로 나눌 것인가? 각 부분 문제의 최적해를 구할 방법, 즉 부분 문제의 최적 전략은 무엇인가? 그 최적 전략 실행의 제약사항은 없는가? 있다면 어떻게 충족시킬 것인가? 부분 문제들에 대해 특정 순서로 최적 전략을 반복하면 정말로 전체 문제의 최적해가 나오는가? 일반적으로, 아무리 어려운 그리디 문제라도 대부분 위와 같은 사고의 과정이 어려울 뿐 복잡한 자료구..

동적 프로그래밍의 개념 전체 문제를 여러 개의 부분 문제로 나누어 풀 수 있을 때에 사용하는 문제풀이법이다. 예를 들어 팩토리얼을 구한다고 하자. 1! 부터 100!까지를 모두 구하라는 문제가 주어졌다. 그런데, 5!을 구하려고 할 때 $1 \times 2 \times 3 \times 4 \times 5$ 와 같이 네 번의 곱셈연산을 수행할 수도 있지만, 이미 4!의 값을 알고 있다면 4!$\times 5$ 와 같이 한 번의 곱셈연산으로 5!를 구할 수 있다. 빨간 글씨의 방법처럼 각 팩토리얼을 구하면 1!을 구하기 위해서 0번의 곱셈, 2!을 구하기 위해서 1번의 곱셈, 3!을 구하기 위해서 2번의 곱셈, ... 100!을 구하기 위해서 99번의 곱셈이 필요하다. 총 4950번의 연산이 필요하다. 파란..

1회차에는 시간 복잡도의 개념 등 기본적인 이야기가 많아 정리를 생략하였다. 2회차에서는 문자열 비교 시에 해싱을 사용하는 방법을 알려주었다. 아직까지 학교 수업에서는 해싱을 개념적으로 배우고 수학적인 예시를 풀어보았을 뿐, 코드에 적용한 적은 없었다. 실제로 구현해보니 굉장히 흥미로웠다.이번 강의에서는 비교적 쉽고 사용하기 편한 Polynimial Rolling Hash 기법을 배웠다. 새로 알게 된 표기문자열의 길이는 절대값기호로 표기. 문자열 해싱을 통한 비교란?문자열을 한 글자씩 일일이 비교하는 대신,문자열마다의 고유 값을 도출하여 그 값을 비교하는 방식이다. 서로 다른 문자열끼리 해시값이 겹치는 경우가 발생하면, 다중 해시를 사용하여 해결할 수 있다.(하나의 대상에게 다른 기준으로 만들어진 여러..