PS

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

PS

[PS] BOJ 11689 / GCD(n, k) = 1

문제 링크: https://www.acmicpc.net/problem/11689 오일러 피 함수의 개념에 관한 문제입니다. 풀이 오일러 피($\phi$) 함수? 오일러 피 함수는 자연수 $N$에 대해 $N$과 서로소인 $N$이하의 자연수의 개수를 구하는 특수함수이다. 정의는 다음과 같다. $$\phi(N) = \vert {m: 1 \leq m \leq n, gcd(m, n)

PS

[PS] BOJ 2665 / 미로만들기

문제 링크: https://www.acmicpc.net/problem/2665 우선순위 큐를 활용한 BFS로 최단 거리를 찾는 문제입니다. 풀이 1) 우선순위 큐 기반 BFS 격자 그래프의 각 칸은 흰 방(1)이거나 검은 방(0)입니다. 흰 방만 통과할 수 있으며, 검은 방을 지나가려면 먼저 그 칸을 흰 방으로 바꾼 뒤 지나가야

PS

[PS] BOJ 2418 / 단어 격자

문제 링크: https://www.acmicpc.net/problem/2418 DFS로 가능한 모든 경우의 수를 세는데, 메모이제이션을 활용해야 합니다. 풀이 1) DFS 단어 격자에서 주어진 단어를 읽는 방법의 개수를 찾기 위해서는 그래프 탐색을 활용해야 합니다. 단, 같은 단어를 중복해서 방문할 수 있으므로 방문 여부를 기록하지 않습니다. 격자 그래프에서 8방향 (상하좌우 + 대각선)으로

PS

[PS] BOJ 22943 / 수

문제 링크: https://www.acmicpc.net/problem/22943 범위 안의 소수를 미리 구한 뒤, 백트래킹으로 가능한 경우의 수를 세면 됩니다. 풀이 1) 소수 찾기 주어진 범위 안의 소수를 찾기 위해서는, 에라토스테네스의 체를 사용하면 됩니다. 문제에서는 0~9까지의 서로 다른 $K$개의 수를 골라 사용하므로, $10^K$보다 작은 소수를 구하면

PS

[PS] BOJ 6549 / 히스토그램에서 가장 큰 직사각형

문제 링크: https://www.acmicpc.net/problem/6549 분할 정복으로 풀면 됩니다. 풀이 분할 정복 (Divide & Conquer) 분할 정복이란, 어떤 큰 문제를 작은 문제들로 계속 쪼갠 뒤 그 답을 합쳐서 전체 문제의 답을 계산하는 방법입니다. 이 문제의 경우도, 답을 구하려는 히스토그램의 범위를 절반씩 쪼개면서 풀고 그 답을 합칠 수

PS

[PS] BOJ 16956 / 늑대와 양

문제 링크: https://www.acmicpc.net/problem/16956 그래프 탐색으로 푸는 간단한 문제입니다. 풀이 아이디어 이 문제는 스페셜 저지 문제이며, 울타리를 최소한으로 설치해야 하는 문제가 아닙니다. 오로지 울타리를 적절히 배치해 늑대와 양이 만나지 못하게 할 수 있는지 판단하는 문제이니, 단순히 빈 칸을 전부 울타리로 바꾸는 방법을 생각했습니다. 1. 입력을 받으면서,

PS

[PS] BOJ 15671 / 오델로

문제 링크: https://www.acmicpc.net/problem/15671 구현 문제는 항상 재밌는 것 같습니다. 풀이 오델로? 6x6의 보드 판 위에서, 매 차례에 돌을 놓았을 때 상대의 돌을 자신의 돌로 감싸게 된다면, 자신의 돌로 감싼 상대의 돌을 모두 뒤집을 수 있는 게임입니다. 이렇게 서로의 차례를 반복하며, 보드판 전체를 자신의 돌로 만들거나,

PS

[PS] BOJ 32036 / 수열과 쿼리 45

문제 링크: https://www.acmicpc.net/problem/32036 아이디어를 도저히 떠올리지 못해서 다른 사람들의 풀이를 참고했습니다,, 설명을 이해하고 나니, 재밌는 문제였습니다. 풀이 문제 이해하기 길이가 $2 \times $ 109 + 1인 배열 $A$에는 -109 $\cdots$ 109까지의 각 인덱스에 0이 초기값으로 들어 있습니다. 이제, 다음의 두 쿼리로 배열 $A$를 조작합니다. 1.

PS

[PS] BOJ 18917 / 수열과 쿼리 38

