개발 블로그 개발 블로그

문자열은 웹개발에서 가장 중요한 요소 중 하나이고 코딩테스트에서 단골로 출제되는 알고리즘이 Dynamic Programming(동적계획법)이기 때문에 가끔씩 DP를 사용하는 문자열 문제가 출제될 때가 있습니다. 어떤 문제든지 패턴을 파악하고 있으면 조금 더 쉽게 풀 수 있습니다. 오늘은 DP를 사용하면 문자열 문제 몇 개를 살펴보도록 하겠습니다. 가장 많이 출제되는 유형의 문제는 두 문자열에서 공통되는 문자의 개수를 찾아내거나 공통되는 문자열의 길이를 구하는 종류의 문제입니다. 예를 들어 "XMJYAUZ”, “MZJAWXU” 두 문자열에서 공통된 글자의 수를 찾아내려고 할 때, 위와 같은 테이블을 만들 수 있을 것입니다. 표에서 인덱스는 각각 하나의 문자를 나타내고 만약 해당하는 인덱스의 문자열이 같은 ..

마르코프 체인은 이미 자연어 처리와 관련된 분야에서는 한물간(?) 취급을 받고 있는 알고리즘인 것 같습니다. 그러나 관련 분야 전문가가 아닌 저와 같은 사람이 코딩을 통해 문장을 생성하는 가장 직관적이고 쉬운 알고리즘이라는 생각이 듭니다. 위 그림은 마르코프 체인을 설명할 때 가장 많이 볼 수 있는 그림인데 알파벳은 상태를, 화살표는 상태의 시간적 흐름을 숫자는 상태 전이가 일어날 확률을 보여주고 있습니다. 쉽게 말해 A 에서 B 가 될 확률은 0.5, 그 반대는 0.8 이라는 것이죠. 이것을 통해서 무엇을 할 수 있을까요? 어떤 상태의 패턴을 추론할 수 있습니다. 가령 날씨를 예로 들자면 '흐림 > 비 > 맑음 > 흐림 > 비 > 맑음' 과 같은 패턴을 가지고 있다면 이 데이터를 통해 각각의 날씨에서 ..

알고리즘 책이나 강의를 보면 항상 초반에 한 가지 탐색 방법이 소개 됩니다. 이분탐색(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..

문제 국경을 지나는 것은 언제나 귀찮고 힘든 일입니다. 여행자들은 도착지에 도착하기 위해 통과하는 국경을 최소화 시키길 원합니다. 당신은 여행자들을 도와 국경선을 최소한으로 통과하는 방법을 찾고 싶습니다. 다행히 당신이 도와줘야 하는 여행자가 사는 세상은 모든 나라의 국경선이 정확한 원이고 서로 겹치거나 교차하지 않는다고 합니다. 각 국가의 좌표 배열 X, Y 와 반지름 배열 R 그리고 시작 좌표인 x1, y1 종료 지점 좌표인 x2, y2가 주어진다고 할 때 최소한으로 통과해야 하는 국경선의 수를 리턴하는 함수를 작성하십시오. 입출력 예시 입력 1) int[] X = { 0, -6, 6 }; int[] Y = { 0, 1, 2 }; int[] R = { 2, 2, 2 }; int x1 = -5; int..