본문 바로가기

코딩테스트/백준28

[백준] 14502번 - 연구소 (골드 5) 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근 방식 지도 공간 중의 0인 위치를 찾아, 중복 되지 않고 3개의 위치를 선택한다. (순열) 해당 위치에 벽을 세우고 BFS로 바이러스를 확산시킨다. (4 방향) 모든 지도에 수행하면서 안전한 영역(0인 곳)이 가장 많이 남은 개수를 찾는다. 코드 #include #include #include #include #include #include using namespace std; void func_1.. 2022. 4. 21.
[백준] 1874번 - 스택 수열 (실버 3) 문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 방식 1~n 까지 오름차순으로 정렬된 num_vector, stack_vector, 원하는 수열을 입력 받을 target_vector 를선언한다. target_v의 각 요소들에서 num의 top(back)과 값을 비교한다. 같으면 다음 target으로 이동하고 다르면 하나씩 뽑아서 비교하면서 stack에 .. 2022. 4. 19.
[백준] 4963번 - 섬의 개수 (실버 2) 문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 접근 방식 BFS로 영역나누기, 8방향 검사 코드 #include #include #include #include using namespace std; int main() { int w = 1, h = 1; queue q; int direc[8][2] = { {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1} }; .. 2022. 4. 4.
[백준] 1920번 - 수 찾기 (실버 4) 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 접근 방식 정렬 후 이진탐색 구현 매개변수로 정렬된 벡터 전달 -> 10% 시간 초과 입출력 속도 개선 -> 10% 시간 초과 정렬된 벡터를 전역 변수로 접근(매개변수로 전달하는 과정에서 시간이 많이 걸릴 수 있다고 함) -> 통과 코드 #include #include #include #include using namespace std; vec.. 2022. 4. 4.
[백준] 1463번 - 1로 만들기 (실버 3) 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근 방식 다이나믹 프로그래밍 분류에 있는 문제이므로 점화식을 찾아 DP로 구현 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 위 규칙을 기반으로 점화식을 찾아보자. 가능한 연산과 규칙을 나열해보면 최종적으로 dp[n] = 1 + min(dp[n-1], dp[n/2], dp[n/3]) 이라는 점화식을 찾을 수 있다. 점화식의 의미는 현재 수에 대한 연산 횟수 증가(1) + 가능한 이전 연산 중 최소 값 ( min(...) ) 이다. 코.. 2022. 4. 4.
[백준] 10026번 - 적록색약 (골드 5) 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 접근 방식 기본 Map과 색약 Map을 만들어 BFS로 구역을 나눠줌 틀렸습니다. 코드와 정답 코드 차이 // 틀린 코드 if (map_visit[i][j] == 0) { q.push({i, j}); visit_value++; } // 정답 코드 if (map_visit[i][j] == 0) { q.push({i, j}); map_visit[i][j] = ++visit_value; }.. 2022. 4. 4.
[백준] 10773번 - 제로 (실버 4) 1. 문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 2. 접근 방식 Stack 활용 3. 코드 #include #include using namespace std; int main() { int test_case, tmp, sum=0; cin >> test_case; stack stack_zero; for (int i = 0; i > tmp; if (tmp==.. 2022. 3. 15.
[백준] 15829번 - Hashing (브론즈 2) 1. 문제 https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 2. 접근 방식 1차 : 문제에서 알려준 공식대로 구현 -> 50점, 작은 문자열에서는 잘 동작하지만 큰 문자열에서는 시간초과 2차 : 합동식 활용 A * B mod C -> (A mod C) * (B mod C) -> 통과 3. 코드 1차 코드 #include #include typedef unsigned long long ll; using namespace std; int main.. 2022. 3. 15.
[백준] 18111번 - 마인크래프트 (실버 2) 1. 문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 2. 접근 방식 1차 : 전체 블록의 평균(높이)을 구해서 해당 높이까지 블록을 맞춰주는 로직 작성 -> 틀림 2차 : 0~가장 큰 높이의 블록을 기준으로 각 케이스를 계산하여 가장 시간이 빠른 경우 선택 -> 1%에서 틀림 3차 : 위와 동일하지만 블록을 먼저 다 회수하고 설치 진행 -> 시간초과 4차 : 제거할 블록과 쌓을 블록의 개수를 구하고 시간을 나중에 구함 -> 통과 3. .. 2022. 3. 14.
[백준] 1009번 - 분산처리 (브론즈 3) 1. 문제 https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 2. 접근 방식 mod연산의 성질을 통해 큰 제곱수를 연산하지 않고 mod 값을 알아냄 빠른 모듈로 거듭제곱법을 적용함 3. 코드 #include #include using namespace std; typedef unsigned long long ll; int func_1009_mod(int a, int b) { vector tmp, tmp2; int *x; ll res = 1; while(b!.. 2022. 3. 10.
[백준] 삼성 SW 역량 테스트 기출 문제 (작성중) 1. URL : https://www.acmicpc.net/workbook/view/1152 문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon) www.acmicpc.net 2. 문제풀이 구슬 탈출2 (골드1) 2048(Easy) (골드2) 뱀 (골드 5) 시험 감독(브론즈 2) #include #include #include using namespace std; int main() { double n, tmp, b, c, sum=0; double sub_supervisor; cin >> n; vector exam_room; for (int i = 1; i > tmp; exam_room.push_back(tmp); } cin >> b >> c; for (auto exam : exam_room).. 2022. 2. 22.
[백준] 단계별로 풀어보기 > 그리디 알고리즘 (c++) 문제 1. 동전 0 가장 금액이 큰 동전부터 개수를 세면서 k원에서 차감해줌 k가 0이되면 동전의 개수를 출력 #include #include using namespace std; int main() { int n, k, tmp; map m; map::reverse_iterator reiter; cin >> n >> k; for (int i = 0; i > tmp; m[tmp] = 0; } for(reiter = m.rbegin(); reiter != m.rend(); reiter++) { while (reiter->first first]++; k -= reiter->first; } if (k second > 0) { tmp += reiter->second; } } cout.. 2022. 2. 20.
[백준] 단계별로 풀어보기 > 동적 계획법 1 (c++) 문제 1. 피보나치 함수 피보나치 f(n) 이 몇개의 f(0)과 f(1)로 이루어 져 있는지 출력하는 문제 점화식(?) { f(i).first, f(i).second } = { f(i-1).first+f(i-2).first, f(i-1).second+f(i-2).second } 을 찾음 #include #include #include using namespace std; int main() { int test_case; cin >> test_case; vector f; f.push_back({ 1, 0 }); f.push_back({ 0, 1 }); for (int i = 2; i > n[i]; cout 2022. 2. 16.
[백준] 단계별로 풀어보기 > DFS와 BFS (c++) 문제 1. DFS와 BFS #include #include #include #include #include using namespace std; void func_1260_dfs_recursion(int n, vector * graph, bool* visited) { visited[n] = true; cout > start_node; vector *graph = new vector[n+1]; bool *visited = new bool[n+1]; memset(visited, 0, sizeof(bool) * (n+1)); for (int i = 0; i > u >> v; graph[u].push_back(v); graph[v].push_back(u); } for (int i .. 2022. 2. 5.
[백준] 단계별로 풀어보기 > 정렬 (c++) 문제 1. 수 정렬하기 (브론즈 1) vector로 입력 받아 sort로 정렬 #include #include #include using namespace std; int main() { int a, num; vector v; cin >> a; for (int i = 0; i > num; v.push_back(num); } sort(v.begin(), v.end()); for (int i = 0; i > num; v.push_back(num); } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) { cou.. 2022. 1. 30.
[백준] 1011번 - Fly me to the Alpha Centauri (골드 5) 1. 문제 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 2. 코드 #include #include using namespace std; typedef unsigned long long ll; int main() { int int_case; ll x, y, res,distance, level; cin >> int_case; for (int i = 0; i .. 2022. 1. 29.
[백준] 단계별로 풀어보기 > 브루트포스 (c++) 문제 1. 블랙잭 (브론즈 2) #include using namespace std; int main(){ int n, m, sum, min, res = 0; cin >> n >> m; int* card = new int[n]; bool is_flag; for (int i = 0; i > card[i]; } sum = 0; min = m; is_flag = true; for (int i = 0; i < n - 1 && is_flag; i++) { for (int j = i + 1; j < n && is_flag; j++) { for (int k = j + 1; k < n && is_flag; k++) { sum = card[i] + card[j] + card[k]; if (.. 2022. 1. 26.
[백준] 15965번 - K번째 소수 (실버 2) 1. 문제 https://www.acmicpc.net/problem/15965 15965번: K번째 소수 자연수 K가 주어진다.(1 ≤ K ≤ 500,000) www.acmicpc.net 2. 코드 #include #include using namespace std; bool *Sieve_of_Eratosthenes(int m) { bool* arr = new bool[m + 1]; memset(arr, 1, sizeof(bool) * (m+1)); arr[0] = false; arr[0] = false; for (int i = 2; i < m + 1; i++) { if (arr[i] == true) { for (int j = i * 2; j < m + 1; j += i) { arr[j] = false;.. 2022. 1. 25.
[백준] 단계별로 풀어보기 > 재귀 (c++) 문제 1. 팩토리얼 #include using namespace std; int func_10872_factorial(int n) { if (n == 0) return 1; else return n * func_10872_factorial(n-1); } int main() { int a; cin >> a; cout > a; cout 2022. 1. 25.
[백준] 단계별로 풀어보기 > 기본 수학 2 (c++) 문제 1. 소수찾기 #include typedef unsigned long long ll; using namespace std; int is_prime_number_custom(ll input) { if (input a; int* arr = new int[a]; for (int i = 0; i > arr[i]; if (is_prime_number_custom(arr[i])) { cnt++; } } cout a >> b; for (int i = a; i h; if (min > h - y) min = h - y; cout > a >> b; if (x.count(a)) x[a]++; else x[a] = 1; i.. 2022. 1. 19.

티스토리툴바