PS

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

PS

[PS] BOJ 13913 / 숨바꼭질 4

문제 링크: https://www.acmicpc.net/problem/13913 Thumbnail: Photo by Dagmar Klauzová (Unsplash) BFS로 풀 수 있는 숨바꼭질 시리즈입니다. 다만, 이전 숨바꼭질 문제들과는 다르게 "최단 경로" 도 출력해야 합니다. 풀이 BFS 기본적인 풀이는 BFS로 다른 숨바꼭질 문제들과 같습니다. 하지만, 이번 문제는 최단거리로 도달하기 위해 거친 경로를 같이

PS

[PS] BOJ 13549 / 숨바꼭질 3

문제 링크: https://www.acmicpc.net/problem/13549 Thumbnail: Photo by Annie Spratt (Unsplash) BFS로 풀 수 있는 숨바꼭질 시리즈입니다. 풀이 BFS 역시나 BFS로 풀 수 있습니다. 다만, 이전 숨바꼭질 2(12851)과는 다르게, 순간이동하는 경우는 이전 경우와 시간 차이가 나지 않습니다! 따라서, 순간이동 하는 경우가 다른 경우보다 처리되는 순서가

PS

[PS] BOJ 26091 / 현대모비스 소프트웨어 아카데미

문제 링크: https://www.acmicpc.net/problem/26091 Thumbnail: Photo by Stephen Kidd (Unsplash) 문제 이름에 걸맞는 현대차로 썸네일 들고 왔습니다 😄 풀이 구상 가장 많은 팀을 소프트웨어 아카데미에 참여시키기 위해서는 결국 점수가 가장 높은 사람과 가장 낮은 사람을 같은 팀에 붙이는 식으로, 팀의 능력치가 중간 값에 맞춰지도록 하는 방식을 구상했다.

PS

[PS] BOJ 30804 / 과일 탕후루

문제 링크: https://www.acmicpc.net/problem/30804 Thumbnail: Photo by Yevhen Buzuk (Unsplash) 풀이 과일의 종류별 개수 세기 정답을 구하기 위해서는, 현재 탕후루에 포함된 과일의 개수를 세는 방법이 필요합니다. 이는 Map 형태의 자료구조를 활용하면 됩니다. 투 포인터 투 포인터란, 이름처럼 두개의 포인터(배열의 인덱스)를 가지고 부분 배열을 동적으로

PS

[PS] BOJ 4396 / 지뢰찾기

문제 링크: https://www.acmicpc.net/problem/4396 Thumbnail: Photo by MW (Unsplash) 항상 썸네일 이미지를 Unsplash에서 찾고 있는데, 도저히 지뢰 찾기 이미지를 찾을 수 없어서 그냥 게임 맵처럼 보이는 걸로 들고 왔습니다.. 😅 풀이 지뢰 위치 기록하기 먼저, \(N \times N\)의 크기로 지뢰의 위치가 주어집니다. 지뢰의 위치를 좌표꼴로 저장해도

PS

[PS] BOJ 14002 / 가장 긴 증가하는 부분 수열 4

문제 링크: https://www.acmicpc.net/problem/14002 Thumbnail: Photo by Mayer Tawfik (Unsplash) 기본적인 풀이는 가장 긴 증가하는 부분 수열 2, 3과 동일합니다. 하지만, 이번 문제는 찾은 부분 수열의 원소들도 출력해야 합니다. 풀이 이분 탐색을 활용해 LIS 찾기 가장 긴 증가하는 부분 수열 2(BOJ 12015)의 풀이를 참고해주세요!

PS

[PS] BOJ 12738 / 가장 긴 증가하는 부분 수열 3

문제 링크: https://www.acmicpc.net/problem/12738 Thumbnail: Photo by Ruffa Jane Reyes (Unsplash) 놀랍게도 어제 풀었던 문제(12015)와 같은 풀이로 풀 수 있습니다! 수의 범위가 음수까지 포함되어 뭔가 더 고쳐야 할지 고민했던게 무색하게 그냥 풀려버렸습니다... 풀이 12015 (가장 긴 증가하는 부분 수열 2)의 풀이를 참고해 주세요~

PS

[PS] BOJ 12015 / 가장 긴 증가하는 부분 수열 2

문제 링크: https://www.acmicpc.net/problem/12015 Thumbnail: Photo by Imagine Buddy (Unsplash) 어제 풀었던 LIS 문제와 마찬가지이나, LIS의 길이가 아닌 원소 합을 기준으로 찾는 문제입니다. 풀이 LIS 이해하기 LIS(Longest Increasing Subsequence)에 대한 설명은 이전 글을 참고해주세요! DP 풀이의 한계 이전까지는 입력으로 주어지는 배열의 길이가 1,000

PS

[PS] BOJ 11055 / 가장 큰 증가하는 부분 수열

