자료구조란 데이터를 효율적으로 저장, 탐색, 추가, 삭제, 수정을 하기 위한 특별한 틀 또는 그것들을 배우는 학문을 의미한다. 자료구조란 학문이 굉장히 고전적이고 이렇다할 참신한 기법이 더 이상 나오기가 힘들지만 컴퓨터과학하면 빼먹을 수 없는 학문이다. 필자가 처음 자료구조를 배웠을 때, 자료구조만큼은 이 책이 바이블이라면서 교수님이 추천해주셨다. 바로 아래 이미지의 책이다. 굉장히 유명한 책이라서 한국어 번역판이 있는지도 모르고 그냥 원서로 사버렸다... 마지막으로 자료구조에 관한 문답 하나를 보이고 끝내겠다. Q: Why are data structures and algorithms so important in computer science? (왜 자료구조와 알고리즘이 컴퓨터과학에서 중요한가요?) A..

1. Introduction 순열이란, 어떤 데이터들에 대해서 해당 데이터로 줄을 세우는 것을 말한다. 예를 들어, (1,2,3) 에 대한 순열은 다음과 같다. (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) 필자는 알고리즘에서 순열을 처음 배울 때 재귀로 푼다는 말을 듣고도 틀렸고, 나중에 시간이 한참지나서 시험칠 때 다시 공부했을 때도 틀렸고, 지금 포스팅할때도 틀렸다... 2. Approach 앞서 설명했듯, 순열은 재귀로 푼다. 다만 그 과정이 쉽게 머리에 박히지 않아서 그림을 통한 설명이 필요하다. 아래 그림은 순열을 구하는 과정을 시각화한 것이다. 사전순으로 얻는 과정을 (즉, 결과가 뒤에서 부터 swap됨) 앞에서 부터 순서대로 고정한다는 개념으로 설명하..

1. Introduction 코딩을 하다 보면 꼭 전체를 정렬할 필요는 없는데 n번째로 큰 원소, 정확히는 n째 인덱스의 값을 얻고 싶을 때가 있다. 예를 들어, 한번 뽑고 나면 다시 섞여버리는 리스트라던가... 필자는 백준에서 문제를 풀다가 어떤 문제에서 존재를 알게되었는데, 처음에는 단순히 성능 "좋은 소팅 알고리즘을 요구하는 문제인가 보다.." 하고 생각했다. 하지만 계속 틀려서 다른 사람들의 답을 찾아보니 $O(n)$ 수준의 시간복잡도를 요구하는 문제였다. 그래서 이번엔 "선택 정렬에서 k까지만 정렬하고 바로 출력하자" 하고 제출하니 또 fail. 생각해보니 이렇게 접근하면 k가 적을 때나 빠르지, 후반으로 갈수록 배열의 대부분을 정렬하니 걍 $O(n^2)$이나 다름 없었다. 그런데 더 찾아보니 ..

1. Uniform binary search 이진탐색의 mid는 현재 값에서 항상 일정한 값 만큼만 차이나게 된다. 즉 현재 a[mid]의 값을 검사했다면 다음에 검사할 값은 a[mid + k] or a[mid - k] 이다. 따라서 매 루틴마다 다음 mid까지의 거리 k를 미리 look-up table에 저장해둔다. 이 결과를 통해 mid를 정하는 산술연산이 불필요하게 된다. 같은 배열에 대해 많은 쿼리를 처리해야하는 환경에서 빠르게 동작한다. 2. Exponential binary search 이 방법은 target의 범위를 고정하는 방법이다. 시작부터 bound의 범위를 2배로 늘려가며 target의 상한을 찾는다. 상한을 찾았으면 target의 범위는 [bound / 2, bound+1] 사이에 ..

