Minjun Kim

PS

[PS] BOJ 2166 / 다각형의 면적

문제 링크: https://www.acmicpc.net/problem/2166 Thumbnail: Photo by Joel Filipe (Unsplash) CCW를 응용해 다각형의 면적을 계산하는 문제입니다. 풀이 다각형의 면적? 다각형을 이루는 각 점의 좌표가 순서대로 주어질 때, 그렇게 만들어진 다각형의 면적을 구하는 문제입니다. 이전에 CCW 문제에서, CCW 알고리즘을 통해 유도된 식은 사선 공식과 동일하며, 이를 활용해

PS

[PS] BOJ 11758 / CCW

문제 링크: https://www.acmicpc.net/problem/11758 Thumbnail: Photo by 愚木混株 Yumu (Unsplash) 세 점에 대한 방향 관계를 구하는, CCW 알고리즘 풀이의 정석적인 문제입니다. 풀이 CCW? CCW는 Counter Clockwise의 약자로, 임의의 세 점 A, B, C를 순서대로 볼 때, 세 점의 연결 방향이 시계 방향인지 반시계 방향인지 판단하는 알고리즘입니다.

PS

[PS] BOJ 1717 / 집합의 표현

문제 링크: https://www.acmicpc.net/problem/1717 Thumbnail: Photo by Orevaoghene Ahia (Unsplash) 분리 집합을 구현하는 방법인 Union-Find 알고리즘을 구현하는 문제입니다. 풀이 분리 집합(Disjoint Set)? 분리 집합의 수학적 정의는 다음과 같습니다: 전체 집합 \(U\)에 대해, 서로 겹치는 원소를 가지지 않는 둘 이상의 부분 집합 \(A, B\)를

PS

[PS] BOJ 1197 / 최소 스패닝 트리

문제 링크: https://www.acmicpc.net/problem/1197 Thumbnail: Photo by Marjan Blan (Unsplash) 정석적인 최소 신장 트리(MST; Minimum Spanning Tree)를 구하는 문제입니다. 풀이 크루스칼(Kruskal) 알고리즘 MST를 구하는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재합니다. 보통 희소 그래프의 경우 크루스칼이, 밀집 그래프의 경우 프림 알고리즘이 더 유리합니다.

PS

[PS] BOJ 5582 / 공통 부분 문자열

문제 링크: https://www.acmicpc.net/problem/5582 Thumbnail: Photo by Brett Jordan (Unsplash) LCS(Longest Common Substring) 를 구하는 문제입니다. 풀이 문제 이름 그대로 LCS (Longest Common Subsequence)를 구하는 문제입니다. Longest Common String, 최장 공통 문자열 LCS 알고리즘은 2차원 배열을 사용해 결과를 계산합니다. 두 문자열 \(A\)와 \(B\

PS

[PS] BOJ 27440 / 1로 만들기 3

문제 링크: https://www.acmicpc.net/problem/27440 Thumbnail: Photo by 青 晨 (Unsplash) 그래프 탐색을 활용해, \(N\)을 1로 만드는 최단 경로를 찾으면 됩니다. 풀이 그래프 탐색 임의의 수 \(X\)에 대해, 수행할 수 있는 연산은 3가지입니다. 1. \(x\)가 3으로 나누어 떨어지면, 3으로 나눕니다. 2. \(x\)가 2로

PS

[PS] BOJ 9935 / 문자열 폭발

문제 링크: https://www.acmicpc.net/problem/9935 Thumbnail: Photo by Katelyn G (Unsplash) 스택을 활용하는 간단한 문제입니다. 풀이 문자열이 폭발한다! 💥 전체 문자열에서 "폭발 문자열"이 존재한다면, 그 부분만 폭발하고 사라집니다. 모든 폭발 문자열이 사라지고 난 뒤의 문자열을 찾는 문제입니다. 전체 문자열에서 한 문자 씩 스택에 쌓고, 현재

PS

[PS] BOJ 1967 / 트리의 지름

문제 링크: https://www.acmicpc.net/problem/1967 Thumbnail: Photo by Gene Gallin (Unsplash) 다양한 방법으로 풀 수 있겠지만, 그래프 탐색을 두 번 하는 것으로 풀었습니다. 풀이 가장 거리가 먼 두개의 정점 찾기 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만

PS

[PS] BOJ 9251 / LCS

문제 링크: https://www.acmicpc.net/problem/9251 Thumbnail: Photo by Sven Brandsma (Unsplash) LCS(Longest Common Subsequence) 를 구하는 문제입니다. 풀이 문제 이름 그대로 LCS (Longest Common Subsequence)를 구하는 문제입니다. LCS 알아보기 LCS는 크게 2가지 존재합니다. * Longest Common String, 최장 공통 문자열 * 부분 수열이 아니므로, 하나로 이어져 있는

