Stack (스택) Stack stack = new Stack(); 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 후입 선출 (LIFO) 구조 입구와 출구가 단 하나 연산자 push(data) : 데이터 삽입 pop() : 가장 마지막 데이터를 반환 (제거O) peek() : 가장 마지막 데이터를 반환 (제거X) empty() : 비어있는지 확인 search(data) : 주어진 데이터를 찾아 위치를 반환 (없을 경우 -1 반환, 1부터 시작) Queue (큐) Queue queue = new LinkedList(); 한 쪽 끝에서 데이터가 삽입되고, 다른 한 쪽 끝에서는 삭제되는 선입 선출 (FIFO) 구조 임시로 자료를 저장하거나 버퍼와 같은 경우에 주로 사용하는 자료구조 형태 LinkedList를 사..
순열 서로 다른 n개 중 r개를 뽑아서 정렬 하는 것 즉, 순서가 있어 순서가 다르면 다른 것으로 카운팅함 AB != AB // int[] arr : 원본 배열 // int[] out : 출력 배열 // boolean[] visited : 방문체크 // int depth : 현재 탐색중인 인덱스 // int r : 뽑고자 하는 개수 public class 순열 { public static void main(String[] args){ int[] arr = {1, 2, 3}; int r = 2; permutation(arr, new int[r], new boolean[arr.length], 0, r); } public static void permutation(int[] arr, int[] out, boo..
구간 합 (Prefix sum) 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 코딩 테스트에서 사용 빈도가 높으니 잘 알아둘 것!! // 배열 A. 합 배열 S S[i] = A[0] + A[1] + ... + A[i-1] + A[i]; // A[0]부터 A[i]까지의 합 // 합 배열 S 만드는 공식 S[i] = S[i-1] + A[i]; // 구간 합을 구하는 공식 S[j] - S[i-1]; // i에서 j까지 구간 합 // 2차원일 경우 S[i][j]의 값을 채우는 구간 합 공ㅇ식 S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j]; 투 포인터 (Two Pointers) 2개의 포인터로 알고리즘의 시간복잡도를 최적화 ..
완전탐색 (Brute Force) 모든 경우의 수를 시도하는 알고리즘 input이 클 경우 오래 걸림 종류 Brute Force : for문을 이용하여 처음부터 끝까지 탐색, 데이터의 개수가 100만 개 이하일 때 적합 비트마스크 : 이진수 표현을 자료구조로 쓰는 기법 백트래킹 : 분할 정복을 이용한 기법, 재귀함수를 이용 재귀함수 순열 : 순회 외판원 BFS/DFS 백트래킹이나 DP로 풀 수 있는 문제라면 완전탐색으로 풀어서는 효율성을 장담할 수 없음
그래프 그래프란? - 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조 - 정점(vertex)와 간선(edge)들의 집합으로 구성 ( 정점은 node라고 불리기도 함) 그래프 용어 - 정점 : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소 - 간선 : 링크라고도 하며 정점 간의 관계를 나타냄 - 인접 정점 : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점 정점 C의 인접 정점은 A, D - 차수 : 정점에 연결된 간선의 수 정점 A의 차수는 3, 모든 정점의 차수의 합은 8 무방향 그래프 : 간선 수 x 2 양방향 그래프 : 외부에서 오는 간선의 수를 진입 차수, 외부로 향하는 간선의 수를 진출 차수 - 경로 : 간선을 따라갈 수 있는 길, 정점을 나열하여 표시 - 경로의 길이..
DFS (깊이 우선 탐색) 알고리즘 말 그대로 그래프를 깊숙이 탐색하는 알고리즘이다. DFS는 Stack 또는 재귀 함수를 통해 구현한다. DFS 알고리즘은 최소, 최단 탐색이 보장되지 않으며 모든 경로를 찾아봐야 하는 경우에 사용하는 것이 좋다. BFS (너비 우선 탐색) 알고리즘 DFS와 달리 시작 정점 방문 후 인접한 모든 정접을 먼저 탐색하는 알고리즘이다. BFS는 Queue를 통해 구현한다. BFS 알고리즘은 최소, 최단 탐색이 보장되며 DFS로 풀 수 있는 문제는 BFS로도 풀 수 있다 (아마도? 효율보장 X) DFS와 BFS 기본 코드 백준 1260번 문제를 풀이한 것이다. https://www.acmicpc.net/problem/1260 DFS와 BFS의 기본코드로 문제풀이 시 기본코드로 ..
