문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 문제 풀이 문제를 읽고 누적합을 구해서 소형차를 배정하는 문제인 것 같았다. 문제에서 주어진 테스트케이스에 대해서 먼저 누적합에 대한 그림을 그려보았다. 처음으로 접근한 방법은 정해진 구간까지의 최대 누적합을 구하는 방법으로 접근했다. 예를 들어 50까지 접근했을때의 최댓값은 40과 50을 태운 90이다. 다음으로 10까지 접근했을때의 최댓값은 40과 50을 태운 90 vs (35+40..
문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 이전의 선택한 색에 따라 다음 선택이 영향이 받는 문제였고, 배낭 문제와 굉장히 유사하게 느껴졌다. 배낭 문제와 같이 물건을 담으면서, 해당 물건을 담을 경우와 담지 않을 경우를 나눠서 계산하는 것처럼 해당 문제도 색깔을 선택할 경우와 선택하지 않을 경우를 나눠서 계산하는 문제였다. 우선 그림을 그려가면서 가장 먼저 발견한 조건은 k가 n의 절반보다 크다면 경우의 수는 0이라는 점이다. 이는 문제에서도 ..
Contract 1.3.60 버전부터 사용되었으며, 컴파일러가 이해할 수 있게 명시적으로 자신의 동작을 설명할 수 있게 한다. 컴파일러가 이해할 수 있게 라는 말이 조금은 헷갈릴 여지가 있다고 생각한다. 코드를 통해 살펴보자 회원가입을 구현하려고 할 때의 시나리오를 생각해 보자. @JvmInline value class Password(val password: String) @JvmInline value class Id(val id: String) fun validate(id: Id?, password: Password?): Boolean { return id != null && password != null } fun signUp(id:Id?, password: Password?){ if(validat..
문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 풀이 문제의 분류가 위상정렬인 줄 모르고 풀었다. 어쩌다 보니.. 위상정렬처럼 풀었다. 단순하게 입력단계에서 A와 B를 구분하는 과정에서 B로는 들어왔지만 A로 한 번도 들어오지 못한 녀석이 맨 뒤에 서야한다는것은 알았다. 입력에 대해서 도식화를 해보면 오른쪽과 같은 관계도가 나온다. 그림을 통해서 3가지 분류를 할 수 있다. 선택을 받지 못한..
문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 풀이 처음에는 점 하나를 잡고 탐색을 해서 정사각형을 판별하는 문제로 생각했는데, n과 m이 각각 1000이라 모든 점에 대해서 탐색하기가 무리가 있었고, 그 점에 대한 정사각형을 판별하는 과정도 굉장히 문제가 있었다. 그러다 무작정 그림을 그리다 보니 규칙을 발견할 수 있었다. 정사각형이란 모두 1로 이루어져야 하고, 가로와 세로의 길이가 같아야 한다. 하나의 점에서 2x2의 정사각형인지 판단하는 방법은 간단했다. 3가지 방향에 대해서 0이 없어야 한다...
등장 배경 원시타입과 문자열을 wrapping 하기 위해 사용했던 데이터 클래스와 클래스는 추가적인 객체 생성과 메모리 할당이 필요했다. 하지만 value class가 추가되면서, 객체 생성 및 메모리 할당을 최소화하고 성능을 개선할 수 있게 되었다. kotlin 1.5에서는 inline class로 사용되었지만, 현재는 Deperecated 되었다. 현재 1.6에서는 value class로 사용하고 있다. 정의 primitive 타입이나, 다른 value class를 감사는 wrapper 클래스로서의 역할을 할 수 있다. 특징 상속이 불가능하다 @JvmInline value class Email(private val email:String) value class SchoolEmail(private va..
문제 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 문제 풀이 확률과 통계를 하셨던 분이라면 자주 접했을 문제라고 생각합니다. 바로 도로를 주고, 도로를 통해 이동할 수 있는 경우의 수를 계산하는 문제입니다. 문제의 특이한 점은 이동하지 못하는 도로를 만들어서, 경우의 수를 제한한다는 점입니다. 확률과 통계에서 풀었던 것처럼 기본적으로 맨 위와 맨 왼쪽은 경로의 수가 1로 고정입니다. 최단 거리의 경우는 직진으로 갈 수밖에 없..
문제 https://www.acmicpc.net/problem/27210 27210번: 신을 모시는 사당 칠할 수 있는 돌상의 개수에 제한은 없으며, 반드시 연속한(인접한) 돌상들만 칠할 수 있음(띄엄띄엄 칠할 수 없음)에 유의하라. www.acmicpc.net 문제 풀이 같은 방향의 돌상의 길이가 가장 큰 구간을 구하는 전형적인 누적합 문제였습니다. 나는 두 개의 변수를 사용해서 각기 다른 돌상의 개수를 계산했습니다. 왼쪽 돌상의 개수를 left, 오른쪽 돌상의 개수를 right로 관리했습니다. 입력을 탐색하면서, 왼쪽 돌상이라면 left ++, right -- 오른쪽 돌상이라면 right++, left--를 해줬습니다. 추가적으로 우리는 연속적인 구간의 최대합을 원하기 때문에 left와 right가 ..
문제 https://www.acmicpc.net/problem/28082 28082번: 기계오리 연구 인하대학교 기계공학과의 기계오리 연구실에서는 2023년 버전 기계오리를 완성하기 위해 실험을 진행하고 있다. 실험 도중, 기계오리에 1개 이상 $K$개 이하의 배터리를 삽입하면 기계오리가 언 www.acmicpc.net 문제 풀이 대표적인 DP유형 중의 한 문제였던 것 같다. 나는 항상 DP 문제를 풀 때 처음에는 dp 배열을 2차원으로 접근하려고 한다. N개의 배터리중에서 배터리를 최대 k개 사용해서 만들 수 있는 전력량의 합을 목표로 점화식을 세워보기 전에 그림으로 그려보자. 주어진 예제를 바탕으로 간단하게 그림을 그려보았다. 최대 k개를 사용해서 구할 수 있는 전력량의 합을 계산하기전에 배터리를 통..