문제 링크: https://www.acmicpc.net/problem/18917 간단한 구현 문제입니다. 풀이 쿼리의 종류 4가지의 쿼리를 수행하면 됩니다. 1. 배열의 끝에 새 원소 $x$를 추가하기 2. 배열에서 원소 $x$를 제거하기 * 여러 개 있다면 제일 앞의 원소를 제거합니다. 3. 배열의 모든 원소의 합을 출력하기 4. 배열의 모든 원소를 XOR한

PS

[PS] BOJ 18436 / 수열과 쿼리 37

문제 링크: https://www.acmicpc.net/problem/18436 세그먼트 트리를 활용해 구간 내 짝수와 홀수의 개수를 각각 저장해주면 됩니다. 풀이 세그먼트 트리? 세그먼트 트리에 대한 설명과 구간 합을 저장하는 세그먼트 이전 글을 참고해 주세요 😄 세그먼트 트리에 짝수/홀수의 개수 저장하기 가장 기본적인 세그먼트 트리의 구현은 구간 합을 저장하는 형태였습니다. 홀수와

PS

[PS] BOJ 30405 / 박물관 견학

문제 링크: https://www.acmicpc.net/problem/30405 아이디어만 떠올리면 구현은 쉬운 문제입니다. 풀이 모든 고양이의 이동 거리의 합을 최소로? 문제 입력에서 각각의 고양이가 박물관을 견학하는 순서를 주지만, 사실 고려할 필요가 없습니다. 어느 박물관을 출입점으로 정하던 각각의 고양이가 자신이 정한 순서로 박물관을 견학하는 총 거리는 항상 일정합니다. (출입문 ->

PS

[PS] BOJ 2357 / 최솟값과 최댓값

문제 링크: https://www.acmicpc.net/problem/2357 세그먼트 트리를 활용하는 기본적인 문제입니다. 다만, 구간 내 최솟값과 최댓값을 동시에 구해야 합니다. 풀이 세그먼트 트리? 세그먼트 트리에 대한 설명과 구간 합을 저장하는 세그먼트 이전 글을 참고해 주세요 😄 각 구간의 최솟값과 최댓값을 모두 구하기? 세그먼트 트리를 활용해 각 구간의 최솟값과 최댓값을 동시에

PS

[PS] BOJ 14428 / 수열과 쿼리 16

문제 링크: https://www.acmicpc.net/problem/14428 세그먼트 트리를 활용하는 기본적인 문제입니다. 다만, 세그먼트 트리에서 구간 내 최솟값이 아닌, 최솟값의 "인덱스"를 조회해야 합니다. 이를 위해 트리의 노드에 값을 어떻게 저장할지 고민이 필요했습니다. 풀이 세그먼트 트리? 세그먼트 트리에 대한 설명과 구간 합을 저장하는 세그먼트 이전 글을 참고해

PS

[PS] BOJ 10868 / 최솟값

문제 링크: https://www.acmicpc.net/problem/10868 세그먼트 트리를 활용하는 기본적인 문제입니다. 다만, 트리의 노드에 값을 어떻게 저장할지 고민이 필요했습니다. 풀이 세그먼트 트리? 세그먼트 트리에 대한 설명과 구간 합을 저장하는 세그먼트 이전 글을 참고해 주세요 😄 구간 합 대신에 최솟값 저장하기 이전에 구현했던 세그먼트 트리는 구간의 합을 저장했습니다. 이번 문제에서는

PS

[PS] BOJ 32160 / 숫자 놀이

문제 링크: https://www.acmicpc.net/problem/32160 애드 혹 문제입니다. 풀이 조금만 생각해보면, 답은 $N-1$ 또는 $N$으로 정해진다는 것을 알 수 있습니다. 답 구하기 칠판에 1부터 N까지의 수를 적고, 수를 지워가며 가장 마지막으로 남는 수가 최대가 되도록 하는 최선의 풀이는 다음과 같습니다: 1. 1부터 N-1까지의 수를 인접한 두

PS

[PS] BOJ 11505 / 구간 곱 구하기

문제 링크: https://www.acmicpc.net/problem/11505 세그먼트 트리를 활용하는 기본적인 문제입니다. 풀이 세그먼트 트리? 세그먼트 트리에 대한 설명과 구간 합을 저장하는 세그먼트 이전 글을 참고해 주세요 😄 구간 합 대신에 구간 곱 저장하기 이전에 구현했던 세그먼트 트리는 구간의 합을 저장했습니다. 이번 문제에서는 구간 곱을 1,000,000,007로 나눈

PS

[PS] BOJ 2268 / 수들의 합 7

