sh1mj1_log

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

정수론 수학에서 정수론은 수의 성질을 공부하는 분야입니다. 실제 코딩테스트에서는 정수론의 분야가 굉장히 방대하기 때문에 가장 많이 등장하는 소수, 오일러 피, 호제법에 관련하여 학습합니다. 소수 소수(prime number) 는 자신보다 작은 2개의 자연수를 곱해서 만들 수 없는 1보다 큰 자연수를 말합니다. 1과 자기 자신 외에 약수가 없는 수입니다. 소수를 구하는 대표적인 방법은 에라토스테네스의 체가 있습니다. 에라토스테네스의 체 1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성. 2. 2부터 시작해서 현재 숫자가 지워지지 않았다면 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 처음으로 선택된 숫자는 지우지 않습니다. 3. 배열의 끝까지 2를 반복한 후에 배열에서 ..

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. 회의와 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬. 종..

그리디(Greedy) 그리디(Greedy) 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘입니다. 그래서 동적 계획법(Dynamic Programming) 보다 구현하기 쉽고 시간 복잡도가 우수합니다. 하지만 항상 최적의 해를 보장하지는 못한다는 단점도 있습니다. 그래서 항상 그리디 알고리즘을 사용하기 전 논리에 대해 자세히 살펴보아야 합니다. 그리디 알고리즘의 수행 과정 1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택 2. 적절성 검사: 현재 선택한 해가 전체 문제의 조건에서 벗어나지 않는지 검사 3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 만약 해결할 수 없다면 1의 과정을 반복. 바로 ..

이진탐색 이진 탐색(Binary Search)은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해서 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다. 기능 특징 시간 복잡도 타깃 데이터 탐색 중앙값 비교를 통한 대상 축소 방식 O(logN) 구현과 원리가 간단해서 코딩 테스트에서 보통 부분 문제로 포함되어 있는 경우가 많습니다. 이진 탐색의 핵심 원리 이진 탐색을 오름차순으로 정렬된 데이터에서의 예로 찾아보겠습니다. 내림차순으로 정렬되어 있는 경우에도 조건을 반대로 해서 똑같이 실행하면 됩니다.) 이진 탐색 과정 현재 데이터셋의 중앙값(median)을 선택. 중앙값 > 타겟 데이터(찾고자 하는 데이터) 일 때 중앙값 기준으로 왼쪽 데이터..

BFS(Breadth-First Search) BFS(너비 우선 탐색)은 DFS 와 마찬가지로 그래프를 완전 탐색하는 방법 중 하나로 시작 노드에서 출발해서 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘입니다. 기능 특징 시간복잡도 (V: 노드 수, E: 에지 수) 그래프 완전 탐색 FIFO 탐색 Queue 자료구조 이용 O(V+E) FIFO(선입선출 방식)으로 탐색하므로 큐를 이용하여 구현합니다. 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선시하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다. BFS 구현은 아래 3단계로 설명할 수 있습니다. 1. BFS 시작 노드를 정한 후 자료구조 초기화 BFS 도 DFS 처럼 방문했던 노드는 다시 방문하지 않습니다. 그래..

DFS(Depth-First Search) 깊이 우선 탐색은 DFS(Depth-First Search). 그래프 완전 탐색 기법 중 하나입니다. 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다. 기능 특징 시간 복잡도 (V: 노드 수, E: 에지수) 그래프 완전 탐색 재귀함수로 구현 스택 자료 구조 이용 O(V+E) DFS 는 실제 구현 시 재귀함수를 이용하므로 Stack Overflow 에 유의해야 합니다. 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬이 있습니다. DFS 는 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이..

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

Comparable 이 인터페이스를 구현하는 각 클래스 개체에 순서를 지정합니다. 이 순서를 natural ordering(자연순서) 라고 하며 클래스의 compareTo 메서드를 자연 비교 메서드라고 합니다. 이 인터페이스를 구현하는 객체 List 나 Array 는 (이하 List) Collections.sort() 로 자동으로 정렬할 수 있습니다. 따로 comparator 을 지정하지 않아도 말이죠. compareTo 메소드 public int compareTo(T o); Comparable 은 compareTo 라는 메서드를 가지고 있습니다. 이 객체를 지정된 객체와 비교하여 순서를 지정하는 메소드입니다. 파라미터 o 는 nullable 입니다. compareTo 메서드를 호출하는 객체가 파라미터인..

자바 코딩테스트 공부 중 백준 11286 절댓값 힙 문제를 푸는 중에 Priority Queue 을 사용하는 방법에 대해 간단하게 정리해보려고 합니다. 이 포스팅에서는 매우 간단한 사용 방법을 설명합니다. 추가로 PriorityQueue 의 인자로 comparator 을 가질 수 있는데 이 부분은 오른쪽 링크 https://sh1mj1-log.tistory.com/122 포스팅하단에서 확인할 수 있습니다. Priority Queue(우선순위 큐)? Priority Queue 는 Queue 와 구조가 비슷합니다. Queue 는 FIFO(First In First Out) 구조로 먼저 들어온 순서대로 데이터가 나가는 것인 반면에 Priority Queue 는 데이터의 우선순위를 정해 우선순위가 높은 순서대로..