youngseo's TECH blog

대회 참여 계기 올해 2번째로 KAUPC가 열렸고, 나는 이번이 첫 참여였다. 아무래도 KOALA에서 주최하는 대회이다 보니 막중한 책임을 가지고 이 대회에 임하게 되었다. 여름방학 때 알고리즘 공부를 진지하게 해야겠다 생각해서 친구들 약속을 싹 미뤘던 생각이 난다... 그만큼 제대로 준비했었다. 대회는 3인 1조로 문제를 푸는 것으로, 시간은 3시간이 주어졌고 문제는 9문제였다. 25팀(75명)이나 참여해서 사람들이 바글바글 있어서 조금 놀랐고 긴장했다.. 대회 준비 개인으로 준비- ‘알고리즘 유형별로 최소 10문제는 풀어봐야 그 유형을 알 수 있다!’라는 생각을 가지고 주어진 알고리즘에 해당하는 좋은 문제들을 매일매일 1개씩 선별하여 풀어보았다. (DP, 에라토스테네스의 체, 누적합, 투포인터 등 )..

진짜 이번 2학년 여름방학이 아니면 운동을 배워볼 시간이 없을 것 같아서 큰 마음을 먹고 웨이트를 배웠었다. 피티쌤이 나랑 동갑에 나랑 MBTI 하나만 다른 ENFJ였고 그 분도 맨날 운동하셔서 같이 파트너 운동도 하고 진짜 재밌었다. 개꿀잼 암튼 그런 일이 있었다. 그래서 운동도 제대로 해보고 싶을 겸, 또 기록하고 저장해두는 걸 좋아하는 나를 떠올리며 내가 가지고 있는 기술 스택을 모아서 구현할 수 있는, 프로젝트 하나를 피그마로 구성해 보았었다. 대충 이렇다.. 그냥 진짜 내가 쓰고 싶어서 만들어본 거라 내 주관이 잔뜩 있는 데다가 왕 허접하다.. 그래서 저 중에 아주 일부분을 구현해보았다! 그냥 간단한 CRUD이다. 일기는 실시간 전송으로 현재 날짜와 내용이 전송된다. import axios fr..

테스트케이스를 만들어보다가 깨달았다…ㅠㅠㅠㅠ DP에 LIS인데, LIS가 2차원이라고 하더라도 똑같은 로직을 따라가면 된다. 이 문제에서 일단 ‘최소거리’로 간다고 했으므로 항상 오른쪽 아래로 가는 방식이다. 그래서 그냥 이 그림으로 쉽게 살펴보자. 노란색으로 동그라미 친 곳의 LIS를 살펴보고 싶다면 파란색 박스를 다 살폈을 때, 노란색 박스가 그 특정 박스보다 크다면 그 특정 박스의 LIS+1과 현재 LIS값을 살피고 갱신해주면 된다 자세한 건 코드에서 확인 가능 그리고 마지막 출력이 중요하다. 마지막 temp[N-1][N-1]을 출력한다고 계속 생각하다보니까 헤맸는데, 그냥 해당 temp 배열에서 가장 큰 값을 가져오면 그게 가장 긴 LIS이다. import sys input=sys.stdin.re..

세상에서 제일 화나는 TOP DOWN DP 유형이다. 저번 글에서 본 것처럼 DP-TOPDOWN의 형식적인 코드는 다음과 같다 (느낌만 알아두자) def topdown: if 마지막 노드에 다다른 조건: return ~~ if 이미 DP 테이블에 값이 있다면(memoization): return 그냥 그거 가져온다. #밑에 있는 노드를 호출해서 답 갱신 + 필요하다면 DP 테이블에도 값 갱신 DP[][]+= 또는 min .. topdown() return 해당 노드값 이 문제에서는 ‘되냐 안되냐’의 문제를 다룬다. 이럴 때 0, 1, max를 사용해서 풀 수 있다. 만약 조건에 만족하는 것이 하나라도 나올 시에는 return 1을 하고 안 나오면 계속 return 0을 한다. memoization 방법은..