문제 링크: https://www.acmicpc.net/problem/11055 Thumbnail: Photo by Walls.io (Unsplash) 어제 풀었던 LIS 문제와 마찬가지이나, LIS의 길이가 아닌 원소 합을 기준으로 찾는 문제입니다. 풀이 LIS 이해하기 이 문제는 LIS의 DP 방식 풀이로 풀 수 있습니다! 관련 내용은 이전 글 참고해주세요~ DP 배열 채우기 이전에 LIS 배열을

PS

[PS] BOJ 11053, 11722 / 가장 긴 증가하는 부분 수열

문제 링크: 가장 긴 증가하는 부분 수열: https://www.acmicpc.net/problem/11053 가장 긴 감소하는 부분 수열: https://www.acmicpc.net/problem/11722 Thumbnail: Photo by Denys Sudilkovsky (Unsplash) LIS 유형을 공부하면서, 시리즈를 좀 풀어보려고 합니다. 가장 쉬운 두 문제를 풀어봤습니다. 풀이 LIS 이해하기 LIS(Longest Increase Subsequence, 가장

PS

[PS] BOJ 30641 / 회문 끝말잇기

문제 링크: https://www.acmicpc.net/problem/30641 Thumbnail: Photo by Sophia Richards (Unsplash) 수학 문제는 늘 머리가 아픕니다.. 풀이 거듭제곱 속도 개선하기 회문의 길이는 최대 \(10^6\)이므로, 등비수열 꼴의 항을 점화식으로 (반복문으로 직접 곱해가며) 계산하게 되면 상당한 수의 거듭제곱 연산(정확히는 같은 수를 여러번 곱하는 과정)이 수행된다.

PS

[PS] BOJ 1911 / 흙길 보수하기

문제 링크: https://www.acmicpc.net/problem/1911 Thumbnail: Photo by Duc Van (Unsplash) 스위핑 문제입니다. 널빤지 배치를 효율적으로 하는 과정에 대해 조금 고민했습니다. 풀이 스위핑 특정 범위에 대한 입력을 정렬한 뒤, 순차적으로 읽어나가는 기법입니다. ponds = [] for _ in range(N): s, e = map(int, input().strip().split()) ponds.append((s,

PS

[PS] BOJ 14496 / 그대, 그머가 되어

문제 링크: https://www.acmicpc.net/problem/14496 Thumbnail: Photo by Cody Chan (Unsplash) 썸네일은 문제랑 아무 상관 없지만, 문득 라멘이 먹고 싶어서 찾아왔습니다. 풀이 최단 거리 탐색하기 문제에서 문자 간의 치환으로 표현했지만, 결국 정점 \(a\)에서 \(b\)로 가는 최단 거리를 찾는 문제로 해석할 수 있습니다. 두 정점 사이의

PS

[PS] BOJ 6568 / 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다

문제 링크: https://www.acmicpc.net/problem/6568 Thumbnail: Photo by Amr Taha™ (Unsplash) 문득 solved.ac 디스코드를 둘러보다가 보인 문제인데, 재밌어 보여서 풀어봤습니다. 간만에 구현 문제라 Python3에 타입힌트랑 주석까지 써가면서 만들었네요 ㅎㅎ 풀이 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다 귀도 반 로썸은 정말 심심하다고 파이썬을 만들어버렸는데, 이 문제에서도

PS

[PS] BOJ 32373 / 장난감 자물쇠

문제 링크: https://www.acmicpc.net/problem/32373 Thumbnail: Photo by Susan Holt Simpson (Unsplash) 시간초과와 싸우며 유익한 고민을 했던 문제였습니다 ㅎㅎ 풀이 어떻게 정렬을 할 것인가? 문제의 조건에서,  주어진 양의 정수 \(k\)에 대하여 수열에서 거리가 \(k\)인 쌍만 교환할 수 있다고 명시했습니다. 따라서, 일반적인 정렬 방법으로는 조건이 지켜지지

PS

[PS] BOJ 33993 / 지정좌석제

문제 링크: https://www.acmicpc.net/problem/33993 Thumbnail: Photo by Hiroyoshi Urushima (Unsplash) 예제 입력을 잘 보도록 합시다.. 풀이 누적 합 \(R \times C\) 크기의 좌석에 임의의 위치에 \(N\)명의 친구가 앉아 있습니다. 각 좌석을 중심으로 주변 \(W \times W\) (단, \(W\)는 홀수) 안에 있는 친구의 수를 그

PS

[PS] BOJ 15918 / 랭퍼든 수열쟁이야!!

문제 링크: https://www.acmicpc.net/problem/15918 Thumbnail: Photo by Miikka Luotio (Unsplash) 오늘도 즐거운(?) 백트래킹입니다. 풀이 랭퍼든 수열? 문제에서 언급한 랭퍼든 수열은 다음의 규칙을 가집니다. * 1 이상 n 이하의 자연수가 각각 두 개씩 들어 있다. * 두 개의 n 사이에는 정확히 n개의 수가 있다. 단, 문제에서는 두 위치 \(X\

