PS

Problem Solving (알고리즘, 자료구조 문제풀이)

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를

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\)에서 나머지 다른 정점들까지의 최단 거리를 계산해야 하니, 다익스트라 알고리즘이 적합합니다.

PS

[PS] BOJ 15666 / N과 M (12)

문제 링크: https://www.acmicpc.net/problem/15666 Thumbnail: Photo by Tony Pham (Unsplash) N과 M은 다시 말하지만 유명한 백트래킹 시리즈입니다. 풀이 기본적인 풀이는 15663번 문제(N과 M (9))와 동일합니다. 하지만, 입력으로 주어지는 수열에 숫자가 들어있기만 하면, 주어진 개수와 무관하게 몇 개든 꺼내 결과 수열에 사용할 수 있습니다. 또,

PS

[PS] BOJ 11660 / 구간 합 구하기 5

문제 링크: https://www.acmicpc.net/problem/11660 Thumbnail: Photo by Melissa (Unsplash) 2차원 배열의 누적 합 문제입니다! 비슷한 문제를 풀었던 기억이 있네요. 풀이 누적 합을 계산하는 풀이는 지정좌석제 (33993)와 같습니다. 다만, 지정좌석제 풀이에서는 범위의 중앙 좌표를 기준으로 계산했다면 이번 문제는 편의 상 끝 쪽 좌표를 사용했습니다. 누적 합

PS

[PS] BOJ 15663 / N과 M (9)

문제 링크: https://www.acmicpc.net/problem/15663 Thumbnail: Photo by Ronit Shaked (Unsplash) N과 M은 다시 말하지만 유명한 백트래킹 시리즈입니다. 풀이 기본적인 풀이는 15652번 문제(N과 M (4))와 동일합니다. 하지만, 입력으로 주어지는 수열에 중복되는 수가 존재하며, 출력할 결과는 사전순으로 정렬되어야 하고 중복이 허용되지 않습니다. 중복 방지하기 결과를 저장할

PS

[PS] BOJ 14003 / 가장 긴 증가하는 부분 수열 5

문제 링크: https://www.acmicpc.net/problem/14003 Thumbnail: Photo by Lindsay Henwood (Unsplash) 놀랍게도 가장 긴 증가하는 부분 수열 4(14002)와 풀이가 동일합니다..! 왜 난이도가 다른걸까요... 풀이 가장 긴 증가하는 부분 수열 4(14002)의 풀이를 참고해주세요! 전체 코드 input = open(0).readline N = int(input().strip()) A

PS

[PS] BOJ 28325 / 호숫가의 개미굴

문제 링크: https://www.acmicpc.net/problem/28325 Thumbnail: Photo by mi_shots (Unsplash) 여러 시행 착오를 겪으며 풀었던 문제입니다. 백준 채점 서버에 문제가 있어 채점되는걸 오랫동안 기다렸습니다...ㅎㅎ 풀이 단계별로 계산하기 다음 과정으로 최대 개미의 수를 계산합니다: * 먼저, 쪽방이 있는 경우는 쪽방에 개미를 채우고 본 방(쪽방이 연결된 방)