1. 문제2635번 - 수 이어가기 2. 풀이수열의 전체 길이를 결정짓는 것은 두 번 째 항으로, 입력받은 첫 번째 수 N 만큼만 순회하면 되는 문제이다.N의 최대값은 30,000이므로 제한 시간 내에 풀이하는데는 문제 없으며, 가장 긴 수열을 찾았을 때 어차피 O(N)의 시간복잡도이므로 별도의 공간을 추가 할당하기 보다, O(N + 1)로 찾은 수열의 두 번째항을 넘김으로써 한 번 더 순회하며 출력하도록 구현하였다. 3. 소스코드더보기fun main() { val n = readln().toInt() var maxLength = 1 var ansIdx = 0 fun findSequence(prev: Int, next: Int, print: Boolean = false): Int {..

1. 문제https://www.acmicpc.net/problem/11366 2. 풀이앞선 두 년도의 오크 숫자가 누적해서 더해지는 구조로, 각 년도별 오크 수의 점화식을 세워보면 아래와 같다.년도오크 수1a + b2a + 2b32a + 3b43a + 5b55a + 8ba와 b의 차수가 각각 피보나치로 증가하는 구조이고, a의 차수는 b의 차수보다 하나 작은 것을 발견할 수 있다. 즉, 단일 피보나치 배열을 미리 생성해두고, 입력받은 쿼리에 따른 출력을 구현하면 O(N)에 처리할 수 있는 문제.가장 중요한 조건이자 검토해야할 사항은 입/출력의 범위가 Integer를 넘어서지 않는다는 것과, 오크가 한 마리도 없는 경우는 어떻게 할 것인가 라는 점이다.3. 소스코드fun main() { val fib..

1. 동시성 제어 왜 필요한 것일까?한정된 자원을 가장 효과적으로 사용해 낭비를 줄이는 경제적 효율성의 원리는 어김없이 서버에도 적용된다. 수 백, 수 천만에 이르는 사용자들의 요청을 1:1로 순차적으로 대응하는 것은 극히 비효율적이고 생산성이 떨어지기 때문에, 요청에 유연하게 대응하기 위해서는 '동시성'은 필연적으로 수반되어야 한다. 요청에 최적의 응답시간을 보장하기 위해 클라이언트 요청마다 스레드를 할당하거나 비동기 / 논블로킹 IO를 사용할 수 있는데, 이 때 공유자원(shared resource)에 대하여 서로 다른 두 스레드가 동시에 조회, 수정하는 일이 발생할 수 있다. 만약 공유 자원에 대한 접근을 제대로 제어하지 않는다면 API의 멱등성이 깨지고, 원치 않는 결과와 장애를 만들어낼 수 있기..

1. 문제 25496번: 장신구 명장 임스 첫 번째 줄에 정수 $P$와 정수 $N$이 공백으로 구분되어 주어진다. ($1 \le P \le 200$, $1 \le N \le 1\,000$) 두 번째 줄에는 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 200$) www.acmicpc.net 2. 풀이 욕심쟁이 알고리즘(Greedy Algorithm)을 통해서 풀이할 수 있는 문제로, 남아 있는 피로도를 어떻게 하면 가장 효과적으로 사용할 수 있을 것인가를 해결하는 것이다. 장신구를 제작하는데 드는 피로도가 작은 것을 최대한 먼저 제작한다면, 다른 장신구를 제작할 수 있는 문제로 분할할 수 있다. 따라서 입력받은 피로도를 작은 순서로 정렬하여, 순..

1. 문제 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 2. 풀이 '강산이는 휴가를 P일 중 L일만 사용할 수 있다'라는 것은 전체 V를 P로 나눈 몫에 L을 곱한 것만큼 휴가를 캠핑장을 사용할 수 있다는 말이다. 중요한 것은 V를 P로 나눈 나머지를 곧바로 더해주면 안된다는 점이다. (L < P) 이므로, V % P가 L보다 클 수 있다는 점을 놓치지 않아야 통과할 수 있다. 즉, min(V % P, L) 값을 추가로 더해주면 풀이할 수 있다! 3. 소스코드 더보기 public class Main ..

1. 문제 25513번: 빠른 오름차순 숫자 탐색 5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1, 2, 3, 4, 5, 6중 하나의 수가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c www.acmicpc.net 2. 풀이 전형적인 BFS를 통한 경로탐색 문제이며, 방문해야 하는 노드가 순차적으로 정해져 있는 형태의 문제다. 우선 보드가 5 x 5 로 작은 형태이므로 구현 자체에도 큰 어려움이 없을 것으로 생각된다. 다만, 이미 방문한 노드를 어떻게 다시 방문하지 않을 것인가를 판단하는 것이 중요한데, 대개 이러한 유형의 경우 3차원 배열로 방문배열을 선언하여 현재 탐색중인 idx 에서는 중복된 칸을 ..

1. 문제 12887번: 경로 게임 첫째 줄에 바꿀 수 있는 하얀색 칸의 개수의 최댓값을 출력한다. www.acmicpc.net 2. 풀이 문제가 다속 복잡해보이기 위해 노력했으나 사실 핵심을 간파하기는 쉬운 유형이다. 격자판의 하얀색 칸을 검정색 칸으로 바꾼 경우에도 왼쪽-오른쪽 경로가 존재할 수도 있다. 이때, 왼쪽-오른쪽 경로가 존재하면서 바꿀 수 있는 하얀색 칸의 최댓값을 구하는 프로그램을 작성하시오. 왼쪽-오른쪽 경로가 항상 존재하는 게임판만 입력으로 주어진다. 이를 다시 정리하자면, 좌측 끝에서 우측 끝으로 가는 경로에서 방문하지 않은 칸의 개수를 최대로 만들라는 말이며, 이는 곧 최소경로를 찾으라는 말과 동일하다. 그렇다면 우리는 아래의 과정을 통해서 본 문제를 풀 수 있게 된다. 입력과 동..

1. 문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 입력으로 제공된 카드들의 누적합을 최소로 만드는 경우의 수를 만들라는 문제다. 이는 Greedy로 접근이 가능한데 이유는 아래와 같다. a, b, c, d 총 네 개의 카드 묶음(a < b < c < d)이 있다고 가정해보자. 이 때, 먼저 만든 묶음은 또 다른 카드 묶음과 합쳐져야 하므로 한 번 더 더해져야 함을 의미한다. 즉, 더 큰 카드 묶음을 이용하여 새로운 묶음을 만들수록 큰 수가 중복해서 더해진다는 것을 의미한다. ..

1. 문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 크게 어려울 것이 없는 단순 구현문제다. 아래 풀이한 코드를 보면 충분히 흐름을 이해할 수 있을 것으로 생각된다. 다만, 해당 문제에서 가장 중요한 조건이 하나 있는데, 미세먼지 확산에 대한 것이다. 바로 미세먼지는 모든 칸에서 동시에 확산된다는 점인데, 이는 다시 말해 단순 반복문을 통해서 확산된 미세먼지가 동일한 쿼리 내에서 상호 영향을 주면 안된다는 얘기가 된다. 즉, 각 기준점의 확산량을 누적할 수 있는 별도의 배열을 선언해야 한다는..

0. 복습 다형성은 지연 바인딩(lazy binding) 매커니즘을 통해 구현된다 지연 바인딩: 메시지에 응답하기 위해 실행될 메서드가 컴파일 타임이 아닌 런타임에 결정되는 것 상속은 코드 재사용에 있어 가장 널리 알려진 방법이지만, 캡슐화의 측면에서 합성이 더 좋은 방법이다 유연한 객체지향 프로그램을 위해서는 컴파일 타임 의존성과 런타임 의존성이 달라야 한다 1. 들어가며 객체지향의 본질은 협력하는 객체들의 공동체를 창조하는 것으로, 객체지향 설계의 핵심은 협력을 구성하기 위해 적절한 객체를 찾고 적절한 책임을 할당하는 과정에서 드러난다. 기능을 구현하기 위해 어떤 협력이 필요하고 협력을 위해 어떤 역할과 책임이 필요한지를 고민하지 않은 채 이른 시기에 구현에 초점을 맞추는 것은 변경하기 어렵고 유연하..