PS

[PS] BOJ 12834 / 주간 미팅

문제 링크: https://www.acmicpc.net/problem/12834 Thumbnail: Photo by Ugne Vasyliute (Unsplash) 간만에 그래프 문제 풀어보니까 재밌었습니다 ㅎㅎ 풀이 다익스트라(Dijkstra) vs 플로이드-워샬(Floyd Warshall) 그래프에서 최단 경로를 찾는 문제이므로, 생각할 수 있는 풀이 방법은 다익스트라(Dijkstra)와 플로이드-워샬(Floyd Warshall)의 2가지가 있습니다. 하지만, 문제의 조건에서 정점의

PS

[PS] BOJ 14613 / 너의 티어는?

문제 링크: https://www.acmicpc.net/problem/14613 Thumbnail: Photo by Fredrick Tendong (Unsplash) DP는 배열을 어떻게 설계할 지가 항상 직관적으로 보이지 않아 어려운 것 같습니다... 풀이 DP 배열 힌트 도저히 떠오르는 게 없어서 질문 게시판을 보며 DP 배열의 힌트를 얻었습니다. 처음에는 승리/패배/무승부 횟수 3가지를 전부 DP 배열의

PS

[PS] BOJ 1011 / Fly me to the Alpha Centauri

문제 링크: https://www.acmicpc.net/problem/1011 Thumbnail: Photo by NASA Hubble Space Telescope (Unsplash) 골드 5 치고는 생각보다 풀이가 쉬웠습니다. 방법만 떠올리면 어렵지 않게 풀 수 있는 것 같습니다. 풀이 유익했던 한마디 처음 문제를 봤을 때는 이전에 풀었던 숨바꼭질을 생각해 BFS 풀이를 떠올렸다가, \(x\)와 \(y\)의 범위가

PS

[PS] BOJ 33870 / 빗질의 중요성

문제 링크: https://www.acmicpc.net/problem/33870 Thumbnail: Photo by charlesdeluvio (Unsplash) 애완견의 빗질은 항상 잊지 말고 해줍시다~ 풀이 구현 별다른 어려움 없이, 문제 조건을 그대로 구현하면 되는 문제였습니다. 다만, 답을 맞히기까지 여러 차례 시행착오를 겪었습니다.. 털 상태 관리 1일차부터 \(M\)일차 까지 강아지 1마리씩 골라 빗고, 만약 이전에

PS

[PS] BOJ 15654 / N과 M (5)

문제 링크: https://www.acmicpc.net/problem/15654 Thumbnail: Photo by Brett Jordan (Unsplash) N과 M은 유명한 백트래킹 시리즈입니다. 풀이 백트래킹 (DFS) 백트래킹도 결국은 DFS입니다. 다만, 분기에 진입하기 전에 조건에 맞는지 아닌지를 미리 판단해, 적합하지 않은 분기라면 진입하지 않고 건너뛴다는 차이점이 있습니다. 이번 문제에서는 \(N\)과 \(M\), 그리고 \(N\)개의

PS

[PS] BOJ 12851 / 숨바꼭질 2

문제 링크: https://www.acmicpc.net/problem/12851 Thumbnail: Photo by loong xu (Unsplash) 어느덧 이런 유형의 문제는 BFS로 푸는게 보이기 시작했습니다. 풀이 BFS BFS로 전체 구간을 탐색하면서, 다음 탐색할 노드로 [\(X - 1\), \(X + 1\), \(2 \times X\)]를 넣어주면 됩니다. 단, 다음에 탐색할 지점이 전체 구간 (\(0 \le

PS

[PS] BOJ 1235 / 학생 번호

문제 링크: https://www.acmicpc.net/problem/1235 Thumbnail: Photo by CX Insight (Unsplash) 풀이 '집합'을 이용한 풀이 집합이란, 동일한 원소가 중복되지 않는 컨테이너 자료구조입니다. (다른 원소를 저장할 수 있는 자료구조) 집합을 구현하는 방법은 이 글에서 다루진 않겠습니다. 이번 풀이에서는 파이썬에 내장된 set를 사용했습니다. 알고리즘은 다음과 같습니다.

PS

[PS] BOJ 19592 / 장난감 경주

문제 링크: https://www.acmicpc.net/problem/19592 Thumbnail: Photo by Jefferson Sees (Unsplash) 최대값 최댓값 어느 쪽이 맞는 표기인지 헷갈려서 찾아봤는데, 최댓값이 맞다고 합니다 ㅎㅎ 풀이 이게 왜 이분 탐색? ~ 한 조건을 만족하는 최대/최솟값을 찾는 형태의 문제들을 최적화 문제 라고 부릅니다. 그러나, 최적화 문제를 왜 이분 탐색으로 풀