유자의 코딩모험

21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 문제 문제를 간략히 설명하면 다음과 같다. 선생님이 정한 학생의 순서와 각 학생이 좋아하는 학생에 대한 정보가 주어진다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, | r1 - c1 | + | c1 - c2 | = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접하다고 한다. 즉, 상하좌우칸을 인접하다고 말하는 것이다. 학생의 자리를 정할 때는 지켜야 하는 규칙이 있다. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로..

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 코드

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제풀이 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다. 배추밭에 대한 정보를 담은 map 배열과 방문 여부를 표시하는 visited 배열을 초기화한다 배추가 심어져 있는 땅을 찾는다 DFS를..

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

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제풀이 오큰수 (Nearest Greater Element) Next Greater Element - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company inte..

11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 문제풀이 플로이드 와샬에 대한 자세한 내용은 아래 포스팅을 참고해주세요:) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm) 플로이드 와샬 알고리즘이란? '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘과의 차이점 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경 woojeenow.tistory.com 플로이드 와샬 알고리즘으로 각 파티장끼리의 최소 이동 시간을 구..

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제풀이 적록색약이 아닌 사람이 봤을 때의 구역수를 DFS로 구할 때 초록색인 구역은 빨간색으로 바꿔준다. 그리고 다시 적록색약인 사람이 봤을 때의 구역수를 DFS로 구해준다. C++ 코드