입국심사 문제 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 ..
1. DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서..
1. DFS/BFS란? 1-1. 그래프 DFS/BFS에 대해 이해하려면 먼저 그래프의 기본 구조를 알아야한다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이 때 노드를 정점(Vertex)라고 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하며 두 노드가 간선으로 연결되어 있을 때 ‘인접하다’고 표현한다. 그래프는 크게 2가지 방식으로 표현할 수 있다. 인접 행렬(Adjacency Matrix) 인접 리스트(Adjacency List) 먼저 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 인접 리스트 방식은 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해서 저장한다. 인접 행렬 방식은 노드 개수가 많을수록 메모리가 불필요하게 ..
1. 우선순위 큐와 힙 우선순위를 부여하는 기준은 다양하다. 우선순위를 가진 원소를 삽입할 수 있고, 우선순위가 가장 큰 원소를 빼낼 수 있으면 우선순위 큐(Priority Queue)라고 한다. 우선순위 큐는 트리처럼 임의의 값을 가진 원소를 검색하는 기능은 필요 없고 가장 높은 것을 알려주고 삭제할 수 있으면 된다. 우선순위 큐도 선형 자료구조를 이용해서 구현할 수 있지만 더 효율적인 방법이 있다. 바로 힙(Heap)이다. 힙은 대표적인 우선순위 큐로, 완전 이진 트리 구조를 사용한다. 이진 트리: 모든 노드가 2개 이하의 자식을 갖는 트리 포화 이진 트리: 루트부터 모든 노드가 정확히 자식 노드를 2개씩 가지면서 꽉 채워진 트리 완전 이진 트리: 노드 수가 맞지 않아 포화 이진트리를 만들 수 없는 ..
문제 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. 입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109) 출력 첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다. 예제 입력 1 12 3 1 5 2 3 6 2 3 7 3 5 2 6 예제 출력 1 1 1 1 2 2 2 2 2 3 3 2 2 풀이 슬라이딩 윈도우 알고리즘을 사용했다. 연속된 L개의 숫자 중 최솟값을 출력하는 문제인데 정렬을 하지 않고 값을 비교하면서 데크에 넣어주면서 l..
문제 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 예제 입력 1 5 3 1 2 3 1 2 예제 출력 1 7 풀이 N의 최대 수가 106개이기 때문에 모든 구간 합을 매번 계산하면 제한 시간 안에 절대 통과할 수 없다. 따라서 ..
1. DI 1-1. DI란? (Dependency Injection) DI는 IoC라는 원칙을 구현하기 위해서 사용되는 방법 중 하나로 의존성 주입을 말한다. 지금까지는 우리가 직접 설정 파일을 통해 의존성 주입을 했는데 지금부터는 스프링에서 지원하는 DI를 위한 내용을 알아보자. 1-2. 스프링 컨테이너(Spring Container) 스프링 컨테이너는 내부에 존재하는 애플리케이션 빈의 생성, 관리 제거 등 생명 주기를 관리한다. 스프링 컨테이너는 XML, 애너테이션 기반의 자바 설정 클래스로 만들 수 있으며 서로 다른 빈을 연결해 애플리케이션 빈을 연결하는 역할을 한다. ApplicationContext라는 인터페이스를 스프링 컨테이너라고 한다. 정확히 말하면 BeanFactory와 BeanFacto..
1. 구현 알고리즘이란? 코딩 테스트에서 구현이란 “머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정”이다. 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이라고 할 수 있기 때문에 대부분 별도의 유형으로 분류하지 않는다. 하지만 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘보다 먼저 다루고자 한다. 2. 예제 💡 모든 문제는 나동빈 저자의 “이것이 코딩테스트다”에 수록되어 있으며 작성한 코드는 오류가 있을 수도 있음을 미리 밝힙니다. 2-1. 상하좌우 문제 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. .가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A..
2. AOP - Aspect? 관점? 핵심 관심사? 횡단 관심사? AOP는 Aspect-Oriented Programming의 약자이고, 이를 번역하면 관점 지향 프로그래밍이 된다. 스프링 DI가 의존성에 대한 주입이라면 스프링 AOP는 로직(code) 주입이라고 할 수 있다. 위 그림을 보면 입금, 출금, 이체 모듈에서 로깅, 보안, 트랜잭션 기능이 반복적으로 나타나는 것을 볼 수 있다. 프로그램을 작성하다 보면 이처럼 다수의 모듈에 공통적으로 나타나는 부분이 존재하는데, 바로 이것을 횡단 관심사(cross-cutting concern)라고 한다. 코드 = 핵심 관심사 + 횡단 관심사 핵심 관심사는 모듈별로 다르지만 횡단 관심사는 모듈별로 반복되어 중복해서 나타나는 부분이다. 남자와 여자의 삶을 프로그..
