알고리즘 공부

LeetCode에 Grind75라는 것이 있다. 1월 이후, 거의 매일 백준을 풀고 코딩테스트를 치르면서, 코테의 벽을 넘기가 힘들다는 것을 느끼게 되었고 어떻게 해야할지 고민을 하다가 LeetCode의 Grind75를 알게 되었다. 사실 Grind 75는 8주를 기준으로 잡았을때 75문제이고 26주까지 늘리게 되면 169문제까지 늘어나게 된다. 우선 내 생각에 LeetCode의 장점은 아래와 같다. 어떤 테스트 케이스에서 오답이 되었는지 알려준다. 에디토리얼이 있어서 어떤 의도로 문제를 냈는지 알수 있다. 사람들이 자신의 솔루션을 올리고 이를 투표하여 좋은 코드를 보기 좋다. 알고리즘 PS 뿐만 아니라 다른 컨텐츠도 있다. 물론 위의 모든 컨텐츠를 이용하기 위해서는 프리미엄이 필요하고 리트 코드를 사용..

분류 구현 혼자 힘으로 해결 했는가? O 느낀 점 그냥 순수 구현 그 자체이다. 재미는 있었다. 구현 중 제일 짜증나는 형태는 배열을 돌리고 뒤집고.. 난리 치는 경우인데 이 문제는 깔끔했다. 다만 이동 계수 부분을 잘못 체크해서 조금 애먹었다. 내가 작성한 코드 from sys import stdin from collections import deque N,M = map(int, input().split()) graph = [] for i in range(N): graph.append(list(map(int, stdin.readline().rstrip().split()))) dy = [0] + [0,-1,-1,-1,0,1,1,1] dx = [0] + [-1,-1,0,1,1,1,0,-1] ddy = [-..

분류 유니온 파인드, 분리 집합 혼자 힘으로 해결 했는가? O 느낀 점 18116번의 응용 형태이다. 이 문제는 집합의 표현이 다소 까다롭다. 보통은 가능한 집합의 원소를 모두 알려주고 시작하지만, 이 문제는 그 때 그 때 해결을 해야한다. 따라서 집합의 표현을 배열이 아닌 딕셔너리로 표현했다. 그리고 타입 때문에 골치가 아팠다. 이 문제에서 함정인 부분은 바로 a e가 입력으로 들어온 후 e a가 입력으로 들어온 경우이다. 처음은 union 함수에서 이미 같은 함수이면 아무것도 리턴을 하지 않았다가 44%에서 Type Error가 발생했다. 그 이유는 a e를 유니온 후 e a가 입력으로 온 경우 이미 같은 집합이기에 None을 리턴했고 이 때문에 타입 에러가 발생했다. 그냥 이미 친구인 관계에 대해서..

분류 유니온 파인드, 분리 집합 혼자 힘으로 해결 했는가? △ 느낀 점 유니온 파인드 문제인데, 기본적인 유니온 파인드가 아니다. 스스로 유니온 파인드 자체를 변경하는 2가지 경우를 고민 해 보았다. 1. 집합의 크기를 구하기 2. 집합의 원소를 구하기 1번의 경우는 라이님의 블로그를 참고했다. https://blog.naver.com/kks227/220791837179 유니온 파인드(Union-Find) (수정: 2020-08-03) 이번에 소개해드릴 것은 다소 이질적이게 보일 수 있는 자료구조입니다. 그 이름하여 유니온 파인드(union-... blog.naver.com 2번의 경우는 gpt를 통해 구현을 해서 코드를 해석했다. 이 문제는 기본적인 유니온 파인드에서 더 나아가 집합의 갯수를 체크해야 ..

분류 파라매트릭 서치 혼자 힘으로 해결 했는가? 애매하다.. 느낀 점 이런 류의 문제가 생각보다 나는 접근이 힘들다. 문제의 요구사항을 그대로 수행하는 방식으론 절대 해결이 불가능 하다. 일단 입력 값 부터 10억이기 때문에 무조건 log로 만들어야 하고 이는 이분 탐색이 필요함을 알 수 있다. 그러나 어디에 이분 탐색을 써야하는지가 생각하기 힘들다. 우선 이 문제는 약간의 그리디로 접근을 해야하는데 그렇다고 무조건 그리디로 해결하면 안된다. 2가지이면 특정 사람이 1번에서 검사를 받거나 or 2번에서 검사를 받는 형태의 dp로 접근을 하겠지만 (그러나 입력 값이 10억이라 그냥 안됨) 우선 어떻게 해결을 할지부터가 어려웠다. 이 문제는 어렵게 생각하기 보다는 그냥 가장 오래 걸리는 시간까지 1씩 증가 ..

분류 구현, (우선순위 큐) 혼자 힘으로 해결 했는가? O 느낀 점 상어....만 보면 머리가 아파진다. 이 문제를 이번에 처음 푸려고 시도한 것은 아니다. 약 6개월 전에 해결을 해보고자 문제를 읽었지만 너무 머리가 복잡해져서 포기했다. 다시 도전하니 한번에 해결을 해서 기분이 좋았다. 이 문제에서 조건이 많아서 귀찮다. 어렵지는 않지만 귀찮고 과연 이게 될까? 라는 생각에 풀이를 시작하기가 꺼려진다. 이 문제에서 제일 짜증났던 부분은 아래와 같다. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 이제 이러한 비슷한 3차원 BFS문제는 크게 어렵지 않게 풀수 있을것 같다. 비슷한 문제는 1600번인데, 해당 문제와 차이점은 z축으로 추가적인 이동을 하기 위해서는 이동하는 그래프가 벽일 때만 가능하도록 해줘야 한다는 것이다. 내가 작성한 코드 from sys import stdin from collections import deque N, M, K = map(int, input().split()) MX = 10000001 graph = [] visit = [[[MX for k in range(K + 1)] for col in range(M)]for row in range(N)] for i in range(N): graph.append(list(st..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 3차원 상태가 필요한 BFS 문제를 많이 풀다보니 이번 문제도 어렵지 않게 구상이 되었다. 크게 어렵지는 않았으며, 벽 부수고 이동하기와는 달리 K번까지 이동 가능한 부분만 잘 처리하면 된다. 내가 작성한 코드 from sys import stdin from collections import deque K = int(input()) W, H = map(int, input().split()) graph = [] for i in range(H): graph.append(list(map(int, stdin.readline().rstrip().split()))) MX = 1000001 visit = [[[1000001 for k in range(K + 1)] ..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 이번 문제는 해결하고도 왜 시간초과 없이 해결이 된 것인지 의아했다. 아니나 다를까 백준에서 문제에 대한 의견들을 찾아보니 나 처럼 이게 풀리다니... 하는 반응이었다. 처음 문제를 봤을 때, 각 섬들에 대해 BFS를 사용하여 마킹을 해두고 각 섬들마다 인접한 바다에서 BFS를 사용해서 최단거리를 brute force로 구하는 것이었다. 그러나 이는 러프하게 계산해도 N^4에 근사한 시간복잡도가 나와 절대 안 풀릴것 같았고 바다에서 BFS를 하는 방법 등 고민을 하다가 우선 처음 생각난 방법대로 구현을 해 보았다. 처음 구상한 방법도 구현 난이도가 쉽지는 않아서 구현 + BFS의 느낌이 강했다. 그런데... 이게 시간초과가 없이 풀려서 나도 놀라웠다. ..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 매우 모범적인 문제라고 생각한다. 기계적으로 BFS를 막 때려맞히는 것이 아니라, BFS의 근본적인 목적 = 그래프 탐색을 이해하고 있는지 스스로 점검을 하기 좋은 문제라고 생각이 된다. 가중치가 모두 동일한 그래프에서 특정 지점에서 특정 지점으로의 최단 경로를 찾을 때 가장 빠른 알고리즘이 BFS이다. 최단경로를 찾는 알고리즘으로는 다익스트라 알고리즘 플로이드 와샬 알고리즘 벨만 포드 알고리즘 이렇게 존재하고 저 셋중 가장 빠른 것은 우선순위 큐를 사용한 다익스트라 알고리즘이다. O(Nlogn) 다익스트라 알고리즘은 가중치가 여러개인 경우 사용할 수 있는 가장 빠른 알고리즘이나 가중치가 모두 같다면, BFS가 가장 빠르다 O(N) BFS는 사실 최단경..