알고리즘 문제풀이
-
[백준/BOJ] 11047번 동전 0 (C++)알고리즘 문제풀이/백준 2021. 9. 12. 17:11
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전의 단위가 큰것부터 k를 나머지가 0이 될 때 까지 나누면 되는 문제이다. #include #include using namespace std; int coin[11]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, k, answer = 0; cin >..
-
[프로그래머스/위클리 챌린지] 5주차 (C++)알고리즘 문제풀이/프로그래머스 2021. 9. 7. 17:37
https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차_모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr word의 길이가 최대 n이므로 DFS를 이용하여 모든 경우의 수를 구할 수 있다고 판단했다. 3주차는 너무 어렵다... #include #include #include using namespace std; string s = "AEIOU"; vector v; void DFS(int len, string no..
-
[프로그래머스/Level 2] 거리두기 확인하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 8. 31. 16:28
https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 카카오 기출 입력값의 크기가 최대 5로 고정 되어 있어서 BFS를 이용한 완전 탐색으로 문..
-
[백준/BOJ] 18428번 감시 피하기 (C++)알고리즘 문제풀이/백준 2021. 8. 31. 15:30
https://www.acmicpc.net/submit/18428/32818300 로그인 www.acmicpc.net 14502번 연구소와 비슷했던 문제, DFS와 구현력을 요구하는 문제였다. #include #include #include using namespace std; int N; char map[7][7]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; bool flag; vector teacher, blank; bool canWatch(int nx, int ny, int dir) { while(1) { nx += dx[dir], ny += dy[dir]; if(map[nx][ny] == 'O' || nx = N || ny ..
-
[프로그래머스/위클리 챌린지] 4주차 (C++)알고리즘 문제풀이/프로그래머스 2021. 8. 30. 15:57
https://programmers.co.kr/learn/courses/30/lessons/84325 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 문자열 파싱, 정렬을 이용한 구현 문제 3주차는 도전중... #include #include #include #include #include using namespace std; int cmp(const pair &a, const pair &b) { if(a.second == b.second) return a.first < b.first; return a.sec..
-
[프로그래머스/Level 4] 무지의 먹방 라이브알고리즘 문제풀이/프로그래머스 2021. 8. 21. 16:00
https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 카카오 기출 시간이 적게 걸리는 음식부터 확인하는 그리디 접근 방식으로 해결한다. (우선순위 큐를 이용) [3, 1, 2] 3개의 음식이 있고 k가 5초라고 가정해보자 1. 가장 적게 걸리는 음식인 2번 음식을 빼는데, 음식이 3개 남아 있으므로 3(남은 음식의 개수) x 1(2번 음식을 먹는 시간) = 3을 빼준다. 이는 2번 음식을 다 먹기 위해 3초가 걸린다는 의미다. 결국 전체 남은 시간은 5 - 3 = 2초가 된다. 2. 남은 음식중에 가장 적게 걸리는 음식은 3번 음식을 빼야하는데, 전체 음식이 2개 남아 있으므로 2(남은..
-
[백준/BOJ] 1439번 뒤집기 (C++)알고리즘 문제풀이/백준 2021. 8. 19. 15:53
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 그리디 유형의 문제, 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우를 모두 구하여 횟수가 적은 경우를 출력한다. 이때 입력의 문자열이 전부 0 혹은 1인 경우는 바꿀 필요가 없으므로 예외처리를 해준다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); // 0과 ..
-
[백준/BOJ] 1766번 문제집 (C++)알고리즘 문제풀이/백준 2021. 8. 17. 16:14
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬을 이용하는 문제, 그러나 '가능하면 쉬운 문제부터 풀어야 한다.' 라는 조건을 만족하기 위해서 큐 대신 우선순위 큐를 사용한다. #include #include #include #include using namespace std; int N, M; int degree[32001]; vector graph[32001]; void topol() { priori..