유자의 코딩모험

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 배열의 ..

코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 단순 2진 암호코드를 응용한 문제다. [SWEA 1240] 단순 2진 암호코드 java SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 암호 코드가 주어졌을 때 정상인지 아닌지를 판별하는 문제다. 암호 코드는 총 woojeenow.tistory.com 문제풀이 전체적인 로직은 단순 2진 암호코드와 비슷하지만 다른 점이 3가지 정도가 있다. 입력이 2진수가 아닌 16진수로 주어진다. 암호코드의 비율이 아래 그림과 같이 n배로 입력될 수 있다. 한 테스트 케이스 당..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 암호 코드가 주어졌을 때 정상인지 아닌지를 판별하는 문제다. 암호 코드는 총 8개의 숫자로 이루어져 있고 앞 7자리는 상품 고유의 번호, 마지막 자리는 검증 코드를 나타낸다. "홀수 자리의 합 * 3 + 짝수 자리의 합 + 검증 코드"를 계산하여 10으로 나누어 떨어진다면 그 암호 코드는 정상이다. 직사각형 배열에 암호코드 정보가 포함되어 전달되고 배열은 1, 0으로 이루어져 있다. 여기서 암호코드를 찾아서 판별하는 방법은 다음과 같다. 그림에서 보면 모든 숫자들이 1로 끝난다. 한 줄씩 입력받을 때마다 오른쪽 끝에서부터 확인해서 1을 찾고 거기서부터 5..