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

안녕하세요 Dibrary입니다. 이번에는 이진탐색을 사용해서 풀어야 하는 문제를 정리해보겠습니다. 처음에 나름 알머리 굴리다가 시간초과로 실패를 겪은 문제입니다. 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제를 처음 보자마자 떠오른 생각은 아래와 같습니다. M만큼만 자르면 된다. (이걸 반복문에서 캐치해야 할 것 같다.) M만큼 자르는 M-1 포인터를 for문으로 돌리면 어떨까. 근데 2번에서 생각해보니 거의 100000! 번에 가까운 연산이 이뤄질 수도 있다는 생각이 들어서 위 방법은 곧바로 포기 했습니다...

안녕하세요 Dibrary입니다. 이번에는 제가 BFS/DFS에 아주 약간? 자신감이 생겨서 도전했다가 몇 시간을 .. 날려버린 문제를 정리해보겠습니다. 알고보니 BFS/DFS같은 그래프 풀이방법 만 쓰는 게 아니라, 여기에 모든 경우의 수 까지 같이 확인해야 하는 문제였어서 처음 접한 저는 매우 어려웠었습니다. 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 처음에 문제를 보고 곧바로 "BFS를 쓰믄 되겠다! " 라는 생각이 제일 먼저 떠올랐습니다. 왜냐하면, 문제에서 "바이러스는 퍼져나갈 수 있다" 라고 나왔기 때문이죠...

안녕하세요 Dibrary입니다. 이번에는 굉장히 유명한 '회의실 배정'문제를 정리해보겠습니다. 사실, 이 문제는 여러 알고리즘 책에 소개가 되었으나 막상 안보고 하려니 잠시 헷갈린 문제입니다. 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 먼저 예제 입력에 대해서 확인을 해보겠습니다. 총 11개의 가능한 시간이 주어지는데, 이를 엑셀로 표현해보면, 이렇게 나옵니다. 이 중에 예제 출력의 결과인 4가 나오게 하려면, 이렇게 골라야 합니다. 근데, 이때 제가 의문이 들었던 내용은, 첫 번째로 택해진 1, 4에 해당되는 시간 구간은 맨 처음에 시작하는 것도 아니고, 그렇다고 길이가 가장 긴 것도 아니고, 아무것도 아닌데, 그럼 ..

안녕하세요 Dibrary입니다. 이번 문제는 '스택'을 활용한 문제입니다. 스택을 배우긴 했는데, 어떻게 써야할 지 모르는 사람이었다면 이 문제를 풀지 못했을 겁니다. (저처럼요...) 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 먼저 예시로 나온 문제를 보면 10, 3, 7, 4, 12, 2 에서, 10을 기준으로는 3개, 7은 1개, 12는 1개 총 5개를 볼 수 있죠. 그래서 전 처음에 이런 방식으로 도전했었습니다. 모든 타워 정보를 넣은 후에, for문을 2겹으로 돌면서 기준 타워보다 그 다..

안녕하세요 Dibrary입니다. 이번에는 그래프 탐색 + 약간의 생각을 사용해야 풀 수 있는 문제 입니다. (참고로 저는 생각을 하지 못해서 어려웠었죠;;) 이 문제를 보자마자 떠오른 생각은 아 확산이 되네? BFS또는 DFS로 퍼뜨려 나갈 수 있겠다. 근데 시작점이 한 개가 아니네....? 헐 생각 1번을 구현하기는 어렵지 않습니다. 문제는 '시작점'이 여러 개 인 것을 해 본 적이 없다는 것이었죠. 이 문제를 풀 때 생각해볼 2가지 아이디어가 있습니다. 먼저 잘 생각해 보면 시작점이 여러 개인 것은 그다지 중요하지 않습니다. BFS를 사용한다고 할 때, 우리는 해당 '위치'에 대해서 뭘 고려할까요? '방문 했느냐' / '방문 안했느냐' 입니다. 즉, 시작점이 여러 개라 한들 방문해버리면 어차피 거긴 ..

안녕하세요 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 별로 다른 것을..