코딩개발로 물장구치는 개발자

안녕하세요 Dibrary입니다. 이번에는 제가 개인적으로 어려워해서 푸는데 시간이 꽤나 걸린 동적프로그래밍 문제를 풀어보겠습니다. 지금도 까딱하면 동적프로그래밍 '감'을 잃을거 같아서 조심스럽네요... 문제는 아래와 같습니다. 처음에 이 문제를 보자마자 어디서 '생각'이 멈췄냐면 1을 쓰는 것과 2를 쓰는 것의 '순간'을 어떻게 알지? 2 외에 3이 있다다는 것을 어떻게 알지? 이런 생각 때문에 문제를 못 풀었습니다... 그래서 그냥 하염없이 갯수를 세다가 문득 규칙성이 보이길래 좀 더 해봤습니다. 제가 이렇게 '규칙성을 찾아서 문제를 풀어야 한다'는 개념을 알게 된 문제는 아래 문제였습니다. 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출..

안녕하세요 Dibrary입니다. 이번에는 이진검색트리에서 '전위순회'한 값 순서가 주어질 때, 이 값을 '후위순회'한 값 순서로 바꾸는 문제입니다. 재귀를 떠올리지 못해서 도대체 어떻게 해야 하나 아주 알머리를 고민했던 문제입니다... 문제는 아래와 같습니다. 제일 먼저 든 생각은 '전위 순회는 어떻게 하는 거였더라~?' 입니다. 전위순회는 루트 먼저 가고 좌, 우 를 방문합니다. 이게 무슨말일까요? 위 문제에서 주어진 예시를 통해 확인해보겠습니다. 먼저 이렇게 3개만 놓고 볼 때, 루트는 50이고, 왼쪽을 먼저 간다고 했으니 30을 방문하겠네요. 다음으로 30을 루트로 놓고 볼 때, 왼쪽 24를 먼저 방문하겠네요. 24를 루트로 놓고 볼 때, 5를 방문하고, 5는 더이상 자식노드가 없죠. 그럴 때 오른..

안녕하세요 Dibrary 입니다. 이번에는 사전형을 써야만 풀리는 문제를 정리해보고자 합니다. 먼저 제가 몇 번을 틀린 방식은 아래와 같습니다. 문제에서 주어진 500000이라는 횟수의 비교를 너무 가벼이 생각했음. list가지고 해결이 안 되길래, set을 이용했음. 그럼에도 안 됨. 우선 500000이라는 횟수는 생각보다 간단하네~ 라고 착각했던게 큰 오판이었습니다. 차례대로 비교를 해 나가야 하는 것이므로, 500000*500000 의 경우의 수가 있죠... ... 그래서 리스트로 접근했던 아래 코드는 시작도 못해보고 시간초과에 걸렸습니다. sys.stdin.readline 을 이용해서 입력을 받았음에도 말이죠. 그래서 set으로 담으면 괜찮을까? 싶어서 set으로 시도를 해보았는데, 역시나 시간초..

안녕하세요 Dibrary입니다. 이번에는 leetcode의 821번 문제를 정리하겠습니다. c로 주어진 문자를 기준으로 좌우 거리마다 1씩 증가하되, c문자를 또 만나면 좌우가 대칭으로 숫자가 들어가야 합니다. 제일 먼저 든 생각은 이랬습니다. c로 입력된 문자를 뽑아내어서 index를 찾는다. 그 index 주위로 +-를 계산한다. 이렇게 하면 맨 앞부분, 맨 뒷부분은 해결이 되는데, 좌 우가 같은 경우는 도저히 해결이 안 되는 겁니다. 예를 들면, 아래 처럼 한 후에, index에 해당되는 값부터 다음 index까지를 - 해 나갈 생각이었죠, 근데 그러려면 5는 -4를 해야 하고, 4는 -2를 해야하고, 3은 -1을 해야하니까, 규칙성이 없네요? 이래서 이 문제를 풀려고 온갖 방법을 헤메고 다녔답니다..

안녕하세요 Dibrary입니다. 이번 문제는 백준알고리즘의 [1002번 - 터렛] 입니다. 제가 이 문제를 풀 때 처음에 쓸데없는 방향으로 생각이 빠져버렸었습니다. 그래서 아주 거지같은 코드가 탄생하기 시작했죠. 처음에 접근했던 생각 원점 위치별로 구분을 해야겠구나, 해당 구분 하에서 원점간의 거리와 반지름의 거리를 비교해야겠구나, 위 생각처럼 풀면 코드가 어떻게 나오냐면요... 이미 조건문만 너무 많죠? 조건문 안에 조건문이 또있고... 근데 또 위 골격에 맞춰서 작성하면 통과가 안 됩니다. 반례가 있는 것이죠... 그래서 생각을 해 보았습니다. 왜 이렇게 코드가 길어질까 뭐만 따지면 되는 것인가? 핵심은 원의 중심과의 거리, 반지름 만 고려하면 되는 것이었습니다. 처음에 원의 x, y 별로 다른 것을..

안녕하세요 Dibrary입니다. 알고리즘을 공부하려면 쉬운 기본 개념부터 공부하고, 점진적으로 그 수준을 높여 나가야 합니다. 알고리즘 관련 책은 다행이도 한국에 몇 권 있습니다. 특히나 개발자들 사이에서 통용되는 'OO책' 이런 이름들을 달고있습니다. 널리 알려진 책 중, 제가 직접 읽어본 책만 주관적인 평가를 해 보겠습니다. 비전공자가 공부하고 느낀 점인 셈이죠. 1. 종만북 종만북이라는 이름으로 정말 널리 알려진 책 입니다. 2권으로 구성되어 있으며, 대부분의 풀이에 정당성 해설도 꼭 들어 있습니다. 왜 종만북이냐구요? 저자가 구종만 입니다. ㅎㅎ 책 이름이 너무 길어서 종만북 종만북 하는 것이죠. 저는 이 책을 읽으면서 굉장히 어렵다는 생각이 제일 먼저 들었습니다. 물론, 전부 다 어려운게 아니라..