모항이코딩한다

완전탐색 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 기법을 배웠다. 새로 알게 된 표기문자열의 길이는 절대값기호로 표기. 문자열 해싱을 통한 비교란?문자열을 한 글자씩 일일이 비교하는 대신,문자열마다의 고유 값을 도출하여 그 값을 비교하는 방식이다. 서로 다른 문자열끼리 해시값이 겹치는 경우가 발생하면, 다중 해시를 사용하여 해결할 수 있다.(하나의 대상에게 다른 기준으로 만들어진 여러..