sh1mj1_log

다익스트라(dijkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 아래와 같습니다. 기능 특징 시간 복잡도 (V: 노드 수, E: 에지 수) 출발 노드와 모든 노드 간의 최단 거리 탐색 에지는 모두 양수여야 함. O(ElogV) 다익스트라 최단 경로 알고리즘은 기본적으로 '그리디 알고리즘'으로 분류됩니다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문입니다. 다익스트라 알고리즘 핵심 이론 아래 5 단계로 설명됩니다. 1. 인접 리스트로 그래프 구현 그래프가 위와 같을 때 인접리스트가 표현됩니다. 물론 그래프를 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N 의 크기가 클 것을 대비해서 보통 인접 리스트로 구현됩니다. 2. 최단 거리 배열 초기화 ..

오일러 피 오일러 피 함수 P[N]는 1부터 N까지 범위의 N과 서로소인 자연수의 개수를 뜻합니다. 실제 오일러 피 함수는 증명과정을 공부해야 완벽히 알 수 있지만 이 포스팅에서는 코딩 테스트에 사용하기 위한 구현 부분만 알아봅니다. 오일러 피 함수의 원리는 에라토스테네스의 체와 비슷합니다. 오일러 피 함수의 원리 1. 구하고자 하는 오일러 피의 범위만큼 배열 초기화 2. 2부터 시작해서 소수일 때(현재 배열의 값과 인덱스가 같으면) 현재 선택된 숫자[K] 의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행. 이 때 i 는 K의 배수. 3. 배열의 끝까지 2번 과정을 반복하여 오일러 피 함수를 완성. 그림과 예시와 함께 더 자세히 알아봅시다. 1. 구하고자 ..

https://sh1mj1-log.tistory.com/130 글에서 이어지는 포스팅입니다. 백준 1931 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 문제 분석 1개의 회의실에 회의가 겹치지 않도록 최대한 많은 회의를 배정해야 합니다. 이 때는 그리디 알고리즘을 적용해야 합니다. 현재 회의의 종료 시간이 빠를 수록 다음 회의와 겹치지 않게 시작하는 데 유리합니다. 종료 시간이 빠른 순서대로 정렬하면 겹치지 않는 회의실을 적절하게 선택하면 됩니다. 2. 손으로 풀기 1. 회의와 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬. 종..

알고리즘에서의 정렬은 크게 아래와 같습니다. 버블(bubble) 정렬: 데이터의 인접 요소끼리 비교하고 swap 연산을 수행하며 정렬 선택(selection) 정렬: 대상에서 가장 크거나 작은 데이터를 찾아가 반복하면서 정렬 삽입(insertion)정렬: 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬 퀵(quick) 정렬: pivot 값을 선정해 해당 값을 기준으로 정렬 병합(merge) 정렬: 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬 기수(radix) 정렬: 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬 이 중에서 버블 정렬을 알아보고 문제를 풀어봅시다. 버블 정렬 버블 정렬(bubble sort) 는 두 인접한 데이터의 크기를 비교해 정렬합니다. 매..

바로 문제를 풀어봅시다. 백준 2164번 - 카드2 2164번: 카드2 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 분석하기 큐를 잘 이해하고 있는지를 묻는 문제입니다. 가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출이 떠오릅니다! 카드의 개수의 최대가 500,000 이므로 시간 복잡도의 제약도 크지 않습니다. 큐로 이 문제를 해결해봅시다. 손으로 풀어보기 poll 을 수행하여 맨 앞의 카드를 버립니다. 이어서 바로 add 을 수행해서 맨 앞에 있는 카드를 가장 아래로 옮..

코딩 테스트를 보다가 어떠한 문제의 답에서 Scanner 와 System.out.print 함수를 사용하지 않고 BufferedReader 와 BufferedWriter 을 사용하는 것을 발견했습니다. 그런데 왜 이 두 클래스를 사용해야 하는 것일까요? 그래서 InputStream 부터, InputStreamReader, BufferedReader 을 알아보려고 합니다. 물론 OutputStream, OutputSreamReader, BufferedWriter 도 알아보구요. 그리고 코딩테스트에서 BufferdReader 와 BufferedWriter 을 사용해야 하는 이유도 알아봅시다. InputStream / OutputStream 바이트 단위 입출력을 위한 최상위 입출력 스트림 클래스 InputSt..

Stack 스택은 삽입과 삭제가 LIFO(Last-in First-out = 후입선출) 로 이루어지는 자료구조입니다. LIFO 는 삽입과 삭제가 한쪽에서 만 일어나는 특징이 있습니다. top: 삽입과 삭제가 일어나는 위치 push: top 위치에 새로운 데이터를 삽입하는 연산 pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산. Stack 은 DFS(Depth First Search = 깊이 우선 탐색), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아두어야 합니다. LIFO 는 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문입니다. Queue 큐는 삽입과 삭제 연산이 FIFO(First-in First-out ..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window) 을 유지한 채로 이동(sliding) 하면서 문제를 해결한다. 위 문장만 읽어봐도 투 포인터 알고리즘과 매우 비슷하다는 것을 알 수 있을 겁니다! 원리도 간단하므로 바로 백준 문제 2개를 풀어보면서 윈도우 알고리즘의 개념과 원리를 공부해 봅시다! 백준 12891 번 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다 구간 합 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 것이다. 코딩 테스트에서 자주 사용되므로 잘 알아둡시다. 먼저 합 배열이 무엇인지 정의합시다. 만약 배열 A 가 있을 때 합 배열 S는 아래와 같다. S[i] = A[0] + A[1] + A{2] + … A[i-1] + A[i] 즉, S[i] 는 A[0] 부터 A[i] 까지의 합이다. 합 배열은 기존 배열을 전처리한 배열이라고 할 수 있다. 만약 이렇게 합 배열을 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) 에서 O(1) 으로 줄어든다. 예를 들어서 A[i] ~ A[j] 까지의 배열 합을 구해야 한다고 합시다. 합 배열 ..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다. 배열과 리스트 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 배열의 특징 Index 을 사용하여 값에 바로 접근할 수 있다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입/삭제 하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다. 배열의 크기는 선언할 때까지 지정할 수 없으며 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단하여 코딩 테스트에서 많이 사용한다. 리스트 값과 포인터를 묶은 ‘노드’를 포인터로 연결한 자료구조 리스트의 특징 인덱스가 없어서 값에 접근하려면 Head Pointer 에서부터 순서대로 접근해야 한다. 포인터로 연결되어 있으므로 데이터 ..