PS

[PS] BOJ 11054 / 가장 긴 가장 긴 바이토닉 부분 수열

문제 링크: https://www.acmicpc.net/problem/11054 Thumbnail: Photo by Robert Haverly (Unsplash) LIS? LDS? 이번엔 바이토닉 부분 수열입니다. 풀이 바이토닉 부분 수열? 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 합니다.

PS Featured

[PS] BOJ 1504 / 특정한 최단 경로

문제 링크: https://www.acmicpc.net/problem/1504 Thumbnail: Photo by Toa Heftiba (Unsplash) 문제 요구 조건을 생각해보면, 결국 최단 경로 문제입니다. 풀이 다익스트라(Dijkstra)! 정점 \(1\)부터 정점 \(N\)까지의 경로 중 임의의 두 정점 \(v_1, v_2\)를 거치는 최단 거리의 경로의 거리(가중치)를 구하는 문제입니다.

PS

[PS] BOJ 9019 / DSLR

문제 링크: https://www.acmicpc.net/problem/9019 Thumbnail: Photo by Kyle Loftus (Unsplash) 그래프 탐색을 이용하는 문제입니다. 다만, 생각보다 시간과 메모리 초과로 고전했습니다 ㅎㅎ; 풀이 기본적인 접근 방법은 그래프 탐색 (DFS, BFS)입니다. 사용 가능한 4가지 연산을 활용해 \(A\)를 \(B\)로 변환하는 최소 길이의 명령어를 찾아야 합니다. 즉,

PS

[PS] BOJ 1647 / 도시 분할 계획

문제 링크: https://www.acmicpc.net/problem/1647 Thumbnail: Photo by Matthieu Rochette(Unsplash) 최소 신장 트리(MST)를 구하는 문제입니다. 풀이 "하나의 도시를 둘로 나누고, 각 도시를 연결하는 도로의 가중치 합이 최소가 되게 하라" 문제에서 요구하는 사항은 위와 같습니다. 이를 간단히 생각해보면, 전체 도시의 최소 신장 트리(

PS

[PS] BOJ 29721 / 변형 체스 놀이 : 다바바(Dabbaba)

문제 링크: https://www.acmicpc.net/problem/29721 Thumbnail: Photo by Daniel Stiel (Unsplash) 맵을 활용하는 문제였습니다. 풀이 체스판 전체를 배열로 관리하려고 하기보단 Map 자료구조를 활용해 방문한/이미 기물이 위치한 위치를 저장하는 편이 유리합니다. 먼저 모든 기물의 위치를 저장한 뒤, 각 기물의 위치에서 이동 가능한 모든 위치에 대해 해당 위치에

PS

[PS] BOJ 27447 / 주문은 토기입니까?

문제 링크: https://www.acmicpc.net/problem/27447 Thumbnail: Photo by J M (Unsplash) 오랜만에 푸는 구현 문제입니다. 풀이 기본적인 풀이는 탐욕법(그리디)에 기반합니다. 매 순간 최선의 선택을 하는 것이 최선의 결과로 이어진다고 이해하면 됩니다. 이 문제도 매 시간 토기를 굽거나 커피를 담는 등 최선의 선택을 해오면 그 결과가

PS

[PS] BOJ 2473 / 세 용액

문제 링크: https://www.acmicpc.net/problem/2473 Thumbnail: Photo by Whitney Wright (Unsplash) 투 포인터에 이분 탐색을 응용하는 문제입니다. 풀이 기본적인 접근은 용액 (BOJ 2467)과 유사합니다. 2467번 문제에서는 투 포인터로 두 용액을 골랐다면, 이번에는 세 용액을 골라야 합니다. 다만, 문제에서 주어지는 용액의 개수 \(N\)의 범위는 \(3 <

PS

[PS] BOJ 2467 / 용액

문제 링크: https://www.acmicpc.net/problem/2467 Thumbnail: Photo by Nikita Tikhomirov (Unsplash) 투 포인터인데 누적합입니다. 풀이 투 포인터 입력 배열에 두 개의 포인터를 두고, 두 위치의 용액 농도의 합의 절댓값이 작아지는 방향으로 포인터를 옮겨가며 최솟값을 찾는 방식으로 풀었습니다. 입력 배열이 이미 정렬된 상태이므로, 포인터를 이동시키는 조건은 다음과 같습니다.

PS

[PS] BOJ 2118 / 두 개의 탑

