願いを流れ星に

알고리즘의 이론을 배웠다면 바로 이를 응용한 문제를 풀면서 응용하고 복습하는 것이 좋다. 이를 위해 다양한 알고리즘 트레이닝 사이트가 존재한다.

대부분의 알고리즘 트레이닝 사이트에는 랭킹 시스템이 있어 문제를 더 열심히, 많이 풀고자 하는 의욕도 생길 수 있다. 이 포스트에서는 몇몇 알고리즘 트레이닝 사이트들을 소개하고자 한다. 

1. dovelet 더블릿

주소는 www.dovelet.com 이고 흔히 30계단이라고도 부르는 사이트이다. 각 계단에는 주제가 있고 그 주제에 관한 문제만 모아 놓은 사이트이다. 예를 들어 1계단=scanf, print, 2계단=if 3계단=for 이런 식으로 주제별로 문제가 모아져있다.. 대부분의 사이트는 주제, 난이도에 상관없이 문제가 뒤죽박죽 나열되있어 초심자가 처음 접하는 알고리즘 트레이닝 사이트로 적극추천한다. 다만 3계단까지 무료로 제공되고 4계단에서 30계단까지는 유료결제를 해야한다. 1달 3천원, 6달 15000원 평생 30000원으로 결제할 수 있고 특이한 점은 랭킹에서 30위안에 한번이라도 들어가게 되면 평생회원으로 올려준다. 글 쓰는 현재, 30위조건은 557문제이고 본인은 31~100위의 순위에서 3천원씩 결제하며 평생회원으로 등급업을 노리고있다. 또 30계단외에 옥상이라 불리는 곳이 있는데 이 곳에는 문제가 타사이트처럼 주제에 상관없이 다양하게 나열되있고 유료결제 없이도 문제풀이가 가능하다.

2. 백준 온라인 저지

주소는 acmicpc.net이다. 주소인 acm icpc는 전세계단위로 열리는 대학생 프로그래밍 대회인데 지도교수 1명- 대학생 3명의 팀으로 출전가능하다. 사이트의 운영자이신 최백준씨의 이름을 딴 트레이닝 사이트이고 모든 문제를 무료로 풀 수 있다. 다만 난이도, 주제에 상관없이 문제가 정리되어 있어 처음 사이트를 방문하는 사람들은 풀만한 문제를 찾지 못하는 경우도 있더라. 사이트의 문제들을 '문제집' 의 형태로 묶어서 정리해놓을 수 있는데 이 문제집 메뉴에 가면 초급자를 위한 문제모음이 여러 종류 존재한다. 또한, 랭킹 시스템에서 오늘, 이번주, 이번달, 올해 등으로 여러 종류의 랭킹을 볼 수 있고 학교 랭킹 또한 존재해 문제를 풀 의욕을 더 커지게 한다.

3. koistudy

주소는 koistudy.net이다. 현직 고등학교 정보 선생님이 운영하시는 사이트이다.

이름에서 알 수 있듯이 koi, 즉 한국 정보올림피아드의 공부를 위한 사이트이다. 경기과학고 학생들의 과제, 교내대회 등의 목적으로도 사용되고 있는 듯하다. 기초문제가 잘 정리되어 있다.

4. 알고스팟

주소는 algospot.com이다. 꽤 문제들이 어렵다. 몇년전부터 이 알고스팟에서 매년 오프라인 대회도 개최하고 있다. 운영진들이 매우 실력있고 유명한 것 같다. 실제로 여기저기 대회를 참여하다보면 대부분 참가자가 비슷하다. 즉 한 대회에서 본 팀들을 다른 대회에서도 계속 보게 된다. 여러 대회를 참여하면서 운영진들을 몇 번 봤는데 정말 잘하시는 것 같다.

5.pku

주소는 poj.org이다. 여태까지 소개한 사이트들이 국내의 저지사이트였다면 이 사이트는 해외 사이트이다. 북경대 온라인 저지사이트인데 중국어로 된 문제와 영어로 된 문제가 섞여있다. 어차피 국내대회도 영어로 출제되는 경우도 많으므로 연습삼아 풀어보자. 

그 밖에도 usaco 라던지 유명한 해외 저지사이트들도 많지만 생략한다.

원래 예정은 웹이나 안드로이드 먼저 포스팅이었지만 다음주의 면접을 위해 알고리즘부터 한번 쭉 훑으며 복습하고자 한다.

알고리즘은 흔히, '어떤 문제를 해결하기위해 명확히 정의된 유한개의 규칙과 절차의 모임' 을 의미한다. 즉 문제를 푸는 방법이다. 이에 따라 알고리즘의 공부에는 보통 자료구조의 학습이 선행되어야 한다. 

대학에 따라 과목도 자료구조론/알고리즘 으로 나눠져있기도 하지만 자료구조와 알고리즘 과 같이 묶어서 가르치는 과목도 있더라.

자료구조에는 리스트, 스택, 큐, 트리, 그래프 등이 있다.

리스트는 목록형 자료구조라 하는데 말그대로 일렬로 자료들을 이어놓은 구조이다. 그래서 보통 리스트 중에도 링크드 리스트(Linked List)를 흔히 사용한다. C에서는 포인터를 이용해 노드라 불리는 자료덩어리들을 연결시켜 구현한다. 노드는 보통 구조체 형태로 만들어서 한 노드에 여러 자료들을 저장할 수 있다.

