Algorithm

[백준 1644] 소수의 연속합 C++

1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 수학, 두 포인터, 정수론 1. 문제풀이 아이디어 에라토스테네스의 체를 이용해서 N까지의 소수를 배열에 순서대로 저장한다. 배열의 마지막 소수를 ed 포인터, 그 이전 소수를 st포인터로 지정 st와 ed까지의 소수의 합을 sum으로 지정 처음에 sum = Prime_list[ed] + Prime_list[st]의 값으로 하고 sum > N이면 st와 ed가 같아질 때까지 sum -= Prime_list[ed]; ed--; 를 수행한다. st와 ed가 같아지면 st--; sum -= Prime_list[st]를 수행한다. (*순서중요!!) sum == N 이면 result++; 하..

[백준 1300] K 번째 수 C++

1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 이분 탐색 1. 문제해결 아이디어 일단 n이 최대 100000 이므로 B배열을 실제로 만들어 주는건 불가능하다. i번째 행은 i의 배수의 집합임을 이용하자 N = 5, K = 17 이 주어졌을 때. 이 문제를 이분탐색으로 풀기 위해서 5x5의 절반인 12를 최초 mid로 설정하자(lo = 0, hi = 25) 12는 위 표에서 몇 번째일까? 1행은 모두 12보다 같거나 작다 -> cnt += 5 2행도 모두 12보다 같거나 작다 -..

[백준 2146] 다리만들기 C++

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 그래프 탐색, BFS 삼성전자 A형 기출문제 1. 문제풀이 아이디어 각 섬을 BFS로 돌면서 해당 섬의 경계좌표를 찾아서 저장한다 섬 간의 거리(경계좌표간의 거리)를 모두 찾아보면서 최솟값을 구한다 2. 코드 설명 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51..

[백준 2239] 스도쿠 C++

2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 백트래킹 1. 문제풀이 아이디어 브루트포스 + 백트래킹 문제이다 현재 칸이 '0' 이라면 1 ~ 9까지의 숫자를 모두 대입해 보고, 대입한 숫자가 현재 칸에 들어가도 되는지 확인한다. 현재 칸에 모든 숫자가 들어갈 수 없다면 현재 칸을 다시 0으로 만들고 이전 칸으로 돌아간다. 현재 칸이 '0'이 아니라면 다음 칸으로 넘어간다. 2. 코드 설명 ~ 숫자를 입력 받아 Map 배열에 넣는다. ~ Map 상태를 보여준다. ~ 현재 칸에 들어있는 숫자를 넣어도 룰..

[백준 2449] 전구 C++

2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 1. 문제풀이 아이디어 전구를 A, B 두 부분으로 나누고, A의 시작 지점의 색깔과 B의 시작 지점의 색깔을 재귀적으로 같게 한다면 A, B 모두 같은 색이 될 것이다.. - A부분의 색을 같게 하는데 필요한 작업의 수 + B부분의 색을 같게 하는데 필요한 작업의 수 + 현재 A, B의 첫 번째 전구의 색을 같게 하는데 필요한 작업의 수 2. 코드 설명 dp[st][ed] : 전구 배열에서 st부터 ed까지의 전구를 모두 같은 색으로 맞추는데 필요한 ..

[백준 1700] 멀티탭 스케줄링 C++

1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 그리디 알고리즘 OS page replacement policy 중 하나인 Optimal replacement policy 를 적용하는 문제이다. 미래에 어떤 작업을 할 지 다 알고있는 경우이므로 적용이 가능하다 -> 가장 나중에 사용될 작업을 현재 멀티탭에서 뽑는다 (2021/05/16 update) 이 문제에서도 특정 조건이 부합하는지만 알면 언제나 최적의 해를 구할 수 있다 특정 조건을 찾는게 많이 어려웠음.. 특정 조건 : ex) 3구짜리 멀티탭이 있고 ..

[백준 1799] 비숍 C++

1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹 연습하기 #4 1. 문제풀이 아이디어 비숍의 특징 : 체스판의 검은 칸에 있는 비숍과 흰색 칸에 있는 비숍은 서로 아무 영향을 끼칠 수 없다. 이 문제를 정석적인 백트래킹으로 푼다면 시간 복잡도는 O(2^(N*N))이 된다.. 체스판에 모든 곳에 비숍을 놓을 수 있고 N=10이면 각각의 칸마다 ( 비숍을 놓는다 or 놓지않는다 ) 2가지의 경우가 생기므로 2^100가지의 경우를 모두 탐색해야한다 2^100 = 1.2676506e+30 이므로 참신한 방법이 필요하..

Minimum Spanning Tree (MST) - Kruskal

크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인드(Union-Find)에 대한 이해 8할 Edge 구조체 설계 2할? find_topnode() 를 통해서 현재 정점(Vertax)의 최상단 노드(부모노드) 를 알 수 있다. Node[Vertax]의 값이 음수이면 Vertax가 부모노드임을 의미한다 is_cycle()을 통해서 a와 b 정점이 서로 같은 노드인지 확인한다(find_topnode() 사용) Union_node()를 통해서 a 와 b정점을 하나로 병합한다 a, b정점의 부모 노드가 가지는 값은 항상 음수이다. 값이 더 작을수록 더 많은..

[백준 10026] 적록색약 C++

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net BFS 연습 #1 전형적인 BFS 탐색 문제이다 색약인 경우에 'R' 과 'G' 를 같다 생각하고 탐색하게 해주면 문제없이 풀 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 6..

[백준 14499] 주사위 굴리기 C++

14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 주사위가 굴러가는걸 내가 어떻게 아냐고.. 라고 처음에 생각했었는데 생각보다 할 만했던 문제였다 삼성 역량평가는 물체가 좌표상에서 움직이는 시뮬레이션 문제가 정말 주된 유형인듯하다 주사위가 굴러가는걸 어떻게 표현할까? 문제에 그려져 있는 주사위 평면도를 보고 풀이방법을 떠올릴 수 있었다.. 저게 없었으면 못풀었을지도 dice[i] 는 i번 면에 적힌 숫자를 의미한다..