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

안녕하세요 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시간 가량 고민해 본 뒤에 다른 사람의 해답을 봐라. 라고 합니다. 근데, 거기서 끝내면 자기 공부가 안 됩니다. 제가 어려운 문제를 마주한 경우 어떤 방법으로 해 나가는지 정리해보겠습니다. 뭐 꼭 이렇게 해야 한다는 것은 아니지만, 확실한 것은 '저'에게 효과가 있었던 방법입니다. 1. 문제를 보고 떠오르는 생각을 정리해 둔다. 말 그대로 해당 문제는 어떤 방식으로 풀어야 할거 같다. 어떤 제약이 있는 것 같다. 그냥 단순히 접근하면 어떤 어려움에 봉착할 거 같다. 등 떠..

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

안녕하세요 Dibrary입니다. 개발자라면 항상 습관적으로 알고리즘을 풀곤 하죠. 주로 파이썬이 '생각'을 구현하는데 편해서 많이들 사용하는데 생각보다 파이썬은 느린 언어죠. 따라서 알고리즘문제를 풀 때 반드시 조심해야 하는 것 2가지가 있습니다. 1. 시간복잡도 네 시간복잡도는 말 그대로 코드로 해답을 구하는데 '시간'이 얼마나 걸리느냐 입니다. 백준 알고리즘을 예로 들어보겠습니다. 이렇게 입력값의 범위가 주어지면 숫자가 얼마나 큰지 감이 오시나요? 아주 어마어마하죠. 문제는, 이렇게 큰 범위 값이 항상 주어지는 것은 아니지만, 전부가 주어질 수도 있다는 겁니다. 그렇기에 파이썬으로 해당 문제를 풀기 전에 시간을 먼저 구해보는 습관을 들이면 좋습니다. 위 코드는 임의로 제가 10의 100제곱만큼의 범위..