반응형 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. 이전 1 2 3 다음 반응형
