알고리즘 문제 풀이 118

[백준] 16120 - PPAP

[문제링크] 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 0. PPAP문자열이란? - P에서 시작해 P를 PPAP로 치환한 문자열 - 반대로 PPAP를 P로 치환하다 보면 근본인 P로 돌아간다 1. PPAP는 P로만 치환되므로, A에만 집중하면 된다 2. A가 들어왔을때, 앞에는 반드시 P가 2개 이상 존재해야하고, 뒤에도 P가 하나 존재해야만 한다 3. 해당 조건을 위해, 앞에 등장한 P의 갯수를 세서 저장하고 있는다 (curIndex) - A가 들어올 때 curIndex가 2 이상이고, A의 뒤에도 P가 있다면 PPAP를 감지, P로 치환한다 - 결과적으..

[백준] 13904 - 과제

[문제링크] 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 0. 마감일까지 10일남은 과제를 오늘 하는건 괜찮지만, 마감일까지 하루 남은 과제를 10일뒤에 하는것은 불가능하다 - 가장 먼 마감일부터 그리디하게 최고 점수의 과제를 선택한다 1. 과제를 마감일 내림차순으로 정렬한다 2. 최고 점수의 과제를 빠르게 선택하기 위해 priority queue 사용 3. 각 날짜별로, 해당 날짜 마감의 과제를 priority queue에 넣고, 최고 점수의 하나만 꺼내서 누적한다 import java.io.BufferedReader; import java.io.I..

[백준] 1747 - 소수 & 팰린드롬

[문제링크] 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 0. 팰린드롬 수인지 판단하기 : 앞/뒤 양쪽에서 동시에 출발해, 한칸씩 이동하며 수가 같은지 비교 - 거의 O(1)에 가까운 복잡도를 가진다 1. 에라토스테네스의 체를 이용해 소수를 판별하면서, 소수에 대해서만 팰린드롬 여부를 판단한다 2. 입력 값 이상의 소수&팰린드롬이 발견되면 소수 판별을 종료하고, 출력한다 import java.io.BufferedReader; import java.io.InputStre..

[백준] 1342 - 행운의 문자열

[문제링크] 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 0. 주어진 문자로 만들수 있는 모든 순열 중, 조건을 만족하는 갯수를 구하는 문제 - 조건 1. 인접한 문자는 달라야 한다 - 조건 2. 최종 결과가 달라야 한다 (a 2개로 aa', a'a을 만들수 있지만, 둘은 같은것으로 취급한다) 1. 순열의 i번째 자리를 정할 때 이전 문자정보를 참고해 다른 문자만 사용한다면, 조건 1번은 해결할 수 있다 - 0번째 자리에서 참조할 값으로는 입력값(알파벳)이 아닌 아무 문자나 주면 된다 2. 조건 2번의 경우, ..

[백준] 9081 - 단어 맞추기

[문제링크] 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 0. C++ 등 일부 언어에서 내장 라이브러리로 제공하는 next permutation 문제 - 알파벳 순서대로 만들어진 조합의 다음 모습 구하기 1. next permutation을 구하는 방법은? 뒤에서부터 탐색해, 증가하지 않는 첫 부분의 위치를 구한다 126543 을 예시로 하면, 3-4-5-6-2-1 이므로 2가 구하려는 위치이다 다시 뒤에서부터 탐색해, 2보다 큰 수들 중 처음 나오는 수의 위치를 구한다 3-4-5-6-2-1 순..

[백준] 16234 - 인구 이동

[문제링크] 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 0. 국경선을 여는, 연합을 구한 다음, 연합 국가들의 인구를 공통 배분한다 - 더이상 연합이 형성되지 않을때까지 반복 1. L 이상 R 이하일때 진행하는 DFS로 연합과 그 인구를 구한다 - 인구는 DFS 결과로 반환, 연합은 tempMap 배열에 idx를 작성한다 2. 연합이 형성되지 않았다면, 즉 DFS가 호출된 횟수가 국가의 횟수와 같다면 종료 후 소요된 day 출력 3. 연합이 형성되었다면, 인구수를 골고루 분배해 갱신한다 (소..

[백준] 14503 - 로봇 청소기

[문제링크] 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 0. 단순한 구현 문제 - 2-b 수행하기 전 2-c,d먼저 조건 체크/수행해야한다 1. 현재 위치를 청소하며 clean 수치를 1씩 증가시킨다 2. 2-c,d 조건 체크를 위해 4방향 탐색 3. 4방향 다 벽/청소가 끝났다면 현 위치의 뒤를 확인하여 벽이라면 종료한다 (2-d) 4. 벽이 아니라면, 뒤로 물러난다 (2-c) 5. 왼쪽에 빈공간이 있다면, 회전 후 1칸 진행한다 (2-a) 4. 없다면, 회전한다 (2-b) import java.io...

[백준] 15685 - 드래곤 커브

[문제링크] 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 0. N세대 드래곤 커브란? N-1세대 드래곤 커브를 끝 점 기준 90도 회전시켜 N-1세대의 끝 점에 붙인 것 - 한 세대마다 2배씩 증가하지만, 세대가 최대 10이므로 최대 pow(2,10), 1024개의 지점으로 구성된다 1. N세대 드래곤 커브를 만들기 위해선? - N-1세대의 끝 점에서 시작해, N-1세대 커브의 구성을 역순으로 90도 회전시켜서 적용한다 - 예를들어, 위 2세대 커브는 →↑←↑ 순서로 이루어져 0,..

[백준] 1922 - 네트워크 연결

[문제링크] 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 0. 기초적인 MST 문제 (MST란?) 1. PRIM 알고리즘 사용, 최소 거리로 갈수있는 & 미방문한 노드 순서로 방문한다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception { Buff..

[백준] 1647 - 도시 분할 계획

[문제링크] 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 0. 집 사이의 연결을 유지하며 길을 제거하고, 최소 비용의 길들을 사용해 전체를 연결하기 == 최소 신장 트리(MST) 1. 최소 신장 트리를 구하면 최소 거리의 길들로 모든 마을을 연결할 수 있다 2. 완성된 MST의 간선들 중 하나를 제거하면 2개의 tree가 생성된다 - 마을을 2개로 분리할 수 있다 3. 길의 유지비의 합은 항상 최소를 유지해야하므로, MST를 이루는 간선들 중 가중치가 가장 큰 간선 하..