소개
- 알고리즘 블로그 운영중
- 프로그래밍 대회 다수 수상
- ICPC Seoul Regional 3회 진출 (2021, 2022, 2023)
- 2024 ICPC Asia Pacific Championship 진출
강의
수강평
- 세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)
- 세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)
- 세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)
- 세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)
- 세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)
게시글
질문&답변
7576번 풀이 코드 관련 질문
안녕하세요, purplejay님! 코드를 살펴본 결과, 올바른 풀이로 코드를 작성하신 거 같습니다.단, max 함수에 대해 오해를 하시고 사용하신 것 같습니다. max 함수의 공식 문서를 살펴보면, 원소 중에서 가장 큰 원소를 반환한다고 나와 있습니다.따라서, 2차원 리스트를 max 함수에 넣는다면 가장 큰 값들로 이루어진 1차원 리스트가 나오는 것이 아닌, 1차원 리스트 중에서 가장 큰 리스트가 반환이 됩니다. 예를 들자면, max([[0, 1, 2], [1, 0, 1]])의 결과는 [2, 1]이 아닌, [1, 0, 1] 이라는 것입니다.즉, [0, 1, 2]과 [1, 0, 1] 중에서 [1, 0, 1]이 더 크므로 [1, 0, 1]을 반환한 것이죠.리스트의 크기 비교는 인덱스가 낮은 원소가 더 높으면 크기가 크다고 생각하시면 됩니다.즉, [1, 1, 1, 2, 1]이 [1, 1, 1, 1, 10]보다 큰 것이죠.두 리스트의 크기 비교에 관한 자세한 설명은 여기를 참고해세요 :) 질문자님이 의도하신 대로 max 함수를 이용하려면 max(max(md) for md in min_dist) 와 같이 사용하시면 될 것 같습니다. 이를 고쳐 코드를 작성하면 아래와 같이 작성할 수 있겠네요.import sys from collections import deque def bfs(cands): global data, N, M, min_dist, dx, dy visit = [[False] * M for _ in range(N)] q = deque() for (i, j) in cands: q.append([i, j, 0]) visit[i][j] = True while q: x, y, dep = q.popleft() min_dist[x][y] = min(min_dist[x][y], dep) for di, dj in zip(dx,dy): ni = x + di nj = y + dj if (0 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄5점 수강평을 남겨주시면 향후 더 나은 강의를 만드는 데 큰 도움이 됩니다. 🌟
- 0
- 1
- 47
질문&답변
2133번 문제풀이 관련 질문
안녕하세요, 최재원님! [BOJ 2133 풀이1 최적화에 대한 질문]말씀하신 것처럼 누적합을 활용하면 풀이 1의 시간 복잡도를 O(N)으로 줄일 수 있습니다.누적합을 활용하여 풀이1을 작성해보면 아래와 같이 나타낼 수 있겠네요.# solve dp = [0] * 31 dp[0] = 1 psum = [0] * 31 psum[0] = 1 for n in range(2, 31, 2): dp[n] = dp[n - 2] * 3 if n - 4 >= 0: dp[n] += 2 * psum[n - 4] psum[n] = psum[n - 2] + dp[n] # input N = int(input()) print(dp[N]) [효율적인 코딩테스트 단기 공부법에 대한 질문]코딩테스트에 나오는 빈도수로 따지면, 필수 알고리즘1 > 그래프 알고리즘 > 필수 알고리즘2 로 나타낼 수 있겠네요. 따라서 필수 알고리즘1을 다 들으셨다면, 그래프 알고리즘을 먼저 들으시는 것을 추천드립니다! 또 궁금하신 점 있으시면 질문해주세요. :)
- 1
- 1
- 35
질문&답변
1987번 관련 질문입니다.
안녕하세요, 최재원님! 백준에 제출할 때 Python3 가 아닌 PyPy3 로 제출하시면 통과할 것입니다.그러한 이유는 백준에 파이썬 코드를 제출할 때 주의할 점 강의를 참고해 주시면 감사하겠습니다. 또 궁금하신 점 있으시면 질문해주세요. :)
- 0
- 2
- 41
질문&답변
3085번 사탕 게임에서 제 풀이가 왜 틀린걸로 처리되는지 잘 모르겠습니다.
안녕하세요, 최재원님! count_max(ser) 에서 가장 긴 부분의 길이를 반환해야 하므로 아래와 같이 고쳐 주시면 될 것 같습니다!def count_max(ser): best = 0 count = 0 bef = '.' for idx in range(len(ser)): if bef != ser[idx]: count = 1 else: count += 1 best = max(best, count) bef = ser[idx] return best 또 궁금하신 점 있으시면 질문해주세요. :)
- 0
- 2
- 35
질문&답변
백준 문제풀이 팁
안녕하세요, Taejin Kim님! 결론부터 말씀드리자면, 백준에서 틀린 문제에 대해 어떤 테스트케이스가 틀렸는지 알 수 있는 방법은 존재하지 않습니다. 그러한 이유는 문제의 테스트케이스 또한 문제를 만든 저작자의 저작물이기 때문에 공개를 하지 않는 것이라고 생각하면 될 것 같습니다. 물론, 틀린 테스트케이스를 알 수 없으니 공부하기 힘들다고 느낄 수 있을 거라고 생각합니다.저 또한 처음 문제를 풀 때는 틀린 테스트케이스를 알 수 없으니 내 풀이 자체가 틀렸는지 또는 풀이는 맞지만 미처 고려하지 못한 경우가 있는지 등 채점이 틀린 정확한 이유를 파악하기 어려웠습니다. 하지만, 이러한 상황 속에서 틀린 이유를 찾는 연습을 해야 한다는 말씀을 드리고 싶습니다.왜냐하면, 코딩테스트나 대회 문제를 풀 때의 환경 또한 어떤 테스트케이스를 틀렸는지를 알려주지는 않기 때문입니다. 실제로, 코딩테스트에서 내 풀이가 틀렸는데 그러한 부분을 찾는 연습이 잘 되어 있지 않다면 한 문제에 1-2시간 동안 묶여 좋은 성적을 얻지 못할 수도 있습니다. (실제로 빈번히 일어나는 현상입니다.) 그래서, 자신의 코드의 틀린 부분을 찾는 팁들을 조금이나마 드리겠습니다.틀린 이유는 크게 2가지로 분류될 수 있습니다 첫 번째는 풀이의 로직 자체가 틀린 경우이고, 두 번째는 구현 과정에서 고려하지 못한 경우나 잘못 구현한 경우에 해당합니다. 제출을 했는데 틀렸다면, 풀이의 로직 자체가 틀린 경우일 수도 있으니 다시 한번 풀이가 맞는지 확인하는 과정이 필요합니다. 확인했는데 풀이의 로직은 맞는 것 같다면 구현 과정에서 실수를 한 것일 확률이 높습니다.사실, 풀이의 로직이 맞는지 틀린지 여부는 제출하기 전이 아닌, 코드를 구현하기 전에 최대한 검증을 해야 합니다. 풀이의 로직이 맞다면, 구현 과정에서 고려하지 못한 경우나 잘못 구현한 경우에 해당하는데요.따라서, 내가 설계한 풀이(아이디어)를 코드로 잘 구현했는지 살펴보고 틀린 부분이 없는지 확인합니다. 특히, 엣지 케이스를 확인하는 것이 좋은데요. 엣지 케이스라는 것은 끝에 해당하는 케이스를 의미합니다. 예를 들어, 문제에서 주어지는 범위가 0부터 10000까지라고 한다면, 0인 경우에 내 코드가 잘 돌아가는지, 10000인 경우에 내 코드가 잘 돌아가는지 등을 파악하는 것이죠. 또한 내 코드에 여러 가지 경우를 처리하는 로직이 포함되어 있다면 (여러 개의 if 문을 의미), 각 경우를 잘 처리하는지 실제로 코드로도 잘 돌아가는지 확인해 보는 것입니다.그리고, 가끔은 ==을 써야 하는데, =을 쓴다거나 하는 실수를 하니 코드를 전체적으로 훑어보며 문법적으로 어색한 부분이 있는지 찾아보는 것 또한 좋습니다. [정리]제 나름대로 팁들을 적어보았는데요. 이러한 팁들을 가지고 틀린 문제에 대해 어떤 부분 때문에 틀렸는지를 연습해 보는 것을 추천합니다. 결론적으로 가장 중요한 것은 자신이 틀린 부분은 자신이 잘 찾아야 하기 때문입니다. 그렇기에, 자신이 자주 실수하는 부분은 정리를 한다던가 하는 과정을 거치면 좀 더 틀린 부분을 찾는 시간이 단축될 거라고 생각합니다. 어쨌든 핵심은!! 코드의 로직을 훑어보며, (문제의 예시에 나온 것이 아닌) 여러 입력값들을 직접 넣어보며 틀린 부분을 찾는 연습을 하는 것만이 틀린 부분을 찾는 실력을 높여줄 것입니다.당연히 처음에는 시간이 오래 걸리고 힘들겠지만, 틀린 부분을 잘 찾는 것 또한 매우 중요한 능력이고 실력이기 때문에, 틀린 부분을 찾는 과정 또한 문제를 푸는 과정이라고 생각해 주시면 좋을 것 같습니다. 또 궁금하신 점 있으면 질문해 주세요. :)
- 0
- 1
- 76
질문&답변
a와 b의 최대 공약수 시간 복잡도 질문
안녕하세요, 2scent님! 말씀하신대로 정확한 시간 복잡도는 O(√a + √b)라고 할 수 있습니다. 하지만, 시간 복잡도를 표기할 때는 보통 상수배가 크지 않은 경우는 생략할 수 있기 때문에 O(√max(a, b))로 표기하였습니다.√max(a, b) 또 궁금하신 점 있으시면 질문해주세요. :)
- 0
- 2
- 52
질문&답변
DP (BOJ 12865) 풀이에 관한 질문
안녕하세요, Taejin Kim님!비슷한 질문이 있어, 해당 글을 참고하시면 도움이 될 것 같습니다! (링크)보시고, 추가적으로 궁금하신 점이나 다른 질문 있으시면 남겨주세요!
- 0
- 2
- 70
질문&답변
백준 등급
안녕하세요 다라미님!제 백준 티어는 플래티넘1 입니다! 대회 준비를 할 때에는 팀 단위로 문제를 푸는 경우가 많아, 팀 단위로 푼 문제까지 고려한다면 다이아4 정도라고 생각해주시면 될 거 같습니다. [실력과 백준 티어의 관계]실력이 높을 수록 백준 티어가 높은 것은 맞지만, 백준 티어가 높다고 잘하는 것은 아닙니다. 오히려 백준 티어를 높이는 것만을 목표로 삼는다면 문제를 곱씹어 보는 과정을 간과할 수도 있습니다. 따라서, 본인의 수준에 맞는 문제를 풀며 점점 쉬워진다면 문제의 수준을 높이며 티어를 올리는 것이 실력을 향상시키는 데에는 더 도움이 될 것입니다. 실제로 저 같은 경우에도, 티어를 올리는 데에 집중할 때보다 제 수준에 맞는 문제를 풀고 천천히 티어를 올릴 때 실력이 더 많이 늘었습니다. 알고리즘을 공부하는 초기에는 티어를 높이는 것만을 목표로 하다가, 실력을 키우기 위해서 문제를 푸는 것이 아닌 티어를 올리기 위해 문제를 푸는 경우를 많이 보아 주저리 주저리 쓴 것 같습니다. 또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.감사합니다. :)
- 0
- 1
- 91
질문&답변
11726 런타임 질문
안녕하세요. 타이거님! N에 상관없이 기본적으로 dp[0]과 dp[1]을 초기값 처리할 때 접근하기 때문입니다.dp 배열의 크기를 N + 1로 한다면 N = 0일 때, dp[1]에 접근하지 못하기 때문에 런타임 에러가 나게 됩니다.즉, N = 0일 때도 dp[1]까지 접근할 수 있게 하기 위해서 dp 배열의 크기를 N + 2로 했다고 생각하시면 됩니다. 비슷한 상황에 대한 설명이 섹션2의 '재귀함수 이해하기 [문제풀이] : BOJ 10870' 강의의 4:34 - 5:02 부분에 설명이 나와 있으니 참고하면 될 것 같습니다.추가로 해당 부분에 대한 설명을 강의 자료에 추가해 놓겠습니다. 또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.감사합니다. :)
- 0
- 2
- 57
질문&답변
브루토 포스 백준 1342 질문
안녕하세요. Taejin Kim님!공유해주신 코드를 보니, ans는 행운의 문자열을 담는 리스트로 어떤 문자열이 행운의 문자열이고 ans에 존재하지 않는다면 계속 추가하는 형식의 풀이인 걸로 확인이 됩니다. element in list의 시간 복잡도는 list의 크기 만큼의 연산이 걸린다고 생각하시면 됩니다. 따라서 행운의 문자열의 최대 개수는 10!으로 약 360만이고, 행운의 문자열 1개를 추가할 때마다 ans에 해당 문자열의 존재 여부를 in 문법을 통해서 판단하기 때문에 최악의 경우에 1 + 2 + 3 + ... + 360만 의 연산횟수가 걸리게 됩니다. 이런 이유로 시간초과가 나게 되는 것입니다. 그러므로 좀 더 효율적으로 행운의 문자열의 개수를 세야 하며, 그러한 방법은 백트레킹을 이용한 풀이 또는 같은 것이 있는 순열을 이용한 풀이이며, 이는 강의를 참고해 주시면 감사하겠습니다. 또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.감사합니다. :)
- 0
- 2
- 73