본문 바로가기
반응형

Algorithm18

K번째수_프로그래머스 정수형 배열 array 값들이 주어지고, 그 array에서 잘라낼 첫 번째 인덱스와 마지막 인덱스가 이차형 정수 배열 commands의 commands[i][0], commands[i][1]로써 주어진다. 잘라낸 수의 배열을 만들어 정렬한 후, 뽑아내고 싶은 숫자의 인덱스가 commands[i][2]로 주어진다. import java.util.*; class Solution { public int[] solution(int[] array, int[][] commands) { int[] answer = new int[commands.length]; int idxForAnswer = 0; for (int i = 0; i < commands.length; i++) { int[] tmp = new int[com.. 2024. 2. 29.
bitCount 메서드 사용 (다음 큰 숫자_프로그래머스) 10 진수 숫자가 주어지고, 그 수를 1씩 증가시킨다. 처음 주어진 숫자를 2 진수로 바꿔주고 그 수를 구성하는 1의 개수를 구한다. 1씩 증가하는 수를 2 진수화 시킨다. 이 때, 2 진수에 구성되는 1의 개수가 같은 다음 수를 구하는 문제. Integer 클래스의 bitCount() 메서드를 사용하면 간단하게 1인 비트 수를 셀 수 있다. class Solution { public int solution(int n) { int num = Integer.bitCount(n); int answer = n; while (true) { answer = answer + 1; int cnt = Integer.bitCount(answer); if (num == cnt) break; } return answer; .. 2024. 2. 20.
C++로 BigInteger 구현해보기 BigInteger의 구현 원리를 알아보고 C++로 만들어 보도록 하겠다. 메모리 상에 표현가능한 정수의 범위로는 2의 32승 만큼인 -2,147,483,648 ~ +2,147,483,647이다. 하지만 실생활에선 21억이 넘어가는 숫자를 사용할 일이 충분히 많이 있다. 이런 경우에 사용하기 위해서 자릿수 제한 없이 정수 숫자를 표현할 수 있는 BigInteger에 대해 알아보고 만들어 보겠다. BigInteger는 데이터로 들어온 숫자를 문자열로 취급하여 표현할 것이다. BigInteger x; BigInteger y("-1234"); BigInteger z(y); x = "1234"; BigInteger 변수 선언시 생성자에 문자열이 parameter로써 들어가거나 다른 BigInteger의 값을 가.. 2023. 4. 11.
Algorithm - Merge Sort (병합 정렬) Merge Sort : Divide and Conquer의 방식을 사용한 알고리즘. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 그 결과물들을 모아서 원래의 문제를 해결하는 전략. 순환 호출을 주로 사용해서 구현. (과정 : 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봄 - 그렇지 않다면 정렬되지 않은 리스트를 반으로 잘라서 비슷한 크기의 리스트 두개로 나눔[divide]. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬[conquer]. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병[merge]) / Quick sort와 동일한 시간 복잡도인 O(N*LogN). Quick sort는 pivot값에 따라 편향되게 분할될 수 있으므로 최악의 경우 O(N^2)의 시간 복잡도를 .. 2022. 8. 18.
Algorithm - Sieve of Eratosthenes(소수판별 알고리즘) Sieve of Eratosthenes(에라토스테네스의 체) 고대 그리스 수학자 에라토스테네스의 가장 대표적인 소수(Prime Number) 판별 알고리즘. 마치 체로 수를 걸러낸다고 해서 에라토스테네스의 체 라고 부름. 소수들을 대량으로 빠르고 정확하게 구하는 방법. 소수는 양의 약수를 두개만 가지는 자연수(2, 3, 5, 7, 11, ... 등). 모든 경우의 수를 다 돌며 약수 여부를 확인하는 경우 시간 복잡도 => O(N). 매우 비효율적. -> 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 됨. (ex. 8 = 2 * 4 = 4 * 2). => O(N^(1/2)) -> 한 두개의 소수를 판별하는 게 아닌 대량의 소수를 한꺼번에 판별하고자 할 때 사용하는 것이 바로 에라토스테네스의 체 즉, 어.. 2022. 7. 30.
Algorithm - 크루스칼 알고리즘(Kruskal) Kruskal Algorithm : 그래프 내의 모든 노드들을 가장 적은 비용으로 연결하기 위해 사용하는 알고리즘. / greedy algorithm으로 분류됨. / 최소 신장 트리를 만들기 위한 알고리즘(신장 트리 = spanning tree, 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 함 / 최소 신장 트리 = minimum spanning tree, 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 최소 신장트리를 찾는 알고리즘). / 그래프에는 vertex(정점)와 edge(간선)이 있는데, edge에 가중치가 포함되어 있음. / 여러개의 vertex가 .. 2022. 7. 21.
Algorithm - Union Find(합집합 찾기) Union Find : 대표적인 그래프 알고리즘으로 합집합 찾기 라는 의미를 갖고 있음. / 서로소 집합(공통 원소가 없는 두 집합, example- {1,2}, {3,4} == 서로소 관계, {1,2}, {2,3} == 서로소 관계 아님), 상호배타적 집합(Disjoint-Set) 알고리즘 이라고도 불림. / 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘. / 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조. / Union Find 알고리즘은 다른 고급 그래프 알고리즘의 베이스가 됨. (ex. Kruskal Algorithm) Disjoint Set = 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자.. 2022. 7. 16.
Algorithm - Floyd Warshall(플로이드 와샬) Floyd-Warshall Algorithm : 모든 최단 경로를 구하는 알고리즘. 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)를 찾음. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있음. '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘 사용. / 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 특징이 있음. / Dynamic Programming 기술 사용. 핵심 - 말그대로 거쳐가는 정점.. 2022. 7. 5.
Counting Sort & Radix Sort Counting Sort & Radix Sort (기수 정렬) - element 값을 명시적으로 비교하지 않아도 정렬할 수 있는 기법 Comparison sort = 두 개 요소 값을 반복적으로 비교하여 정렬을 수행하는 알고리즘. (Decision tree 모델 이라고도 불림) ● Counting Sort counting sort로 1,3,2,4,3을 정렬하면 count[1] = 1; count[2] = 1; count[3] = 2; count[4] = 1; 해당 개수만큼 순서대로 써주면 됨. -> 이 방식은 stable sorting이 불가능. (stable sorting = 처음 가진 순서를 유지한 상태로 정렬을 하는 방식을 말함. 같은 값을 가졌다고 해서 순서를 마음대로 배치시키는 것이 아니라 원래.. 2022. 6. 28.
Algorithm - Network Flow, Edmonds-Karp Network Flow(네트워크 플로우)란? 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘. / 한 정점에서 다른 정점까지 흐를 수 있는 데이터의 최대 크기가 어느정도 인지를 확인하는 알고리즘. (얼마나 많은 유량(Flow)를 보낼 수 있는지를 계산/ 이러한 알고리즘은 교통 체증, 네트워크 전송, 전자 회로의 전류, 배수관을 흐르는 유체, 유량구하기 등의 다양한 분야에서 활용됨. / 유향 그래프에서 각 간선은 데이터가 흐를 수 있는 정해진 용량으로 제한되어 있으며 이를 최대한의 양으로 얼마나 흐르게 할 수 있는지를 확인함. -> 최대 유량 문제(Max Flow)로 정의하며 해결하기 위한 알고리즘으로 에드몬드 카프 알고리즘(Edmonds-Karp)를 적용함. - 유량.. 2022. 6. 22.
Algorithm - Topological Sort(위상 정렬) Topological Sort : 어떤 일을 하는 순서를 찾기 위한 알고리즘. / 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것. / '순서가 정해져 있는 작업'을 차례로 수행해야 할때, 그 순서를 결정해 주기 위해 사용하는 알고리즘. 위상 정렬은 여러 개의 답이 존재할 수 있음. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능함. -> 사이클이 발생하지 않는 방향 그래프. 사이클이 발생하는 경우 위상 정렬은 수행 불가. Topological Sort 의 특징 : 하나의 방향 그래프에는 여러 위상 정렬이 가능. / 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 함. / 위상 정렬의.. 2022. 6. 12.
Algorithm - Hashing(해싱 알고리즘) Hash? - 해시에는 크게 Hash, Hash function, Hashing, Hash table 이렇게 네가지로 나뉘어짐. ㆍHash : 해시는 데이터를 다루는 기법 중의 하나로 검색과 저장을 아주 빠르게 하는 자료구조이다. 데이터를 저장할때 Key, Value 형태로 데이터가 존재하고, Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장을 빠르게 할 수 있음. ㆍHash function과 Hashing Hash function은 Key값을 고정된 길이의 hash로 변환하는 역할을 함. Hash function에서 Key값을 hash로 변환하는 과정을 hashing이라고 한다. Hash function에서는 Key값을 해싱 과정을 통해 Hash value(해시 값) 또는 Hash code로 변경.. 2022. 5. 21.
Algorithm - Dijkstra(다익스트라) 알고리즘 Dijkstra Algorithm : Dynamic programming을 이용한 대표적인 최단경로(Shortest path) 탐색 알고리즘. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. 이 때 음의 Edge는 포함할 수 없음(현실 세계에선 음의 Edge가 존재 하지 않기 때문에 다익스트라는 현실에서 사용하기 매우 적합함). / 음의 가중치가 없는 그래프의 한 정점(vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 / 에츠허르 다익스트라 라는 사람이 고안한 알고리즘이라함. / 그래프 방향의 유무는 상관없으나 간선(Edge)들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없음. 음의 가중치를 가지는 간선이 있으며 가중치 합이 음인.. 2022. 5. 7.
Algorithm - Backtracking(백트래킹) Backtracking : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법. 최적화 문제와 결정 문제를 푸는 방법이 된다. / 가능한 모든 방법을 탐색한다라는 성격을 가짐. / 모든 경우의 수를 전부 고려하는 알고리즘. 상태 공간을 트리로 나타낼 수 있을때 적합한 방식(일종의 트리 탐색 알고리즘). 방식에 따라서 DFS, BFS, 최선 우선 탐색 등이 있다. DFS가 일반적. / 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면, 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘. DFS와 Backtracking : DFS - DFS의 장점은 무한히 깊은곳을 찾아야 할때 효과적이고 단점은 모든곳을 방문하기 때문에.. 2022. 5. 4.
Algorithm - Brute force(브루트 포스) Brute force : 키 전수조사(exhaustive key search), 무차별 대입, 완전탐색 알고리즘 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법. 흔히 암호학에서 연구되지만, 알고리즘 분야에서도 사용. (수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전) / 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옴. 브루트 포스의 강력한 점은 예외없이 100%의 확률로 정답만을 출력한다. Brute force 특징 : brute-force는 "짐승같은(난폭한) 힘"의 뜻이고 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식해보이지만, 항상 정확도 100%를 보장 한다는 것이 암호 해독법 중 가장 확실하고 무서운 방.. 2022. 5. 2.
Algorithm - Divide and Conquer(분할 정복) Divide and Conquer algorithm : 분할 정복은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘. (원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제들로 나눈다) Divide and Conquer 알고리즘 설계 요령 (도식화) : - Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. / 문제를 더 이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. - Conquer : 나누어진 문제가 여전히 분할이 가능하면, 다시 divide를 수행. 그렇지 않다면 문제를 푼다. / 가장 작은 단위의 하위 문제를 해결하여 정복. - Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다. .. 2022. 4. 28.
Algorithm - Breadth First Search(너비 우선 탐색) Breadth-First Search(BFS, 너비 우선 탐색) : root 노드(혹은 다른 임의의 노드)로부터 시작해서 인접한 노드를 먼저 탐색하는 방법. (최단 경로 탐색, 임의 경로 탐색) / 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어진 노드는 나중에 방문하는 traverse방법. / 깊게(deep하게) 탐색하기 전 넓게(wide하게) 탐색. / 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이 방법을 사용. / 예) facebook같은 거에 존재하는 모든 친구 관계를 그래프로 표현한 후 Hong과 Jo 사이에 존재하는 경로를 찾을때. DFS - 모든 친구 관계를 다 살펴봐야 할 수도 있음. BFS - Hong과 가까운 관계부터 탐색. / BFS가 DFS보다 좀 더 복잡함... 2022. 4. 20.
Algorithm - Depth First Search(깊이 우선 탐색) Graph 탐색 : 하나의 vertex로 부터 시작하여 차례대로 모든 vertex들을 한 번씩 방문하는 것. / 예) 특정 도시에서 다른 도시로 갈 수 있는가, 전자 회로에서 특정 단자끼리 서로 연결 되어 있는가 Depth-First Search(DFS, 깊이 우선 탐색) : root 노드(혹은 다른 임의의 노드)로부터 시작해서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법. / 미로 탐색시 한 방향으로 갈 수 있을때까지 계속 가다가 더 이상 갈수 없을때, 다시 가장 가까운 갈림길로 돌아와서 이곳에서 다른 방향으로 다시 탐색을 진행하는 방법과 유사함. / 넓게(wide하게) 탐색하기 보다는 깊게(deep하게) 탐색하는 것. / 모든 node를 방문하고자 하는 경우에 이 방법.. 2022. 4. 19.
반응형

티스토리툴바