본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 10372번 : Alarm Clock https://www.acmicpc.net/problem/10372 10372번: Alarm Clock Output five characters in “hh:mm” format — the time shown on the clock in Alice’s dream. The time must be correct: 0 ≤ hh < 24 and 0 ≤ mm < 60. If there are many possible correct times, output any of them. If there is none, output “Impossible www.acmicpc.net brute force 문제였습니다. 📕 풀이방법 1. 0은 그림을 확인해보시면 6개의 획입니다. 1은 5, 2는 5... 이런식으로 9까지 획을 ..
(C++) - 백준(BOJ) 14501번 : 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp문제였습니다. 📕 풀이방법 1. 두 가지 선택 방법이 있습니다. 현재 상담을 선택하는 경우와 현재 상담을 선택하지 않는 경우입니다. 현재 상담을 선택하는 경우 그만큼의 이익이 있지만 상담기간동안 다른 상담을 못한다는 기회비용이 존재합니다. 따라서 선택하거나 선택하지 않을 경우에 대해 저울질해서 이익의 최댓값을 찾아야 합니다. 2. 현재 기간 + 현재 상담하기로 결정했을 때 걸리는 상담시간이 퇴사일보다 이하라면 현재의 상담을 하도록 선택할 수 있습니다. 점화식을 세워보면 다음과 같습니다. 먼저 d배열은 t일차에 얻을 수 있는 최대 ..
(C++) - 백준(BOJ) 13458번 : 시험감독 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 단순 수학 문제였습니다. 📕 풀이방법 1. 총 감독관은 1명만 있어야하므로 무조건 추가되어야 합니다. 2. 부 감독관은 몇 명이 있는지 상관없으므로 (a[i] - b) / c만큼 있으면 됩니다. * (a[i] - b) % c가 나머지가 있으면(양수면) 부 감독관을 한 명 더 배치해야합니다. * 총, 부 감독관이 감시가능한 학생 수 가 각각 ..
(C++) - 백준(BOJ) 4889번 : 안정적인 문자열 https://www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 문자열을 다루는 문제였습니다. 📕 풀이방법 문자열의 길이가 2000이므로 재귀적인 방법으로는 어렵다는 생각을 하게 되었습니다. 1. 입력을 받고 올바른 문자열들을 한 번 stack을 이용해 걸러줍니다. 2. 걸러진 문자열들 또한 길이가 짝수입니다. '{ }' 를 하나의 세트로 지웠기 때문입니다. 따라서 '{'와 '}'의 개수는 둘 다 짝수이거나 둘 다 홀수인 두 가지 경우뿐입니다. 즉, 홀수 ..
(C++) - 백준(BOJ) 1774번 : 우주신과의 교감 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 크루스칼 문제였습니다. 📕 풀이방법 1. 입력, 초기화 1-1. n만큼 좌표를 입력받습니다. 1-2. m만큼 이미 연결된 통로를 입력 받습니다. 이미 연결되어 있는 간선들은 트리형태로 구성되어 있습니다. 따라서 parent 배열을 이용해 union를 한다면 독립된 트리들이 한 개 혹은 여러개로 구성됩니다. 2. 서로 연결이 될 수 있는 후보간선들을 edges라는 변수에 ..
(C++) - 백준(BOJ) 16499번 : 동일한 단어 그룹화하기 https://www.acmicpc.net/problem/16499 16499번: 동일한 단어 그룹화하기 첫째 줄에 단어의 개수 N이 주어진다. (2 ≤ N ≤ 100) 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다. www.acmicpc.net 자료구조를 이용한 정렬문제였습니다. 풀이방법 1. 단어의 서순은 중요하지 않으므로 매 단어마다 사전순으로 정렬하여 그 결과를 key로 결정합니다. 이를 map에다 저장해줍니다. 2. 답 출력 : map의 size를 출력해줍니다. Code #include using namespace std; int n; map m; int main(){ cin >> n; for(int i = 0; i..
(C++) - 백준(BOJ) 11779번 : 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net dijkstra 문제였습니다. 풀이방법 1. 입력 : 도시의 개수가 노드가 되며 버스의 경로가 간선이 됩니다. 이 생각을 적용해 인접리스트로 그래프를 만들어줍니다. 2. 다익스트라를 수행합니다. 인접한 간선들중 최소를 찾을 때마다 역추적을위해 배열에 저장합니다. 현재 정점을 cur, 다음 정점을 next라고 했을 때 prev[next] = cur로 저장한다면 nex..
(C++) - 백준(BOJ) 20165번 : 인내의 도미노 장인 호석 https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net simulation, 구현 문제였습니다. 풀이방법 1. 현재 게임판에 대한 입력을 적절이 받고 매 라운드별 입력을 받습니다. 2. 공격의 행,열 좌표에 해당하는 도미노가 쓰러져있다면 아무일도 벌어지지 않습니다. 서 있다면 방향대로 쓰러뜨립니다. 판의 끝까지 순회하며 더 높은 높이가 있다면 지속적으로 갱신해주면서 도미노를 쓰러뜨립니다. 3. 수비수의 입력 좌표에 해당하는 도미노를 세워..

티스토리툴바