최용우

백준이라는 온라인 알고리즘 문제풀이 사이트에서 문제를 풀고있다. 햇수로는 어느덧 3년차가 되었다. 나는 1주일 1문제 풀기를 목표로 하고있다. 목표치가 너무 낮은가 싶다가도 나의 풀이속도를 볼때 적당한 수준이다. 나의 문제풀이 현황. 초록색이 문제를 해결한 날이다. 가끔 이런 궁금증이 생긴다. 1. 문제가 안풀리면 답지를 보는것이 좋나요? 아니면 안보고 끝까지 푸는게 좋나요? 2. 몇시간 정도 고민하는것이 적당한가요? 위 질문에 정답은 없다. 어떤 사람은 답지를 끝까지 안보고 풀어내는것이 의미가 있다고하고 어떤 사람은 지나치게 물고 늘어지는것은 비효율적이므로 일정시간동안 진척이 없으면 답지를 보는것이 좋다고 한다. 그래서 GPT에게 물어보았다. 역시 귀에 걸면 귀걸이 코에 걸면 코걸이라고 일명 '케바케'..

이분 탐색 아이디어로 풀면된다. 주어지는 수가 최대 500억이므로 이분 탐색 문제임을 쉽게 떠올릴 수 있다. k명씩 최대 몇개의 그룹을 만들 수 있는지 확인 한다(총 인구 수 // k)-> high 그룹은 최소 1개 이상 -> low count는 현재 사이클에 차있는 그룹 수 cycle은 현재까지 그룹별로 차리한 횟수 만약에 설정한 그룹 수 보다 인구수가 많다면 cycle에 1을 더하고 넘어가면 된다. n, k = map(int, input().split()) data = list(map(int, input().split())) low = 1 high = sum(data) // k from collections import deque while low = target: cycle += 1 else: co..

구현 + 완전탐색 문제이다. 구현이 조금 까다로워서 골드4 수준인듯 하다. 나는 조건문 + 재귀문을 이용해서 완전 탐색을 구현했다. 코드가 조금 지저분 하긴 한데 더 효율적인 방법이 있으면 소개부탁드린다. import sys input = sys.stdin.readline data = [] n = int(input()) nn = n ** 2 for _ in range(nn): line = list(map(int, input().split())) data.append(line) from collections import deque def calc(d, count): q = deque(d) for _ in range(count): x = q.pop() q.appendleft(x) return list(q) ..

2차원 배열에서 부분합에 대한 이해도를 묻는 문제. 행렬의 최대크기는 가로 x 세로 = 200 x 200 = 40000이며 O(n^2)이라고 하더라도 1억6천번으로 2초내에 계산이 가능하다. 특정 좌표 i, j에서 1, 1까지 부분합을 전부 계산하여 최대값이면 갱신하는 식으로 풀어냈다. 행렬의 크기를 1씩 늘려서 만들어주는 이유는 padding을 통해 계산을 용이하게 하기 위함이다. n, m = map(int, input().split()) data = [[0] * (m+1) for _ in range(n+1)] #부분합 만들어주기 for i in range(1, n+1): line = list(map(int, input().split())) for j in range(1, m+1): data[i][j]..

푸는데 하루 꼬박 걸렸다. 처음부터 경우의 수를 잘 나누어서 분기처리했다면 더 잘 풀었을 텐데 주먹구구식으로 풀다보니 30번째 제출에 해결하였다. 풀이가 막 떠오른다고 섣불리 타자를 치기보단 정리 후 예외 사항은 없는지 반례는 없는지 고민해보는 습관의 중요성을 깨달았다. 12시간을 투자해서 풀었지만 의미있었던 문제라 기록을 남긴다. 쪼갤 수 있을때까지 세분화해서 문제를 풀어갈 것. 첫번째, 좌표평면에서 오른쪽 상단으로 밖에 움직일 수 없으므로 지뢰의 위치가 오세준보다 왼쪽 아래에 있는 경우 -1 두번째, 지뢰가 오세준의 x좌표 동일 선상에 있거나 y좌표 동일 산성에 있을 때 세번째, 오른쪽으로 i번 움직이면 위로는 n - i번 움직일 수 있고 모든 경우의 i에 대하여 완전 탐색을 한다. 이때 x축의 거리..

문자열 문제 같지만 사실은 수학 문제. a, b, c, d 4개의 음이 아닌 정수가 주어진다. 1) a, b, c, d 중 하나라도 0인 경우 2) a, b, c, d 모두 1 이상의 값일 때 두번째 경우 작은 수들 사이를 경계로 만들어 줄 수 있다. 예를 들어 b = 3 이면 아래 파란색 타원과 같이 a가 들어갈 자리는 b + 1 = 4 이 된다. b + 1 개 자리에서 a의 짝들이 최대 몇개까지 들어갈 수 있는지 계산 해주면 된다. (maxA, maxB가 모두 1이상임을 보장하므로) 만약 a == b 라면 a의 짝들은 타원 3개를 차지하므로 b * 2 a == b + 1 이라면 a + b a > b + 1 이라면 min(maxA * (b + 1), a) + b 끝. import sys input = ..

그래프 문제를 끄적이다 보면 단골로 등장하는 알고리즘이다. 3개의 특징을 구분지어 보고자 한다. 1) 다익스트라 : 하나의 정점에서 다른 어떤 정점까지의 최단거리를 구할 때 2) 플로이드 와샬 : 모든 정점에서 다른 어떤 정점까지의 최단거리를 구할 때 3) 벨만포드 : 하나의 정점에서 다른 어떤 정점까지의 최단거리 구할 때 딱 보아도 플로이드 와샬이 시간 복잡도가 가장 크다. 다익스트라 O(V+E) > 벨만포드 O(VE) > 플로이드 와샬 O(V3제곱) 세 알고리즘은 장단점이 있다. 그러나 특수한 경우에는 특정한 알고리즘을 쓰는 것이 좋다. Case 1. 하나의 정점에서 어떤 정점의 최단거리를 구할 때(일반적인 경우) => 다익스트라 Case 2. 음의 가중치가 존재하거나 음의 사이클을 검출 할 때 =>..

나를 괴롭혔던 정렬 알고리즘. 병합정렬과 함께 가장 빠른 정렬 알고리즘이다. 다만 안정성은 병합정렬이 좋아서 대다수의 내장함수들은 병합정렬을 채택한다. 분명 2년전 자료구조 수업때 java로 구현해봐서 당연히 알고있다고 착각하고 있었다. 파이썬으로 간만에 재미삼아 구현하려니 안된다. 진짜 실력의 부족함을 매일 느낀다. 나는 언제쯤 잘해질 수 있을까. 추상적으로는 아래와 같은 절차를 따르면 된다. 1. pivot 원소 지정(어디든 상관 없음, 일반적으로 처음 or 끝 or 중간) 2. 배열 양끝단에 두개의 포인터를 지정한다. 일반적으로 i, j 3. 피벗원소보다 작은 원소는 왼쪽으로, 큰건 오른쪽으로 보낸다. - 원소 교체 후 i++, j-- 4. 3번을 반복하다 i > j 가 엇갈리면 i 혹은 j를 기준..