![]()
문제 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개를 사용해서 구할 수 있는 전력량의 합을 계산하기전에 배터리를 통..
![]()
문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 풀이 사실 대표적인 DP문제이다. DP 문제는 차근차근 손으로 할 수 있는 만큼 해보는 것이 좋다고 생각한다. n = 0인 경우 3*0의 크기의 벽을 채우는 경우의 수는 공집합이라는 느낌으로 1로 생각했다. n = 1인 경우 3*1 크기의 벽은 주어진 도형을 통해서 채울 수 없다. 직접 그려보면 알 수 있다. n = 2인 경우 3개의 모양으로 채울 수 있다. n = 3인 경우 dp 문제이기 때문에 그 전에 구했던 도형들을 최대한 이용해보려고 했다. 3*3의 사각형인 경우 3*2 사각형과 3*1 사..
![]()
고차 함수와 함숫값을 사용하면 함수가 객체로 표현되기 때문에 성능 차원에서 부가 비용이 발생한다. 이러한 부가 비용을 줄일 수 있는 해법이 Inline 기법이다. fun testInLine() { val time = 5 repeatInline(time) { println("inlie : $it") } } fun repeatInline(time: Int, action: (Int) -> Unit) { for (i in 0 until time) { action(i) } } fun main() { testInLine() } 코틀린 코드를 자바로 디컴파일해보면 아래와 같은 결과를 얻을 수 있다. public final class SolutionKt { public static final void testInLin..
![]()
문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 풀이 해당 문제는 소수에 대한 판별을 최적화할 수 있는지와 투 포인터를 알고 있는지를 묻는 문제라고 생각한다. 소수에 대한 판별은 학부생 때 에라토스테네스의 체를 이용해서 최적화하는 방법은 배웠었다. 이제 시간복잡도를 계산해보자. N*2에 해당하는 반복문 2개로, 연속된 소수의 범위를 설정해서 합을 구할 수도 있다. 하지만 N의 최댓값이 4,000,000이고, 그에 따른 소수의 개수는 알지 못해도 소수의 개수가 100,000개만 돼도 N^2이면 10,000,000,000이라 시간 초과가 난다. 따라서 해당..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 읽어보면 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 한다라고 적혀있다. 이를 통해 해당 문제는 선택지마다 최선의 선택을 해야 하는 그리디 문제이다. 항상 그리지 문제를 풀기전에 어떻게 최선의 선택을 도출할까 가 가장 고민되고, 어려운 부분이다. 배낭문제와 같이 보통의 그리디문제는 주어진 배열을 정렬해서, 최선의 선택을 하기 위한 사전작업을 한다. 입력받은 구간에..