문제 링크: https://www.acmicpc.net/problem/2268 세그먼트 트리를 활용하는 기본적인 문제입니다. 풀이 세그먼트 트리 (Segment Tree) 세그먼트 트리의 동작 과정과 예제를 함께 볼 수 있는 자세한 글을 BOJ BOOK에서 확인할 수 있습니다. https://book.acmicpc.net/ds/segment-tree 다음과 같은 문제를 생각해 봅시다. 크기가 N인 정수 배열 A가

PS

[PS] BOJ 1708 / 볼록 껍질

문제 링크: https://www.acmicpc.net/problem/1708 주어진 점들을 모두 포함하는 볼록 껍질(Convex Hull)을 구하는 문제입니다. 풀이 볼록 껍질(Convex Hull) 볼록 껍질이란, 주어진 점들을 모두 포함하는 가장 작은 볼록 다각형(또는 집합)을 말합니다. 이번 문제에서는 2차원 평면 상에 주어진 점들을 모두 포함하는 볼록 다각형을 말합니다.

PS

[PS] BOJ 16987 / 계란으로 계란치기

문제 링크: https://www.acmicpc.net/problem/16987 계란 프라이가 먹고 싶은 밤입니다. 백트래킹으로 가능한 모든 경우를 탐색해 최댓값을 찾으면 됩니다. 풀이 문제 조건 분석하기 계란으로 계란을 치는 과정은 다음과 같습니다. 1. 가장 왼쪽의 계란을 든다. 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에

PS

[PS] BOJ 3865 / 학회원

문제 링크: https://www.acmicpc.net/problem/3865 그래프 탐색을 응용하는 문제입니다. 풀이 파싱 + 그래프 탐색 파싱을 통해 유향 그래프를 만들어낸 뒤, 그래프 탐색으로 진출 차수가 0인 정점의 개수를 세면 됩니다. 1) 파싱 먼저, 입력 데이터는 다음과 같이 구성됩니다. N academy_name:member1,member2,...,memberK. ... (repeated N-1 times) $N$은

PS

[PS] BOJ 17436 / 소수의 배수

문제 링크: https://www.acmicpc.net/problem/17436 포함 배제의 원리를 이해하기에 적당한 문제입니다. 풀이 포함 배제의 원리? 포함 배제의 원리는 여러 개의 집합이 있을 때, 그 전체의 합집합의 크기를 구하는 방법을 말합니다. 이해하기 집합의 크기 = 집합에 속한 원소의 개수 집합 A의 크기는 $\vert A \vert$ 처럼 표기합니다. 간단하게 2개의

PS

[PS] BOJ 2252 / 줄 세우기

문제 링크: https://www.acmicpc.net/problem/2252 위상 정렬을 구현하는 정석적인 문제입니다. 풀이 위상 정렬? 위상 정렬이란, 순서가 정해져 있는 작업을 차례대로 수행하기 위해 그 순서를 결정해주는 알고리즘입니다. 방향 그래프에서, 모든 정점을 순서대로 방문하는 일직선의 순서를 찾는 방법이라고 생각하면 됩니다. 위상 정렬은 일반적으로 DAG (Directed Acyclic Graph)에만 적용

PS

[PS] BOJ 2468 / 안전 영역

문제 링크: https://www.acmicpc.net/problem/2468 Thumbnail: Photo by Amy Gatenby (Unsplash) 그래프 탐색을 활용하는 문제입니다. 이런 유형의 문제를 푸는 요령을 Flood-Fill이라고도 합니다. 풀이 아이디어 쌓인 비의 높이를 $H$라 할 때, $H = 1 \dots 100$에 대해 다음을 반복합니다. 1. 전체 격자 그래프를 순회하며, 높이가 $H$보다

PS

[PS] BOJ 5719 / 거의 최단 경로

문제 링크: https://www.acmicpc.net/problem/5719 Thumbnail: Photo by D koi (Unsplash) 다익스트라를 활용하는 문제인데, 아이디어의 구현이 어려웠습니다. : 풀이 아이디어 1. 다익스트라로 시작점 S에서 다른 모든 정점까지의 최단 거리를 구합니다. 2. 1에서 구한 최단 경로 중, S -> D의 최단 경로에 포함되는 간선들을 삭제합니다. 3. 다시 다익스트라로

PS

[PS] BOJ 13334 / 철로

문제 링크: https://www.acmicpc.net/problem/13334 Thumbnail: Photo by Irina Iriser (Unsplash) 우선순위 큐를 활용해 스위핑을 진행하는 문제입니다. 정렬 순서로 인해서 많은 고민을 했던 것 같습니다. 풀이 아이디어 먼저, 스위핑을 위해 입력을 정렬해줘야 합니다. 스위핑(sweeping) 알고리즘이란, 넓은 범위로 주어지는 입력을 정렬한 뒤 순차적으로 읽어가는 기법입니다. 입력 전처리