문제 링크: https://www.acmicpc.net/problem/2118 Thumbnail: Photo by Quentin BASNIER (Unsplash) 투 포인터인데 누적합입니다. 풀이 최초 구상 \(N\)개의 지점이 원형으로 이어진 상태에서, 임의의 두 지점을 골라 탑을 배치할 때 두 탑의 최대 거리를 구하는 문제입니다. 이때, 두 지점 사이의 거리는 시계 방향/반시계 방향 거리 중

PS

[PS] BOJ 1987 / 알파벳

문제 링크: https://www.acmicpc.net/problem/1987 Thumbnail: Photo by Surendran MP (Unsplash) 그래프 탐색 문제입니다. 풀이 DFS \(R \times C\) 크기의 격자에 임의의 알파벳들이 채워져 있습니다. \((0, 0)\)에서 탐색을 시작해, 한 번 지나간 알파벳을 다시 지나가지 않는 선에서 갈 수 있는 최대 길이를 구해야 하는 문제입니다. DFS를

Life

[월말정산] 25년 6월의 이야기

Thumbnail: Photo by Josh Appel (Unsplash) 벌써 6월도 다 갔습니다! 이제는 6월만 지난 게 아니라 25년도의 상반기가 다 지나갔네요. 이제 전역이 있는 하반기가 찾아왔습니다! 집에좀가자... 5월 월말정산에서 새로운 것들을 공부해보자!고 다짐했던게 무색하게 아직 마땅히 도전한건 없는 한 달이었습니다. 오히려 꾸준히 해 오던 일들의 성취가 더 쌓여갔던 한 달이었네요. 무엇을

PS

[PS] BOJ 12865 / 평범한 배낭

문제 링크: https://www.acmicpc.net/problem/12865 Thumbnail: Photo by Jakob Owens (Unsplash) DP로 풀 수 있는 0-1 배낭 문제입니다. 풀이 배낭 문제 (Knapsack Problem) 이 문제는 배낭 문제입니다. 배낭 문제는 크게 2가지로 나뉩니다. * Fractional Knapsack * 물건을 쪼개어 넣을 수 있는 배낭 문제입니다. * 탐욕법(그리디)로 풀 수 있습니다.

PS

[PS] BOJ 17070 / 파이프 옮기기 1

문제 링크: https://www.acmicpc.net/problem/17070 Thumbnail: Photo by Samuel Sianipar (Unsplash) DFS/BFS의 그래프 탐색으로 푸는 문제이지만, 그냥 풀면 시간 초과를 맞닥뜨리게 되는 문제였습니다. 풀이 DFS [\((0, 0), (0, 1)\)]에 가로로 배치되어있는 파이프를 오른쪽 / 아래 / 대각선의 3가지 방향으로 밀면서 \((N, N)\)으로 옮길 수 있는 경우의

PS

[PS] BOJ 1916 / 최소비용 구하기

문제 링크: https://www.acmicpc.net/problem/1916 Thumbnail: Photo by Igor Sporynin (Unsplash) 정말 정석적인 다익스트라 구현 문제입니다. 풀이 다익스트라(Dijkstra)! 문제를 요약하면, \(N\)개의 도시(정점)과 \(M\)개의 버스(간선)이 있을 때, 시작 위치 \(S\)와 도착 위치 \(E\) 사이의 최단 거리를 구하는 문제입니다. 한 정점에서

PS

[PS] BOJ 1932 / 정수 삼각형

문제 링크: https://www.acmicpc.net/problem/1932 Thumbnail: Photo by Rafael Garcin (Unsplash) 간단한 DP 문제입니다. 풀이 DP (Dynamic Programming) DP (Dynamic Programming, 동적 계획법)은 크고 복잡한 문제를 작고 단순한 문제로 쪼개어 푸는 알고리즘 설계 기법입니다. 💡 알고리즘 기법과 알고리즘 설계 기법의 차이? 알고리즘 기법은 문제 해결을 위한 구체적인

PS

[PS] BOJ 1753 / 최단경로

문제 링크: https://www.acmicpc.net/problem/1753 Thumbnail: Photo by oxana v (Unsplash) 정말 정석적인 다익스트라 구현 문제입니다. 풀이 다익스트라(Dijkstra)! 다익스트라 알고리즘은 그리디하게 현재 방문한 정점들로부터 가장 가까운 거리에 위치하는 정점을 찾아가는 방식입니다. 이번 문제는 정점 \(K\)에서 나머지 다른 정점들까지의 최단 거리를 계산해야 하니, 다익스트라 알고리즘이 적합합니다.