본문 바로가기

알고리즘

 (151)
[백준 / BOJ] 1060 좋은 수 (CPP) 문제 출처 : https://www.acmicpc.net/problem/1060 1060번: 좋은 수 정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 정수 www.acmicpc.net 정수 집합 S가 주어진다. 이때 다음 두 조건을 만족하는 범위[A,B]의 갯수가 적을수록 좋은 수 라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 이때, 좋은 수 n개를 좋은 수 순서대로(같다면 작은 수를 먼저) 출력하는 문제다. 풀이 문제 이해만 되면 풀이 생각하기는 쉬운 ..
[백준 / BOJ] 15823 카드 팩 구매하기 문제 출처 : https://www.acmicpc.net/problem/15823 15823번: 카드 팩 구매하기 첫 줄에는 두 개의 자연수 N과 M이 공백으로 구분되어 주어진다. N은 상점에 진열된 카드의 수이며 M은 주띵이가 구매해야 할 카드 팩의 수다. 이후 두 번째 줄에는 총 N개의 나열된 카드에 대한 www.acmicpc.net N개의 카드가 일렬로 진열되어 있다. 주띵이는 진열된 카드중에 몇개의 연속된 카드를 뽑아 하나의 카드팩을 만드는 방식으로 M개의 카드팩을 만들려고한다. 이때 카드팩은 모두 동일한 수의 카드가 들어가 있어야 하고 카드는 중복해서 뽑을 수 없으며 하나의 카드팩에 동일한 숫자의 카드가 들어갈 수 없다. 카드팩안에 들어갈 수 있는 카드의 최대 갯수를 구하는 문제다. 풀이 결정문..
[백준 / BOJ] 11780 플로이드 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net n개의 도시와 n개의 도시를 연결하는 m개의 버스가 있을때, 각 도시를 오가기위해 지불해야하는 버스의 최소비용과 이때의 경로를 구하는 문제다. 풀이 푸는데 2일이나 걸린 문제다.. 경로를 찾는과정에서 생각보다 어려움을 겪었는데, Java언어가 String을 이어붙이는 메커니즘상(Java는 String을 붙일경우 새로운 String객체를 생성한다.) 각 경로를 비교해가며 최단경로를..
[백준 / BOJ] 9655 돌 게임 (Java) 문제 출처 : https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net N개의 돌이 주어지고, 두명의 플레이어(상근, 창영)가 있다. 각 플레이어는 번갈아가며 돌을 가져가는데 자신의 턴마다 1개 혹은 3개의 돌을 가져갈 수 있다. 플레이어는 매번 최선의 선택을 한다고 가정했을때, 상근이가 이기는지 창영이가 이기는지 구하는 문제다. 전형적인 게임이론 문제다. dp배열을 dp[남아있는 돌의 수][turn] = 이긴 플레이어 와 같이 설정하고 자신이 이기는경우가 있다면 항상 그 경우를 선택하면 된다. 즉, 자신이 이기는 경우가 한번이라도 존재한다면, 절대로 지지 않는다.(매번 최..
[백준 / BOJ] 16564 히오스 프로게이머 (누적합 풀이) 문제 출처 : https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net N개의 캐릭터로 이루어진 팀이 있다. 이 팀의 팀 레벨은 팀의 가장 작은 레벨을 갖고있는 플레이어의 레벨과 동일하다. 팀의 플레이어의 레벨을 K만큼 올릴 수 있을때, 최대 팀 레벨을 구하는 문제다. 풀이 약간의 아이디어만 있으면 풀리는 문제였다. N과 K의 값이 커서 완전탐색으로 풀경우 시간초과가 나온다. 시..
[백준 / BOJ] 18809 Gaaaaaaaaaarden (Java) 문제 출처 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net N*M크기의 정원에 빨간색 배양액 R개 초록색 배양액 G개를 뿌린다. 배양액을 뿌릴 수 있는 위치는 R+G곳 이며, 배양액을 뿌린 위치는 매 초마다 인접한 영역으로 퍼져나간다. 서로 다른 색의 배양액이 동시에 만나면 꽃이 피며, 배양액은 사라진다. 이때, 피울 수 있는 최대 꽃의 개수를 구하는 문제다 풀이 조합과 BFS로 풀..
[백준 / BOJ] 5875 오타 문제 출처 : https://www.acmicpc.net/problem/5875 5875번: 오타 올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키 www.acmicpc.net 오타가 '최대 한번' 있는 괄호배열이 주어진다. 이 괄호배열의 괄호를 하나 조작하여 올바른 괄호 배열을 만드는 경우의 수 를 구하는 문제다. 풀이 어려웠던 문제다 누적합으로 풀었는데, 여는 괄호를 +1, 닫는괄호를 -1 이라고 하고 누적합 배열을 만들자. 예를들어, 괄호배열 ( ) 의 누적합배열은 {1, 0}, ( ( ) ) 의 누적합 배열은 {1, 2 ,1, 0}이 된다. 올바른 괄호배열이 여는괄호..
[백준 / BOJ] 20183 골목 대장 호석 - 효율성 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/20183 20183번: 골목 대장 호석 - 효율성 2 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 교차로 N개 교차로를 잇는 골목 M개(단, 골목에는 통행료가 존재한다.)가 주어진다. A교차로에서 B교차로로 갈때, 이 경로의 통행료 합을 C 이하로 만드는 경로중 통행료의 최댓값을 최소로 하는 경로를 구하는 문제다 풀이 전형적인 다익스트라 알고리즘으로 풀리는 문제였다. 알고리즘은 다익스트라를 사용하면 풀리기때문에 따로 설명할게 없고, 최소힙에 ..

티스토리툴바