유자의 코딩모험

20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제풀이 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하는 문제다. 이중 for문으로도 해결할 수도 있지만 시간복잡도가 O(n^2)이기 때문에 시간초과가 발생할 가능성이 크다. 이럴 때는 투 포인터를 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다. 먼저 과정을 정리해보자면, 다음과 같다. left, right 모두 0에서 시작한다. cnt[arr[right]]이 K 미만이면 cnt 증가시키고 수열 길이를 갱신한 다음 right++..

2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제풀이 모든 육지에 대해서 BFS를 수행해서 각 육지에서 인접한 육지로 이동하면서 가장 긴 시간이 걸리는 육지를 찾는다. 각 육지의 최대 이동 시간을 비교했을 때 가장 큰 이동 시간이 보물이 묻혀 있는 두 곳 같의 최단 거리로 이동하는 시간이 된다. 코드 C++ 코드 Kotlin 코드

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제풀이 익은 토마토를 찾아서 BFS를 수행한다. 보통은 visited 배열을 쓰지만 이번에는 map 배열로 방문 여부를 표시해주었다. 0이면 방문하지 않았다는 의미이고 그 외의 경우에는 이미 방문했다는 의미이다. 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들의 값을 map[x][y] + 1로 수정해서 방문 표시를 한다. BFS가 끝난 후에는 전체 배열을 검사해서 익지 않은 토마토가 있는지 확인한다. 있다면 -1을, 없다면 map 배열의 ..

플로이드 와샬 알고리즘이란? '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘과의 차이점 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘으로 가장 적은 비용을 하나씩 선택한다. 하지만 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 모든 정점'을 기준으로 알고리즘을 수행한다. 알고리즘 위와 같은 그래프가 존재한다고 할 때, D는 각각의 정점이 다른 정점으로 가는 비용을 이차원 형태로 저장해놓은 것이다. 처음에는 위와 같은 상태이다. 이때 무한대는 이동하는 경로가 없다는 뜻이고 자신 자신의 비용은 0이다. D[x][y] = x에서 y로 가는 최소 비용을 의미한다. 거쳐가는 정점을 K라고 하자. X에서 Y로 가는 최소 비용과 X에서 노드 K로 ..

4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제풀이 문자열을 3등분해서 가운데 문자열에 해당하는 부분은 공백으로 바꾼다. end - start가 1이 되면 종료해주면 된다. C++ 코드

4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 문제풀이 처음에 문제를 읽고 어떻게 해야될지 한참 생각해도 잘 모르겠어서 다른 블로그 글을 참고했다. [백준 4256] 트리 예제로 트리 구조를 유추해보자. 전위 순회 : 3 6 5 4 8 7 1 2 중위 순회 : 5 6 8 4 3 1 2 7 전위 순회는 루트부터 시작하고, 중위 순회는 루트를 중심으로 왼쪽 서브트리, 오른쪽 서브트리로 나뉜다. 전위 baelanche.tistory.com 위 트리를 살펴보자. 전위 순회 : 3 6 5 4 8 7 1 2..

2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 동꿀오소리님 풀이 참고 [백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리 문제 donggoolosori.github.io 문제풀이 이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제이다. 위 트리의 인오더, 포스트오더, 프리오더를 살펴보자. 중위 순회 : 5 6 8 4 3 1 2 7 후위 순회 : 5 8 4 6 2 1 7 3 전위 순회 : 3 6 5 4 8 7 1 2 굵게 표시해놓은 것이 루트 노드이다. 후위 순회는 [왼쪽 ..