Minjun Kim

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) 여러 시행 착오를 겪으며 풀었던 문제입니다. 백준 채점 서버에 문제가 있어 채점되는걸 오랫동안 기다렸습니다...ㅎㅎ 풀이 단계별로 계산하기 다음 과정으로 최대 개미의 수를 계산합니다: * 먼저, 쪽방이 있는 경우는 쪽방에 개미를 채우고 본 방(쪽방이 연결된 방)

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\)의 범위가