![]()
문제 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 문제 풀이 문제를 읽어보면 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 한다라고 적혀있다. 이를 통해 해당 문제는 선택지마다 최선의 선택을 해야 하는 그리디 문제이다. 항상 그리지 문제를 풀기전에 어떻게 최선의 선택을 도출할까 가 가장 고민되고, 어려운 부분이다. 배낭문제와 같이 보통의 그리디문제는 주어진 배열을 정렬해서, 최선의 선택을 하기 위한 사전작업을 한다. 입력받은 구간에..
![]()
문제 https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 문제 풀이 오랜만에 풀어본 그리디 문제였다. 그리디문제는 문제에서 요구하는 최적의 결과를 도출하기 위한 접근방법을 잘 생각해야 하는 것 같다. 버스 정류장을 지날 때마다 2가지 선택지가 있다. 멈춰서 연료를 채우거나, 그냥 지나가거나 따라서 나는 모든 정류장을 지나갈 때마다 2가지 선택지를 우선순위큐에 넣어줬다. 이렇게 해도 괜찮을거라 생각했던 이유는 우..
![]()
문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 풀이 골드 1이라는 난이도답게 BFS와 여러 가지를 섞었던 문제였다. 우선 문제의 핵심은 주어진 섬을 모두 연결할 수 있는 다리를 건설하는데 발생하는 최소비용을 구하는 것이다. 해당 문구를 통해서 섬이라는 정점을 모두 연결해야 하는 MST라고 유추할 수 있다. 원래 MST는 모든 정점을 연결하는 문제이지만, 해당 문제는 정점을 확대한 섬으로 계산을 해야 했기 때문에..
![]()
문제 https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 문제 풀이 정말 오래 걸렸던 문제다. 특정 테케에서 통과하지 못해서 많이 고생했다. 내가 생각하는 알고리즘 분류는 조합과 BFS를 같이 사용하는 문제인 것 같다. 배양액을 뿌릴 수 있는 땅에 대해서 빨간색,초록색,배양액X에 조합을 통해서 경우의 수를 정해준다. 사용한 자료구조 private lateinit var setting: Se..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258712 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제가 길고 설명이 장황하지만 LV1 문제답게 문제 흐름 그대로 쭉쭉 있어나가면 된다. 우선 해당 문제에서는 선물을 주고 받은 기록이 중요하다. 따라서 선물을 주고 받을 기록을 저장할 자료구조를 나는 2차원 배열로 설정했다. 인접리스트도 상관없지만 친구수가 50명밖에 되지 않기도 했고, 인덱스로 바로 접근할 수 있다는 장점이 컸던 것 같다. 인접리스트를 한다면 해당 인덱스의 친구..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음에는 방문한 정점의 개수와 간선을 바탕으로 그래프의 모양을 구하려고 했지만, 그래프의 크기를 측정할 수가 없었다. 생각해 보니 각 그래프의 특징이 있었고, 해당 그래프의 특징을 파악하면 풀 수 있는 문제였다. 도넛 그래프 도넛 그래프는 사이클을 형성하고 있으며 N-1개의 간선으로 구성되어 있기 때문에 모든 정점이 하나의 간선을 가지고 있다. 막대그래프 막대그래프는 간선마다 하..
