1. DFS/BFS란? 1-1. 그래프 DFS/BFS에 대해 이해하려면 먼저 그래프의 기본 구조를 알아야한다. 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이 때 노드를 정점(Vertex)라고 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하며 두 노드가 간선으로 연결되어 있을 때 ‘인접하다’고 표현한다. 그래프는 크게 2가지 방식으로 표현할 수 있다. 인접 행렬(Adjacency Matrix) 인접 리스트(Adjacency List) 먼저 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 인접 리스트 방식은 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해서 저장한다. 인접 행렬 방식은 노드 개수가 많을수록 메모리가 불필요하게 ..
1. 우선순위 큐와 힙 우선순위를 부여하는 기준은 다양하다. 우선순위를 가진 원소를 삽입할 수 있고, 우선순위가 가장 큰 원소를 빼낼 수 있으면 우선순위 큐(Priority Queue)라고 한다. 우선순위 큐는 트리처럼 임의의 값을 가진 원소를 검색하는 기능은 필요 없고 가장 높은 것을 알려주고 삭제할 수 있으면 된다. 우선순위 큐도 선형 자료구조를 이용해서 구현할 수 있지만 더 효율적인 방법이 있다. 바로 힙(Heap)이다. 힙은 대표적인 우선순위 큐로, 완전 이진 트리 구조를 사용한다. 이진 트리: 모든 노드가 2개 이하의 자식을 갖는 트리 포화 이진 트리: 루트부터 모든 노드가 정확히 자식 노드를 2개씩 가지면서 꽉 채워진 트리 완전 이진 트리: 노드 수가 맞지 않아 포화 이진트리를 만들 수 없는 ..
1. 구현 알고리즘이란? 코딩 테스트에서 구현이란 “머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정”이다. 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이라고 할 수 있기 때문에 대부분 별도의 유형으로 분류하지 않는다. 하지만 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘보다 먼저 다루고자 한다. 2. 예제 💡 모든 문제는 나동빈 저자의 “이것이 코딩테스트다”에 수록되어 있으며 작성한 코드는 오류가 있을 수도 있음을 미리 밝힙니다. 2-1. 상하좌우 문제 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. .가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A..
1. 스택이란? 스택이란 가장 뒤에 들어온 데이터가 가장 먼저 나가는 구조의 자료구조다. 스택은 맨 위의 원소만 접근 가능한 것이 특징이며 맨 위의 원소를 스택 탑(top)이라고 한다. 새 원소를 삽입할 때는 스택 탑 바로 윗자리에 원소를 저장한 후 새 원소가 스택 탑이 된다. 그리고 원소를 삭제할 때는 무조건 탑에 있는 원소를 삭제한 후 바로 아래 원소가 스택 탑이 된다. 2. 배열 스택의 구현 public interface StackInterface { public void push(E newItem); public E pop(); public E top(); public boolean isEmpty(); public void popAll(); } public class ArrayStack imple..
1. 그리디 알고리즘이란? 그리디 알고리즘은 현재 상황에서 가장 좋은 것만 선택하고 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 문제 출제의 폭이 매우 넓기 때문에 단순 암기를 통해서는 모든 문제에 대처하기 어렵다. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 “가장 큰 순서대로”, “가장 작은 순서대로”와 같은 기준을 알게 모르게 제시해준다. 또한 대체로 정렬 알고리즘과 짝을 이뤄 출제된다. 2. 예제 💡 모든 문제는 나동빈 저자의 “이것이 코딩테스트다”에 수록되어 있으며 작성한 코드는 오류가 있을 수 있음을 미리 밝힙니다. 2-1. 큰 수의 법칙 문제 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열..
재귀란? 예를 들자면 n! = 1 X 2 X 3 X … X (n-1) X n 이고, 여기서 맨 끝의 n을 제외하면 (n-1)!이 된다. 즉 n! = n X (n-1)!이다. 이처럼 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다. 재귀 구조의 예 수열 초항이 1이고 공차가 3인 등차수열 public class Main { public static void main(String[] args){ int n = 5; System.out.println(seq(n)); } static int seq(int n) { if(n == 1) { return 1; } else { return seq(n-1) + 3; } } } 재귀 알고리..