풍차공격은 룩과 비숍을 이용하여 대량의 이득을 챙기는 전술이다. 디스커버드 체크(Discovered Check)를 기반으로 사용된다. 다음 그림에서 백은 룩을 g7에 배치하여 체크를 부른다. 흑은 킹을 h8로 움직여 체크를 피한다. 룩은 f7의 폰을 다시 먹으면서 비숍으로 디스커버드 체크. 킹이 다시 g8로 돌아온다. 백도 룩을 다시 g7으로 되돌려서 체크. 흑은 이때부터 뭔가 잘못됐음을 느낀다. 흑이 피하면 이번엔 비숍을 잡으면서 디스커버드 체크. 킹이 돌아오고 룩도 돌아오고 체크. 흑이 피하면 다시 비숍을 잡고.... 이렇게 백은 h열의 폰을 제외한 7랭크의 모든 기물을 잃게 됐다. 잘 나오지는 않지만 사용하기만 하면 엄청난 이득을 가져올 수 있다.

디코이는 내가 전술적인 이득을 얻도록 하기 위해 상대 기물을 유인하는 것이다. 다음 이미지에서 흑의 나이트는 f4로 이동하여 퀸과 룩에 대해 포크를 걸어 이득을 취할 수 있지만 디코이를 사용하면 더 큰 이득을 볼 수 있다. 먼저 흑은 퀸을 g2에 배치하여 룩을 잡는으면서 동시에 체크를 넣는다. 백은 선택의 여지가 없다. 킹으로 퀸을 잡는다. 이때 나이트가 f4로 이동하여 킹과 퀸을 포크. 퀸을 잡는다. 원래 같으면 나이트가 포크로 룩을 따내고 킹에게 잡혀서 5점(룩)을 얻고 3점(나이트)을 잃어 2점의 이득을 보지만, 디코이를 사용한 전술에서는 퀸을 교환하고 상대 룩을 잡았으므로 5점의 이득을 얻는다.

디플렉션이란 원하는 목적을 이루기 위해, 방어하고 있는 상대 말을 쫒아내는 것이다. 다음 이미지에서 흑은 나이트를 d5에 배치해서 상대 킹과 퀸에 대해 포크를 걸 수 있다. 하지만 정작 중요한 d5를 백의 비숍이 막고 있다. 즉, 흑의 입장에서는 저 비숍만 갖다 치워버리면 만사형통이다. 흑은 비숍을 d7에 배치하여 백의 비숍이 c6를 포기하도록 유지한다. 흑의 비숍은 잡힐 수도 있지만, 이는 나중에 퀸을 따내기 위한 작은 희생(Sacrifice)이다. 다음 이미지는 디플랙션의 또 다른 경우이다. 흑의 퀸은 백의 룩을 잡고 싶지만 또다른 룩의 보호를 받고 있어 불가능하다. 하지만 흑은 나이트를 d2에 배치해서 룩의 보호를 끊는다. 백이 비숍으로 나이트를 잡으면 백은 원래 목표대로 퀸으로 룩을 잡으면 된다...

디스커버드 어택은 기물이 다른 곳으로 비킴으로서, 다른 기물이 공격을 하는 전술이다. 다음 이미지에서 흑은 나이트를 c4에 배치하는 것으로 디스커버드 어택을 걸었다. 백은 체크를 당했으므로 비숍으로 흑의 퀸을 잡을 수 없다. 디스커버드 어택으로 상대킹을 공격하는 것을 디스커버드 체크라고 따로 구분하기도 한다. 디스커버드 어택에 속하는 전술중에 더블 어택 / 더블 체크라는 것이 있다. 다음 이미지에서 흑은 룩을 f4에 배치하는 것으로 디스커버드 체크를 걸고 있다. 디스커버드 어택이므로 당연히 백은 룩으로 흑의 퀸을 잡을 수 없다. 또한 룩으로 퀸의 경로를 가로막는 것도 할 수 없다. 흑의 룩의 체크도 남아 있기 때문이다. 이처럼 두개의 기물로 동시에 적의 기물을 공격하는 것을 더블 어택이라고 하고 이렇게 ..