개발 블로그

알고리즘 책이나 강의를 보면 항상 초반에 한 가지 탐색 방법이 소개 됩니다. 이분탐색(binary search)라는 이름을 가지고 있는 이 알고리즘은 보통 책이나 강좌의 앞쪽에 소개 되는데다 그 개념 자체가 이해하기 어렵지 않기 때문에 배울 때는 큰 어려움이 없지만, 의외로 코딩테스트의 문제로 만나게 되면 문제를 쉽게 풀 수 없게 만드는 복병이 되기도 합니다. 오늘은 이 이분 탐색에 대해 간단히 알아보고 실제 코딩 테스트에서 어떻게 활용할 수 있는지에 대해 생각해 보도록 하겠습니다. 사실 이분탐색의 개념은 매우 간단하고 직관적입니다. 이를 설명하기 위해 스무고개 놀이를 한 번 해 보도록 하겠습니다. 1부터 100사이에 있는 숫자를 하나 생각하고 가능한 적은 횟수의 추측으로 이 숫자를 알아내는 방법을 생각..

정렬(Sort)은 알고리즘 과목에서 항상 단골로 출제되는 영역입니다. 오늘은 그 중에서 힙 정렬(Heapsort)를 알아보도록 하겠습니다. 우선 이 정렬 알고리즘을 이해하기 위해서는 힙(heap)이라는 독특한 자료구조에 대해 먼저 이해 해야 합니다. 그런데 이 heap을 알려면 우선순위큐(Priority Queue)를 또 먼저 알아야 합니다. 그러면 또 그냥 큐(Queue)가 뭔지도 알아야겠죠. 점점 일이 복잡해 지니까 아주 단순하게 설명하도록 하겠습니다. 각각의 개념에 대해 부족한 설명은 추후에 (가능하다면)포스트 하도록 하겠습니다. 큐(Queue)는 컴퓨터의 기본적인 자료구조의 일종입니다. 먼저 삽입된 데이터가 먼저 나오는 FIFO(First In First Out)구조로 되어 있는데 화장실 앞에 줄..

한 며칠 고민하다가 답을 못 구할 것 같아서 문제 제목으로 검색했더니 KOI 초등부 문제였다. 초등부 문제도 못풀었다는 생각을 하니까 참 자괴감도 들고 내가 잘 하고 있는건지 자신감도 좀 떨어지는 것 같다. 이정도 수준의 동적계획법 문제는 초등학생들도 푸는구나... 문제는 이곳에서 볼 수 있다. 결국 동적계획법은 격자를 만들고 그 격자를 정의 해야 한다. 결국 이 점화식을 생각해 낼 수 있느냐 없느냐가 문제를 풀 수 있느냐 없느냐를 나누게 된다. 기본적으로 동적계획법 문제가 나오면 (일단 처음에는 그게 동적 계획법으로 푸는 문제인지 모르니까) 완전탐색 방법으로 문제를 생각해 본 후 -> 이미 계산했던 답을 재활용 할 수 있는지 생각해 본다. 재활용이 가능하다면 동적계획법을 활용할 수 있다. 이 문제에서도..

비전공 개발자로 CS공부를 하면서 가장 어려운 것은 역시 알고리즘이다. 나에게 알고리즘 문제는 마치 아이큐 테스트 같이 느껴진다. 공부를 해도 발전이 느껴지지 않는다. 그럼에도 대부분의 기업에서 알고리즘 문제로 코딩테스트를 보기 때문에 특히 좋은 회사일 수록 어려운 문제를 내는 경향이 뚜렷하기에 손에서 놓을 수가 없다. 이번에 푼 문제는 프로그래머스에서 제공하는 문제다. 혹시 저작권 문제가 있을지도 몰라 문제의 내용은 링크로 대체한다. 이번 풀었다고는 했지만 이 문제를 거의 2주일 동안 고민했다. 물론 매일매일 이어지는 야근 속에 깊이 고민할 시간이 대체로 부족하기는 했지만 그럼에도 2주 동안 답을 찾지 못하고 있었다. 그러다 오늘 아침 조금 일찍 출근해 문제를 풀다보니 실마리가 보였다. 순식간에 답을 ..

문제 프로그래머스(Programmers.co.kr) 에서 제공하는 문제입니다. 저작권 문제가 생길 수 있기 때문에 문제를 옮기지는 않겠습니다. 문제를 보고싶으신 분은 https://programmers.co.kr/learn/courses/30/lessons/42895 으로 접속하시면 됩니다. 풀이 사용하는 N 세 개를 사용해서 숫자를 만들 때를 생각해 봅시다. 이 때 숫자를 만드는 방법은 N이 두 개일때 만들어진 숫자와 N 하나를 연산하는 것입니다. N 네 개를 사용해서 숫자를 만 들면 N이 두개일 때 만들어진 숫자들은 서로 연산하거나 N이 세 개 일 때 만들어진 숫자와 N 하나를 연산하는 것입니다. 여기까지 생각하게 되면 이 문제가 전형적인 동적계획법 문제임을 알 수 있습니다. 코드 1234567891..