코후닝

알고리즘 분류: 파싱 문제 링크: https://leetcode.com/problems/is-subsequence/description/ 【 문제 】 문자열 s와 t의 subsequence 인지 확인하는 문제이다. 【 풀이 】 문자열 s와 t의 길이가 0이면 true를 반환한다. 문자열 t를 순회하면서, s의 문자와 같은 문자가 나오면 idx를 증가 시킨다. idx가 s의 길이와 같아지면 s가 t의 subsequence 임을 의미하므로, true를 반환한다. t를 모두 순회했을 때, idx가 s의 길이와 같아지지 않으면 false를 반환한다. 시간 복잡도: O(n) 공간 복잡도: O(1) 【 코드 】 public class LeetCode_392 { public boolean isSubsequence(S..

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: 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] 가 될 ..

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 【 풀이 】 이 문제는 시작점이 여러 개로 주어질 수 있기 때문에, 여러 정점에서 동시에 출발할 수 있도록 해주어야 한다. 즉 모든 시작점(1) 들을 큐에 밀어 넣어서, bfs를 정점들마다 번갈아가면서 탐색할 수 있게끔 해주면 된다. 그리고 날짜를 기록하는 게 곧 탐색의 거리를 의미하기도 하기에 배열마다 거리..

알고리즘 분류: 분할 정복, 재귀 문제 링크: 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억이 넘어가기 때문이다. 따라서 이 문제는 분할, 정복으로 배열을 계속 쪼개가면서,..

알고리즘 분류: 분할 정복, 재귀 문제 링크: 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크기의 행렬로 표현되는..

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: 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..