boj

[백준 2143] 두 배열의 합 C++

2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 이분 탐색 1. 문제해결 아이디어 문제에서 정의된 부 배열의 최대 크기는 N(N+1)/2 가 됨을 알 수 있었다. (1~N까지의 합) N, M이 최대 1000이므로 부 배열의 크기는 최대 500,000 이다. 따라서 배열에 담은 후 nlogn 연산이 충분히 가능함을 알 수 있었다. 이분 탐색을 수행하기 위해 subB배열을 정렬한다. T 에서 subA의 원소를 뺀 값이 subB에 있는지 ..

[백준 16929] Two Dots C++

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net DFS 1. 문제해결 아이디어 DFS를 통해서 사이클을 찾는 문제이다. 시작 알파벳과 같은 칸만 이동하며 시작 좌표에 다시 돌아올 때까지 or 돌아오지 못할 때까지 dfs 를 돌린다. 하나의 dfs루프에서 방문한 점을 backtracking 하지 않고 방문처리 기록을 남겨둔다. 2. 코드 : dfs를 돌면서 방문을 했거나 시작점으로 지목된 점에 방문을 한 경우 + 현재 점이 시작점이 아닌경우 (시작하자마자 return 되는것 방지) 1 2 3 4 5 6 ..

[백준 1309] 동물원 C++

1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 기초 1. 문제풀이 아이디어 row행에서 사자를 놓는 모든 경우의 수 = row행에 사자를 놓지 않는 경우 + row행의 1번에만 사자를 놓는 경우 + row행의 2번에만 사자를 놓는 경우 row행에 사자를 놓지 않는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만 사자를 놓는 경우 + row+1행의 2번에만 사자를 놓는 경우 row행의 1번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 2번에만 사자를 놓는 경우 row행의 2번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만..

[백준 17298 17299] 오큰수 , 오등큰수 C++

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 자료구조, 스택 문제 1. 문제풀이 아이디어 N이 최대 1,000,000이므로 단순히 2중 for문으로 해결하는건 시간제한에 걸리게 된다. (N이 최대 5,000 정도면 가능할듯..) (1) 오큰수 1. 스택이 비어있을때 지금 보는 배열의 원소와 원..

[백준 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구짜리 멀티탭이 있고 ..