'🍀 Knowledge/알고리즘' 카테고리의 글 목록 (2 Page)

[알고리즘] 정수론 - 오일러 피와 유클리드 호제법

2023.09.01

정수론을 제대로 파고자 한다면 그 범위가 만만찮다. 하지만, 코딩 테스트에 나오는 일반적인 유형이라는게 존재하기에 그 대표적인 경우들을 대처할 수 있다. 그 중 많이 쓰이는 것은 유클리드 호제법(확장도 있다)이다. 물론 오일러 피 함수도 간혹 쓰이나 유클리드 호제법에 비할 바는 아니다. 그 이유는 유클리드 호제법이 최대 공약수와 최소 공배수를 구하는 정말 효율적인 방법이기 때문이다. 오일러 피 함수 오일러 피 함수는 1부터 N까지의 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 실제 코딩 테스트에서 사용되는 구현 부분만 짚고 넘어갈 것이기에 간단하게 핵심 원리만 알아보자. 1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 한다. 2. 2부터 시작하여, 현재 배열의 값과 인덱스가 같다면(소수라면) ..

🍀 Knowledge/알고리즘

[알고리즘] 정수론 - 소수에 관하여

2023.08.30

소수란, 1과 자기 자신 이외의 값으로는 나누어 떨어지지 않는 수를 뜻한다. 우리는 이 소수를 구하기 위해서, 통상적으로 2부터 자기 자신 바로 이전이 될 때까지 나누어 떨어지는 지 확인하곤 한다. 하지만, 이러한 방식은 대량의 소수를 구해야 할 때 꽤나 많은 시간 복잡도를 소요한다. 그래서 많은 똑똑한 사람들이 수학적으로 소수를 구할 수 있는 효율적인 방법을 찾아냈다. 그 중 하나가 "에라토스테네스의 체"이다. 에라토스테네스의 체 : 소수의 배수를 소거하는 방법으로 소수를 찾아내는 방법 에라토스테네스의 체를 사용할 때, 시간복잡도는 이중 for문을 사용하므로 O(N^2)이라고 판단할 수 있다. 꽤 많은 것이 아니냐 생각할 수 있는데, 바깥쪽 for문을 생략하는 경우가 많아 실제론 O(Nlog(logN)..

🍀 Knowledge/알고리즘

[알고리즘] 그리디 알고리즘

2023.08.28

그리디 알고리즘? 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 단, 모든 문제에 무작정 사용하는 것이 아니라 전체 선택지에서 똑같이 적용되는 지 꼭 확인해야 한다. 그래서 그리디 알고리즘을 고려하기 위한 3가지 단계는 다음과 같다. 1. 해 선택 : 현재 상태에서 최선의 해를 선택한다. 2. 적절성 검사 : 선택한 해가 전체 문제 제약 조건에 벗어나는 지 확인한다. 3. 해 검사 : 선택한 해 집합이 전체 문제를 해결할 수 있는 지 확인한다. 못한다면, 다시 해 선택으로 이동한다. 예시 문제를 통해 어떤 방식으로 그리디 알고리즘이 사용될 수 있는 지 알아보자. 그리디 알고리즘 문제 예시 1 11047번: 동전 0 첫째 줄에 N과..

🍀 Knowledge/알고리즘

[알고리즘] 정렬된 데이터에서의 탐색, 이진 탐색

2023.08.26

이진 탐색 이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾을 때 효율적인 알고리즘이다. 주요 특징은 대상 데이터의 중앙값과 탐색 대상 값을 비교하고, 데이터 크기를 절반씩 줄이면서 찾는다는 것이다. 정렬된 데이터가 있는 경우, 굉장히 유효하게 사용되는 일반적인 알고리즘이기에 꼭 숙지해야 한다. 이진 탐색의 과정 1. 현재 데이터 셋의 중앙 값을 찾는다. 2. 중앙 값 > 타깃 값인 경우, 중앙 값 기준 왼쪽 데이터 셋에서 다시 탐색한다. 3. 중앙 값 < 타깃 값인 경우, 중앙 값 기준 오른쪽 데이터 셋에서 다시 탐색한다. 4. 이 과정을 반복하다가 중앙 값 = 타깃 값이 된 순간 종료한다. 이진 탐색 문제 예시 1 백준 1920번 문제를 통해서 이진 탐색이 사용되는 간단한 예시를 알 수 있..

🍀 Knowledge/알고리즘

[알고리즘] DFS와 BFS 다루기

2023.08.25

DFS와 BFS는 코딩 테스트에서 항상 단골 문제로 출제되는 매우 중요한 알고리즘 중에 하나이다. 이제부터 어떠한 경우에 DFS와 BFS 문제를 적용하여 문제를 풀이 할 수 있는 지 작성해 본다. DFS 깊이 우선 탐색은 그래프 완전 탐색 기법 중에 하나로, 그래프의 시작 노드에서 출발하여, 탐색할 한 쪽 분기를 정해 탐색을 마친 후, 다른 분기로 이동하여 탐색을 하는 알고리즘이다. DFS(깊이 우선 탐색)의 특징 - 재귀 함수로 구현한다.(중요) - 스택 자료구조를 사용한다. 실제 문제 풀이에서 DFS는 재귀함수를 사용하는 경우가 많은데, 이 때 스택 오버플로우를 주의해야 한다. DFS 문제에 대한 유형은 주로, 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제이다. DFS 문제 예시 1..

🍀 Knowledge/알고리즘

[알고리즘] 정렬(병합, 기수) 알고리즘 (3)

2023.08.18

병합 정렬 분할 정복, 데이터를 분할하고 분할한 집합을 정렬하는 병합 정렬 알고리즘의 정렬 방식이다 특이한 점은 swap을 사용하지 않는 다는 것이다. 여기서 swap이란, 인접한 요소와 비교하여 교환하는 것을 말한다. 그럼 어떤 방식을 사용하길래 swap을 쓰지 않고도 정렬이 가능한 걸까? 병합 정렬의 핵심은 병합이다. 이 과정에서 정렬이 되게끔 재 조합한다는 것이다. 직접 코드를 살펴보며, 어떠한 방식으로 구동되는 지 살펴보자. 병합 정렬 문제 풀이 백준 2751번 문제를 통해 병합 정렬을 구현할 수 있다. 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 ..

🍀 Knowledge/알고리즘

[알고리즘] 정렬(퀵 소트) 알고리즘 (2)

2023.08.14

잘쓰면 정말 효율적인 퀵 소트 퀵소트의 시간 복잡도는 O(nlogn)이다. 또한 퀵 소트에 대해 제대로 이해만 한다면, 더욱더 빠르게 답을 구하는 것도 가능하다. 퀵 소트의 전반적인 과정에 대해 이해해보자. 1. 피벗을 하나 선택한다. 이 때, 피벗의 부분 배열의 가장 왼쪽을 선택하냐, 중간을 선택하냐, 제일 오른쪽을 선택하냐에 따라서 효율이 다를 수 있다. 2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값과 작은 값을 찾는다. 헷갈린다면, 정렬이라고 생각해보자. 왼쪽에는 작은 값들부터 오른쪽에는 큰 값까지 있어야 한다. 그럴려면, 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾아 바꾸어 줄 필요가 있다. 3. 양쪽에서 찾은 값을 서로 바꾸어 준다. 4. 왼쪽과 오른쪽에서 탐색..

🍀 Knowledge/알고리즘

[알고리즘] 정렬(버블, 선택, 삽입) 알고리즘 (1)

2023.08.13

그놈의 정렬 알고리즘을 공부하며 정말 많이 찍먹하였던 정렬 알고리즘. 그만큼 중요하다는 뜻이겠지만, 이제는 그 끝 마무리를 하려한다. 정렬은 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것을 의미한다. 그렇다면 왜 중요한 것인가? 결국은 "효율성"이다. 시간 복잡도가 작을 수록 더 빠르고 효과적인 프로그램을 만들기 쉽다. 정렬에 대한 알고리즘은 이러한 효율성을 증진시키기 위해, 수 많은 똑똑한 사람들이 만들어 낸 것이다. 조금은 과장일 지라도 정렬에 대한 알고리즘을 제대로 사용할 줄 안다면 코딩 좀 하는 개발자가 될 수 있을 것이라 생각한다. 정렬의 종류 버블 : 데이터의 인접 요소를 비교하고, swap 연산을 수행하며 정렬 선택 : 대상에서 가장 크거나 작은 데이터를 찾아가 선택하며..

🍀 Knowledge/알고리즘

[알고리즘] 스택과 큐의 사용

2023.08.12

스택과 큐를 사용한 문제 풀이 일반적으로 스택과 큐하면, 후입 선출과 선입 선출의 개념만 알면 끝 아닌가? 라는 생각을 할 수 있다. 하지만, 개념만 알아서는 되는 것이 아니라 실제로 어떻게, 어떠한 상황에서 사용하는 지 알아야 할 필요가 있다. 그 이전에 자바에서 사용되는 스택과 큐 메서드 용어를 정리해 두자. top : 삽입과 삭제가 일어나는 위치 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek : top위치에 현재 있는 데이터를 단순 확인하는 연산 rear : 큐에서 가장 끝 데이터를 나나냄 front : 큐에서 가장 앞의 데이터를 가리킴 add : rear 부분에 새로운 데이터를 삽입 poll : front부분에 ..

🍀 Knowledge/알고리즘

[알고리즘] 슬라이딩 윈도우 알고리즘

2023.08.11

슬라이딩 윈도우 알고리즘 이름만 들어도 참 길다. 하지만, 그 이름 자체에 모든 의미가 내포되어있다. 슬라이딩 윈도우 기법이란 2개의 포인터로 범위를 지정한 후에 그 범위를 유지한 채로 이동하며 문제를 해결한다. 투 포인터 알고리즘과 비슷하고 그 사용법 또한 어렵지 않다. 그렇다면 왜 사용하는가? 개인적으로는 탐색에 있어 좋은 효율을 보여주기 위해. 그리고 사고의 단순화를 위해서라고 생각이 든다. 슬라이딩 윈도우 기법은 쉽지만, 무엇과 어떻게 활용할 수 있냐에 따라 그 난이도가 달라진다. 아래 예시 코드로 슬라이딩 윈도우 기법의 예시를 살펴보자. 일반적인 슬라이딩 윈도우 기법 해당 문제는 백준 12891번 문제로, 일반적으로 슬라이딩 윈도우 기법을 사용하는 경우다. 12891번: DNA 비밀번호 평소에 ..

티스토리툴바