일단 이 문제는 구현이 되게 생소하고 어렵다. 그래프를 표현하는 방법에 대해 생각을 많이 해볼 수 있는 문제라 좋다. 그래프를 배울 때 가장 먼저 배우는 것이자 많이 사용하는 것이 바로 계산하는 순서인 전위/중위/후위 표기식이다. 이런 표기식을 잘 생각해 보면서 문제를 풀어야 한다. 잘 나타내 보면, 규칙은 다음과 같다. ‘+’일 때는 그냥 내려간다. ‘-’일 때는 -오른쪽 자식의 상태를 switch 시킨다. -왼쪽은 그냥 내려간다. 이런 식으로 계속 상태를 바꾸어 주다가 마지막 노드인 1~N까지의 수에 도달하였을 때 연산자가 -라면 -가 몇 개 나오는지 모두 더해준다. 마지막으로 -의 개수(만약 3개라면) 에 따라서 가장 작은 수(3개)의 개수만큼을 최소 heapq에서 뽑아 SUM 값에서 빼준다. SU..

지금껏 다익스트라는 adj라는 배열만 만들어서 사용했었는데, 이 문제는 dijkstra를 눈치채고 다익스트라를 구현하기까지 쉽지 않았다. 일단 맨 처음 문제를 보았을 때에는 floodfill 먼저 떠올랐는데(GridWorld라서 더 그랬다), floodfill과는 결이 다르다. 왜냐면 이미 갔던 곳도 더 빠른 방법이 있다면 왼/오/위/아래 의 방법을 선택해서 빠른 방법으로 갱신해낼 수 있기 때문이다. 그래서 가중치를 가지는 다익스트라로 구현할 수 있다. 다익스트라의 특징은 다음과 같다. 가중치가 모두 양수이다. 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다. 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다. 우선순..

밑은 내가 맨 처음에 호다닥 작성한 코드. 그리고 시간초과를 받았다😥 bottom up 방식으로, 외판원이 현재 위치에서 갈 수 있는 위치로 간 후 갱신 -> 다시 그 위치에서 갈 수 있는 위치로 간 후 갱신 ---> 이 방법을 반복하였다. 어떻게 보면 DFS 느낌?으로 해결하려 했다.(이 발상이 이게 참 문제임 ) 이 코드의 문제는 DP에서 가장 중요한 문제인 MEMOIZATION이었다. DP 테이블을 갱신하는 방법은 이미 계산된 결과 이용하기 가 바탕이고, 다양한 방법이 있는데, 내가 짠 건.. 앞에서 왔던 길을 보는 게 아니라 갈 길에 체크를 하는 ,, 아주 바보같고 느린 방법을 사용했다. 암튼 이 코드는 매우 비효율적. '차곡차곡 쌓자'라는 접근방식을 자꾸 생각하는 걸 줄여나갈 필요가 있다. 배낭..

분할정복의 시간복잡도는 NlogN이다. (단계 별 문제 개수 (N//2^K) X 해당 단계에서 쪼개는/병합하는 시간(2^K) X 단계 개수(크기가 이진탐색 수준으로 줄기 때문에 logN)) 이것을 밑으로 내려가면서 쪼갤 때 / 위로 올라오면서 병합할 때 2번해서 어차피 2 NlogN이므로 시간복잡도는 그냥 NlogN이다. (DP테이블은 문제 종류가 M이라고 하면 O(NM)이라 더 효과적인 것을 확인할 수 있음) ★DP와 다른 점 부분 문제가 서로 중복되지 않는다. 위 사항 덕분에 Memoization이 필요하지 않다. 굳이 내가 알아낸 데이터를 저장하지 않는다. ★이분탐색트리 또는 세그먼트 트리와 다른 점 이분탐색/세그먼트는 일단 아는 노드를 쭉 나열해 두고 둘씩 짝지어서 위로 올라가며 판단하는 과정을 ..