youngseo's TECH blog

0. 에필로그 원래 백준 문제는 블로그에 안 쓰고 개인적으로 정리했는데 코알라 면접 보다가 큰 영감을 얻어 열심히 기록해볼 생각이다! 👻 일주일에 적어도 5개는 풀어야징 1. 문제 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net2. 생각 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 두 개를 고르는 문제이다. 우선 이 문제에서 요구하는 현상을 2차원 그래프로 표현할 수 ..

백준에는 잘 나오지 않는 부분 배열/부분 집합 DP 로직에 대해 정리해 보았다. 1차원 배열 A에서 생각해볼 수 있는 DP 접근을 다양하게 해볼 수 있다. 간단한 목차는 아래와 같다. 1. 배열 A의 부분 배열의 최댓값 (제한 X) 2. 배열 A의 k개의 연속한 부분 배열의 최댓값 (k개라는 제한이 존재한다) 3. 배열 A의 k개 이상 연속한 부분 배열의 최댓값 (k개 이상이라는 제한이 존재한다.) 4. 배열 A에서 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부, 제한 X) 5. 배열 A에서 k개의 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부, k개라는 제한이 존재한다)1. 배열 A의 부분 배열의 최댓값 (제한 X)배열 A가 주어졌을 때, 이 배열의 부분 배열 A의 최댓값을 구하라..

목차 1. 문제 정리 2. 알고리즘 증명 및 설명 3. 코드 구현 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 1. 문제정리 2차원 평면 위에 여러 점들이 콕콕 박혀 있다. 이 점들 사이 거리 중 가장 짧은 거리를 찾으려 한다. 2. 알고리즘 증명 및 설명 일단 일일이 다 해보는 전략에 따르면, 모든 가능한 점의 쌍 거리를 구하는 데 O(N^2), 정렬하는 데 O(N^2 logN)으로 총 O(N^2 logN)의 시간복잡도가 걸린다. 그럼 이 2차원 평면을 두 개로 쪼개서 해..

문제 일단 프로그래머스는 시간제한이 따로 명시되어 있지 않다. 약 1~10초 정도의 시간 안에 풀면 된다고 암묵적으로 정해져 있다고 한다. 입력 N값이 최대 100만이므로, O(N^2)은 안된다. IDEA (잘못된 생각들..) 일단 for문 두 개로 돌리는 방법은 절대 통하지 않는다. O(N^2) 그래서 뒤에서부터 하나씩 숫자들을 판단해가면서 dictionary에 최소 index를 저장해주고 탐색하는 식으로 가려고 했으나, dictionary에 저장되는 수마저 100만이므로 똑같이 O(N^2)가 되어 이 방법도 불가능하다. IDEA - stack 자료구조 + while문 결국 아이디어를 참고하고 만 문제이다.😓 다음과 같이 하나씩 돌면서 numbers[i]가 '가까운 가장 큰 수'인 것들을 stack에서..

세상에서 제일 화나는 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 테이블을 갱신하는 방법은 이미 계산된 결과 이용하기 가 바탕이고, 다양한 방법이 있는데, 내가 짠 건.. 앞에서 왔던 길을 보는 게 아니라 갈 길에 체크를 하는 ,, 아주 바보같고 느린 방법을 사용했다. 암튼 이 코드는 매우 비효율적. '차곡차곡 쌓자'라는 접근방식을 자꾸 생각하는 걸 줄여나갈 필요가 있다. 배낭..