CVillain

문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한 사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i]..

다음 숫자들을 오름차순으로 정렬하시오. 2, 5, 4, 1, 3 선택 정렬은 가장 직관적인 정렬 방법이다. 숫자들 중 가장 작은 수를 제일 앞으로 보내는 방법으로 동작한다. 그림으로 살펴보자! 숫자들 중 가장 작은 1을 제일 앞의 2와 자리를 바꿨다. 가장 작은 자리를 찾았으니 다음으로 작은 숫자를 찾는다. 남은 숫자들 중에 가장 작은 2를 5와 교체한다. 다음 작은 수인 3과 4를 바꾼다. 마지막으로 4와 5의 자리를 바꾸면 오름차순으로 정렬된 것을 알 수 있다. 코드로 확인해보면, public class Main { public static void main(String[] args) { int[] arr = {2, 5, 4, 1, 3}; int min; for(int i=0; i

문제 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한 사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 풀이 내가 좋아하는 그래프 ..

문제 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제한 사항 입국심사를 ..

스프링과 객체 지향 스프링은 다음 기술로 다형성 + OCP, DIP를 가능하게 지원 DI(Dependency Injection) : 의존관계, 의존성 주입 DI 컨테이너 제공 클라이언트 코드의 변경 없이 기능 확장 쉽게 부품을 교체하듯이 개발 스프링이 없던 시절에는 좋은 객체 지향 개발을 하려고 OCP, DIP 원칙을 지키면 업무량이 너무 많아짐 → 그래서 아예 프레임워크로 만듬 순수하게 자바로 OCP, DIP 원칙을 지키면서 개발해보면, 결국 스프링 프레임워크(DI 컨테이너)를 만들게 됨 정리 모든 설계에 역할과 구현을 분리하자! → 자동차, 공연의 예시 인터페이스와 구현 클래스를 분리하자! 애플리케이션 설계도 공연을 설계 하듯이 배역만 만들어두고, 배우는 언제든지 유연하게 변경할 수 있도록 만드는 것..

문제 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한 사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 풀이 동적계획법(Dynamic Programmin..

문제 추석 트래픽 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 입력 형식 solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다. 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.s..

문제 올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요. 제한 사항 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수 풀이 보자마자 이게 왜 Level 4 문제지? 했다가 14번 테스트 케이스 때문에 골머리 앓았던 문제다. 처음 접근할 때 괄호 쌍이 나올 수 있는 경우의 수를 전부 백트래킹으로 탐색했다. 1 ~ 13번 테스트 케이스까지는 PASS했는데, 14번이 시간 초과가 났다. 검색해보니까 카탈란 수(Catalan number)라는 알고리즘을 사용하더라. ■ ..

정의 및 응용 n번째 카탈란 수(Catalan number) Cn이란 아래의 점화식을 만족하는 수열의 n번째 항을 말한다. $$ C_0 = 1, \quad C_n = \sum_{i=0}^{n} C_i C_{n-i}, \ n \geq 0. \tag{1.1} $$ 이 수열의 첫 10개 항을 나열하면 다음과 같다. (C0부터 C9까지) 1, 1, 2, 5, 14, 43, 132, 429, 1430, 4862, ··· 카탈란 수는 조합론(Combinatorics)에서 빈번하게 등장하는 수 중의 하나로, 아래와 같은 문제들의 해답이 모두 n번째 카탈란 수 Cn으로 주어진다. 먼저 C4= 14 라는 사실을 기억하자. Cn은 n쌍의 여는 괄호와 닫는 괄호로 만들 수 있는 올바른 괄호 구조의 가짓수와 같다. 예를 들어..

SOLID 클린 코드로 유명한 로버트 마팅이 좋은 객체 지향 설계의 5가지 원칙을 정리한 것 SRP : 단일 책임 원칙 (Single Responsibility Principle) OCP : 개방-폐쇄 원칙 (Open/Closed Principle) LSP : 리스코프 치환 원칙 (Liskov Substitution Principle) ISP : 인터페이스 분리 원칙 (Interface Segregation Principle) DIP : 의존관계 역전 원칙 (Dependency Inversion Principle) SRP, 단일 책임 원칙 Single Responsibility Principle 한 클래스는 하나의 책임만 가져야 한다. 하나의 책임이라는 것은 모호하다. 클 수 있고, 작을 수 있다. → ..