스택은 한쪽이 막힌 관으로 표현할 수 있는 자료구조이다. 한쪽이 막혔기 때문에 데이터를 일렬로 넣었을 때, 가장 먼저 들어간 데이터가 가장 늦게 나올 수 있다. 이를 Last In First Out, LIFO라고 표현한다. 스택에 데이터를 삽입하는것을 Push, 가장 위의 데이터를 제거하는것을 Pop이라 부른다. C++에서 <Algorithm> 헤더파일에도 구현이 되어있지만 배열을 이용해 손쉽게 구현할 수 있기 때문에 나는 배열을 주로 이용하는 편이다. 스택의 데이터를 저장할 배열과 배열안에 들어있는 데이터의 갯수를 나타내는 int형 변수 하나면 스택을 표현할 수 있다. 

큐는 반대로 양쪽이 모두 뚫힌 관으로 표현할 수 있다. 즉 양 쪽 다 뚫혀있기 때문에 넣은 순서대로 그대로 나오게 된다. First In First Out ,FIFO라고 표현한다. 큐에 데이터를 넣는 것을 인큐(enqueue), 빼는 것을 디큐(dequeue)라 부른다. 이 역시 <Algorith> 헤더파일에 구현되어있는데 이 역시 배열로 구현할 수 있다. 하지만 스택을 구현하는 것 처럼 배열로 구현하면 디큐할때마다 배열의 데이터를 한칸씩 앞으로 옮기거나 아니면 아예 큐의 첫 구간을 나타내는 변수를 하나 더 만들어줘야한다. 스택보다 귀찮기 때문에 나는 알고리즘 헤더파일에 구현된 큐를 사용하는 편이다.

트리는 수학 시간에 배우는 수형도 처럼 생긴 자료구조이다. tree라는 이름 자체가 나무처럼 생겼다해서 붙여진 이름인데 실제로 사용할 땐 위아래로 뒤집어서 사용한다(?). 즉 실제로 트리 구조를 보면 나무뿌리처럼 위가 적고 아래로 갈수록 옆으로 퍼진다. 트리의 용어는 부모노드, 자식노드나 뿌리(루트), 리프,가지, 차수 등 아주 많은데 나중에 다시 설명하도록 한다. 주로 한 노드에 최대 2개까지의 자식노드를 가지는 이진트리를 이용한다. 이 트리는 정렬, 탐색, 압축 등 여러 분야에서 자주 사용된다. 

그래프는 노드에 해당하는 정점(vertex)와 이를 잇는 간선(edge)로 이루어진 자료구조이다. 이 정의에 의하면 트리도 그래프의 일종이라 할 수 있다. 그래프에 대한 세부 내용은 알고리즘에서 다시 나오기 때문에 자료구조로서의 그래프의 설명은 이정도 까지 하겠다.

위와 같이 자료구조의 학습이 끝나면 알고리즘을 배우게 된다. 알고리즘의 종류는 매우 다양한데 정렬, 탐색, 문자열, 그래프 등 이외에 많은 알고리즘이 있다.

각 알고리즘은 한 포스트에 다루기에 너무 광대해서 추후에 따로 정리할 것이다.

또한 알고리즘의 설계 기법? 이라 부를 수 있는 것들이 있다.

분할 정복은 어떠한 문제를 작은 범위의 문제로 나누어 해결하는 방법이다.

동적 계획법은 보통 영어로 DP, Dynamic Programming 이라고도 자주 부른다. 단계적으로 문제를 풀어나가는, 즉 문제의 점화식을 구해서 구현하는 방법이다.

탐욕 알고리즘, 흔히 그리디(Greedy)라고 부르는 알고리즘은 무작정 바로 보이는 상황만을 고려해서 답을 구하는 방법이다. 

백트래킹은 여러 후보 해들을 탐색하면서 잘못 되면 재귀등을 이용해 다시 전으로 가고 다른 해를 탐색하는 식으로 문제를 해결하는 방법이다. 미로찾기를 생각하면 이해하기 쉽다.

다음 알고리즘 포스팅은 내가 제일 약한 그래프 복습을 위해 그래프에 관한 내용이 될 것같다.

새로만든 블로그의 첫 글이다. 

매번 꾸준히 포스팅하겠다고 다짐하면서 실패했는데 이번에도 솔직히 계속 할 수 있을지는 모르겠다. 

매번 보여지기 위한 포스팅 때문에 말투도 뒤죽박죽이고 했는데 이번에는 방문자도 안 바라고 일기장같은 형태로 운영하고자 한다. 

잡담은 네이버블로그에서도 충분히 하기 때문에 이번 블로그 컨셉은 전공공부하면서 배우는 지식을 정리하는 곳? 지금은 쓰고있는 글 하나밖에 없지만 앞으로 공부하면서 점점 블로그도 커지겠지. 

아직 블로그이름, 메뉴등도 미정이라 천천히 꾸밀예정.

 지금 공부하고 있는 분야는 안드로이드/ 웹프로그래밍이라 당분간은 안드로이드나 html,css 등의 내용이 포스팅 될 것 같다.

아무래도 이번엔 웹 쪽도 다루다보니 처음엔 티스토리에서 제공하는 스킨 쓰더라도 나중엔 직접 코딩해서 만들지도.. ㅋ..