SWEA 2383: 점심 식사시간 풀이 정리 문제 조건 분석 계단을 내려가는 시뮬레이션에서 가장 중요한 규칙들을 정리합니다. 계단 입구까지의 이동 시간 사람($P$)에서 계단 입구($S$)까지 가는 시간은 맨해튼 거리로 계산합니다. $이동 시간 = PR - SR ...

문제 조건에서 N은 1,000,000,000,000,000,000까지 주어진다. 즉, int는 물론이고 일반적인 선형 DP로도 감당하기 어려운 크기다. 게다가 결과는 1,000,000,007로 나눈 값을 출력해야 한다. 처음 이 문제를 봤을 때는 익숙한 피보나치 문제처럼 보였지만, 입력 범위를 보는 순간 평소 방식으로는 안 되겠다고 생각했다. 이 문...

구간 합 질의가 잦은데 값도 자주 바뀌는 문제를 풀면서 세그먼트 트리를 다시 손에 익혔다. 스터디 때 쓴 자바 코드를 정리해둔다. 노드 의미와 배열 인덱싱 segmentTree[node]는 구간 [nodeL, nodeR] 합을 담는다. 부모의 왼쪽·오른쪽 자식 인덱스는 2*node, 2*node+1. 트리 크기는 안전하게 4*N 배열을 ...

두 문자열의 최장 공통 부분수열(LCS)을 풀다가, 캐시를 켜고 끈 상태가 얼마나 다른지 직접 찍어봤다. 손에 익힌 느낌을 적어둔다. 문제와 기초 재귀 기본 재귀식은 다음과 같다. 문자가 같으면 1을 더하고, 아니면 두 가지 분기를 비교한다. int LCS(int i, int j) { if (i == n || j == m) return 0; ...

스터디 때 밤새 붙잡았던 문제다. “1에서 N까지 가는데 v1, v2를 모두 거쳐야 한다”는 제약이 붙으니 구현이 헷갈렸다. 직접 자바로 정리해둔 기록. 문제 세팅 양방향 가중치 그래프, 정점은 1..N 반드시 v1, v2를 모두 통과해야 하며 순서는 자유 답은 min(1→v1→v2→N, 1→v2→v1→N) 핵심 코드 가중치가 큰 입...

[문제링크] N x N 격자에서 좌상단→우하단 최소 비용을 구하는 문제. 가중치가 모두 양수라 그냥 다익스트라면 된다. 그래도 우선순위큐로 바꿔야 마음이 편함. 구현 메모 dict[y][x]는 시작점에서 (y,x)까지의 최소 비용. 4방향 이동 시 if (dict[ny][nx] > dict[cy][cx] + cost)로 완화. 큐...

[문제링크] 정점 v1, v2 둘 다 들러야 하는 다익스트라 응용. C++로 풀었던 거 Java로 다시 구현해 봄. 그냥 3번 돌리면 끝나는 문제. 접근 시작(1), v1, v2를 각각 출발점으로 다익스트라 3번 실행 → dict1, dictV1, dictV2. 가능한 경로 두 개 1 → v1 → v2 → N ...

[문제링크] 인접 리스트 + 우선순위 큐로 프림 알고리즘 구현. 크루스칼이랑 자꾸 헷갈려서 PQ 버전만 짧게 적어둔다. 흐름 임의 시작 정점의 가중치를 0으로 두고 PQ 삽입. PQ에서 최소 간선을 꺼내 방문하지 않았으면 MST 가중치에 누적. 해당 정점에서 나가는 간선으로 이웃의 최소 비용을 갱신하며 PQ에 push. 코드 발췌 ...

[문제링크] Disjoint Set 기본기 복습용. 헷갈릴 때마다 다시 쓰게 돼서 아예 정리. find에 경로 압축만 얹은 버전이라 금방 구현 가능. 핵심 함수 static int find(int v) { if (v == parent[v]) return v; return parent[v] = find(parent[v]); // 경로 ...

[문제링크] N x N 종이를 4분할하면서 색이 다르면 재귀를 더 파는 전형적인 분할정복 문제. 구현은 심플한데, 재귀 흐름 한 번 정리해두려고 기록. 핵심 아이디어 check(y,x,size)로 현재 영역이 단색인지 검사. 단색이면 색 카운트 후 반환, 아니면 size/2로 4분할 재귀 호출. 시간복잡도 O(N^2 log N) 정도(...