![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/u513o/btsGshtnGAn/5YeW46xh8Qm5i0BKi48kU0/img.png)
알고리즘: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/28422 28422번: XOR 카드 게임 XOR 카드 게임이란 $N$장의 카드 더미가 있을 때, 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져가 점수를 획득하는 게임이다. 이 게임에서 점수는 아래 단계를 거쳐 누적해서 획득할 수 있다. 한 www.acmicpc.net 【 문제 】 주어진 카드 n장 중 2장 혹은 3장을 카드가 0장이 될 때까지 뽑는다. 뽑은 카드에 적힌 숫자들을 XOR 연산한 뒤, 2진수 값으로 변환시켜 1의 개수를 구하고 점수로 더한다. 마지막에 1장의 카드가 남을 경우 최종 점수가 0점이 된다. 이때 점수의 최댓값을 구하는 문제. 【 풀이 】 1비트의 개수를 구하는 함수를 정의한다...
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/W4k4m/btsv7S5wy5I/RsRAF2rSmBJM7W6fTWztB1/img.png)
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 【 풀이 】 한층 밑으로 내려갈 때마다 각 칸에 맞는 경우의 수 중에 최솟값을 저장하고 마지막 값들 중 최솟값을 출력해주면 되는 문제이다. 최솟값을 계산해 저장하는 배열을 dp, 원본 배열은 rgb라고 하자. dp[0][0] = rgb[0][0] dp[0][1] = rgb[0][1] dp[0][2] = rgb[0][2] 가 될 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/cAsHLM/btsv7vaXVZO/C1W4ChuXrzBKVTkX2DqUXK/img.png)
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 【 풀이 】 이 문제는 시작점이 여러 개로 주어질 수 있기 때문에, 여러 정점에서 동시에 출발할 수 있도록 해주어야 한다. 즉 모든 시작점(1) 들을 큐에 밀어 넣어서, bfs를 정점들마다 번갈아가면서 탐색할 수 있게끔 해주면 된다. 그리고 날짜를 기록하는 게 곧 탐색의 거리를 의미하기도 하기에 배열마다 거리..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/VqW80/btswbB8PZ60/23OkvOwNLkkukH0kRXkgk0/img.png)
알고리즘 분류: 분할 정복, 재귀 문제 링크: https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 【 풀이 】 중학교 때 배운 좌표와 그래프에서 '사분면'이란 개념을 생각하면, 배열을 이용하지 않고도 쉽게 해결 가능하다. 일단 이 문제는 배열에 접근하는 식으로는 해결하기 힘들다. 이 문제에서의 최댓값인 2의 15 제곱은 32768이고, 32768의 제곱은 1억이 넘어가기 때문이다. 따라서 이 문제는 분할, 정복으로 배열을 계속 쪼개가면서,..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bVPUku/btsvXWk0L8m/nCmgweXUvVZZPNfKWRZFr1/img.png)
알고리즘 분류: 분할 정복, 재귀 문제 링크: https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 【 풀이 】 1780번과 거의 유사한 분할, 정복 문제이다. https://baehoon.tistory.com/62 [백준] 1780번: 종이의 개수 [C++] 알고리즘 분류: 분할 정복, 재귀 문제 링크: https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/coJOfK/btsvNsSEQH1/pxdn2jgzk8kNjPXl7H7tK1/img.png)
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 【 풀이 】 1차원 배열에서의 BFS 로 해결할 수 있는 문제이다. 수빈이의 현재 점(N) 부터 BFS 를 해서 +1, -1, *2를 했을 때 나오는 위치들을 모두 방문처리 해주고 그 위치에 도달했을 때의 시간을 따로 기록해주면 된다. 【 코드 】 #include #include using name..