Problem Solving
1.[PS] 백준 13424번 비밀 모임
https://www.acmicpc.net/problem/13424Floyd-Warshall 알고리즘을 이용해 모든 정점간의 최단 거리를 구해 놓는다.그 후에 한 정점에 친구들이 모이는 거리를 구해서 더하면 한 정점에서 모이는 비용을 구할 수 있다.이 작업을
2.[PS] 백준 23559번 밥
https://www.acmicpc.net/problem/23559모든 경우의 수를 하려면 O(2 ^ n)이므로 브루트 포스로는 풀 수 없다.다만 이것을 알고리즘 문제가 아니라 자기자신이 밥먹을 계획을 세운다고 생각한다면 간단하게 풀이가 나온다!밥을 굶는 날이
3.[PS] 백준 10166번 관중석
https://www.acmicpc.net/problem/10166동심원의 선위에 좌석을 배치하는데, 각도가 같은 위치에 있는 좌석들은 맨 앞 좌석에 의해 가려진다.그래서 각 좌석의 각도를 구해놓고 비교해야 하는데, 소수로 나타내면 정밀도 문제로 비교할 수가
4.[PS] 백준 19951번 태상이의 훈련소 생활
https://www.acmicpc.net/problem/19951길이가 n인 일차원 배열에 흙 높이가 저장되어있다. a부터 b까지 k만큼 파내라/덮어라를 m번 수행한 후 흙 높이를 출력해야한다.1부터 n까지 k만큼 파내라/덮어라를 m번 수행하는 것이 최악의
5.[PS] 백준 17088번 등차수열 변환
https://www.acmicpc.net/problem/17088등차수열 변환 문제이다. n개의 숫자가 순서대로 주어지고 각 숫자에 최대 한 번의 연산을 수행할 수 있다. 연산은 1을 더하거나 뺀다. 주어진 수열을 등차수열로 변환하는 최소 연산횟수를 구하면
6.[PS] 백준 11066번 파일 합치기
https://www.acmicpc.net/problem/11066소설의 각 장(chapter)를 하나로 합치는데, 합치는 연산은 연속된 두 장을 하나로 합치는 연산이며 이 때의 비용은 각 장의 페이지 수이다. 총 장(chapter)의 수와 각 장의 페이지 수
7.[PS] 백준 2110번 공유기 설치
https://www.acmicpc.net/problem/2110집 N개가 수직선 위에 존재하고, 그 좌표가 주어진다. 각 집에 공유기를 설치한다고 했을 때, 공유기간 거리의 최소의 최대치를 구하는 문제이다.뒤집어서 생각해보자공유기간 거리의 최소를 정하고, 설
8.[PS] 백준 11049번 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049이전에 풀이했던 파일 합치기 문제와 유사하다.
9.[PS] 백준 17281번 ⚾
https://www.acmicpc.net/problem/172819명의 선수가 있는데, 각 선수가 각 이닝에서 어떤 결과를 낼 지 알고있다. 그리고 타순을 결정할 수 있다. 다만, 1번 선수를 4번 타자로 고정시키고 싶다.이 때, 가능한 최대 점수를 구하는
10.[PS] 백준 15683번 감시
https://www.acmicpc.net/problem/15683n \* m 크기 grid에 설치된 최대 8개의 cctv가 설치되어 있다. 또한, cctv의 종류는 5가지인데, 90도씩 회전할 수 있다. 벽이 존재하며, cctv는 벽너머를 감시할 수 없고 c
11.[PS] 백준 5430번 AC
https://www.acmicpc.net/problem/5430배열의 수를 뒤집거나 맨 앞의 수를 제거하는 연산을 수행한 후, 배열의 요소를 출력하는 문제이다. 배열을 진짜로 뒤집어버리면 약 100,000 (연산최대횟수) \* 100,000 (배열 최대길이)
12.[PS] 백준 3190번 뱀
https://www.acmicpc.net/problem/3190n X n 보드판위에서 뱀이 0행0열에서 오른쪽 방향으로 출발한다. 처음 몸 길이는 1이고 1초 뒤 현재 머리가 향하고 있는 방향으로 이동한다. 이동한 칸에 사과가 있다면 꼬리는 줄어들지 않는다.
13.[PS] 백준 1655번 가운데를 말해요
https://www.acmicpc.net/problem/1655숫자가 차례대로 하나씩 주어지고, 주어질 때마다 주어진 숫자 와 이전에 주어진 숫자의 중간값을 구하는 문제이다. 최소힙과 최대힙 두개를 이용해서 풀이하였다. 아래의 형태가 정렬된 상태로 유지되게
14.[PS] 백준 9935번 문자열 폭발
https://www.acmicpc.net/problem/9935최장 길이 1,000,000의 입력 문자열과 최장 길이 36의 폭발 문자열이 주어진다. 입력 문자열에는 폭발 문자열이 들어있을 수 있고, 폭발 문자열이 존재하는 경우, 입력 문자열에서 폭발 문자열
15.[PS] 백준 23288번 주사위 굴리기 2
https://www.acmicpc.net/problem/23288각 칸에 10미만의 자연수가 있는 2차원 배열(지도)가 주어진다. (1, 1)위치에서 주사위(1~6)를 동쪽방향으로 굴리는 것을 시작으로해서, 다음칸의 숫자와 주사위 바닥면의 숫자를 비교해서 주
16.[PS] 백준 14725번 개미굴
https://www.acmicpc.net/problem/14725개미 굴이 있다. 개미 굴에 로봇 개미를 보내면 로봇 개미는 굴의 아래층으로만 향한다. 아래층으로 향하며 더이상 내려갈 층이 없으면, 방문한 개미 굴 방에있는 먹이의 이름을 방문 순서대로 데이터
17.[PS] 백준 1600번 말이 되고픈 원숭이
https://www.acmicpc.net/problem/1600H x W 격자에서 (0, 0) 에서 (H - 1, W - 1)로 가는 최소 동작 횟수를 구하는 문제이다. 각 칸에서 가능한 동작은 아래와 같다.상하좌우로 이동한다. 장애물이 존재하는 칸으로는 이
18.[PS] 백준 5639번 이진 검색 트리
https://www.acmicpc.net/problem/5639임의의 이진 검색 트리(BST)가 있을 때, 이 BST에 대한 전위 순회 결과주어진다. 이 BST에 대한 후위 순회를 구하는 문제이다. 복습겸 BST를 설명하면 아래와 같다.노드의 왼쪽 서브트리에
19.[PS] 백준 2206번 벽 부수고 이동하기
https://www.acmicpc.net/problem/2206N x M 그리드로 표현되는 맵이 있고 각 칸이 이동 가능하면 0, 벽이 있어 이동이 불가능하면 1 로 이루어져 있다. (1, 1)에서 (N, M)의 위치까지 이동하는 최단 거리를 구하는 문제이다
20.[PS] 백준 2250번 트리의 높이와 너비
https://www.acmicpc.net/problem/2250이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그렸을 때, 각 레벨의 너비 중 최대 너비를 갖는 레벨과 그 너비를 구하는 문제이다. 1\. 이진트리에서 같은 레벨에
21.[PS] 백준 17471번 게리맨더링
https://www.acmicpc.net/problem/17471그래프가 주어지고, 그래프를 두 개의 그룹으로 분할해야 한다. 각 그룹에 속한 정점들은 같은 그룹에 속한 정점들끼리 간선으로 연결되어 서로 연결되어 있어야 한다. 그룹에는 하나이상의 정점이 포함
22.[PS] 백준 16236번 아기 상어
https://www.acmicpc.net/problem/16236N x N 격자 칸에 물고기와 아기 상어 1마리가 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 가장 처음에 아기 상어의 크기는 2이다. 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한
23.[PS] 백준 10830번 행렬 제곱
https://www.acmicpc.net/problem/10830N x N 행렬 A 가 주어졌을 때, A ^ B 의 각 원소를 1000으로 나눈 나머지를 출력하는 문제이다.이 때, B <= 100,000,000,000 이다.B가 매우 크다. 어떤 수의
24.[PS] 백준 2812번 크게 만들기
https://www.acmicpc.net/problem/2812N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하는 문제이다. 이 때, K < N <= 500,000 이고 주어지는 수는 0으
25.[PS] 백준 2234번 성곽
https://www.acmicpc.net/status?user_id=rhqjatn2398&problem_id=2234&from_mine=1그리드가 주어지고 각 칸의 네 방향에 벽이 있을 수 있다. 벽으로 둘러싸인 칸들이 하나의 방이 된다. 이 때, 이 성에
26.[PS] 백준 2042번 구간 합 구하기
https://www.acmicpc.net/problem/2042N(N <= 1000,000)개의 수가 순서대로 주어진다. 이 때 p ~ q번째 수 까지의 합을 구하는 연산과 x번째 수를 변경하는 연산이 있다. 이 떄, M + K (M <= 10,0
27.[PS] 백준 1766번 문제집
https://www.acmicpc.net/problem/17661번 부터 N번까지의 문제가 있다. 문제의 난이도는 1번이 제일 쉽고 그 다음이 2번, 3번, ..., N번이다. 다음 조건을 만족하는 문제 풀이 순서를 구하는 문제이다. N개의 문제는 모두 풀어
28.[PS] 백준 4195번 친구 네트워크
https://www.acmicpc.net/problem/4195 문제 설명 > 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 문제이다. '친구1 친구2' 이런 관계가 주어지면 친구1의 친
29.[PS] 백준 1727번 커플만들기
https://www.acmicpc.net/problem/1727남자 n명, 여자 m명이 있을 때, 최대한 많이 짝지어 준 후에 짝끼리의 성격 차의 합이 최소가 되게 하려 한다. 이 때 최소를 구하는 문제이다.도저히 풀 수 없어 풀이를 보고 말았다. 다이나믹
30.[PS] 백준 11404번 플로이드
https://www.acmicpc.net/problem/11404정점 n(n <= 100)개, 간선 m(m <= 100,000)개인 가중 그래프에서 모든 정점 간의 최단 거리를 출력하는 문제이다. 단, 가중치는 100,000이하의 자연수이고 도달하
31.[PS] 백준 21609 상어 중학교
https://www.acmicpc.net/problem/21609문제에 제시된 조건대로 블록그룹을 제거하다가 더 이상 제거 할 수 없게 되었을 때 그 때까지 획득한 점수의 합을 출력하는 문제이다.최대 점수 혹은 최소 점수를 구하는게 아니라 문제에 주어진 조건