본문 바로가기

분류 전체보기311

[알고리즘] 32비트에서 1인 비트를 세기 32비트 unsigned int에서 1인 비트는 몇개인가? ex) 0011 1000(56) -> 3개 1010 1010(170) -> 4개 Solution 1 : Shift 하면서, 한비트씩 확인. 너무나도 쉽게 생각할 수 있는 알고리즘이다. Shift한 값을 &연산을 하여 1이면 Count를 추가시키면 될 것이다. Solution 2 : x와 x-1을 And 함. 0이 될 때까지 아래는 x(56)을 x-1과 &연산한 과정이다. 1) 0011 1000 & 0011 0111 = 0011 0000 2) 0011 0000 & 0010 1111 = 0010 0000 3) 0010 0000 & 0001 1111 = 0000 0000 총 3번의 과정을 거쳐서, 비트가 1인게 3개 있다고 판단할 수 있다. Solut.. 2021. 3. 25.
[알고리즘] 혼자인 값 찾기 2N+1개의 값이 배열에 저장되어 있다. 단 하나의 값을 제외한 N개의 값들이 두번씩 나타난다. 한번만 나타나는 값은 무엇인가? 답 : 모든 값을 XOR했을 때 나온 값이 정답. 이유 : xor은, 비트연산으로 비트가 서로 다를 때 1이 된다. 하지만 같은 값들끼리는 비트도 당연히 같을 것이기 때문에 항상 0이다. 따라서 XOR값이 결국에는 다른 1개의 값만 남게 될 것이다. 2021. 3. 25.
[알고리즘] Linked list에서 Cycle 찾기 (잘못된부분 찾기) 보통 Linked list라는 것은, list들이 이어져서 만들어진다. Start list와, End list 사이의 list들이 서로서로의 주소를 가리키면서 이어져 있는데, 만약 어떠한 list의 가리키는 주소가, 다음 list가 아닌 이전 list라면, Linked list의 특성상 무한적으로 돌 수 밖에 없다. 이를 Cycle이라고 정의하겠다. 그렇다면 이 Cycle을 어떻게 발견을 하고, 수정을 할 것인가? 총 6개의 아이디어가 있다. 1. Linked Listd를 따라가면서 모든 주소를 배열에 저장. 그 후 정렬을 하며 같은 값이 있는지 확인. 이는 가장 흔하게 생각 할 수 있는 방법중 하나이다. 하지만 조금만 생각해보면 무한으로 도는 List에서, 어떻게 모든 주소를 배열에 저장하겠는가? 불가.. 2021. 3. 25.
[알고리즘] 달리기(Merge Sort를 활용) 자신보다 앞에서 달리고 있는 사람들 중 자신보다 실력이 낮은 사람은 몇명인가? - 입력 : 크기 N인 배열 A가 주어진다. A[1]은 현재 1등인 사람의 평소실력, A[2]은 현재 2등인 사람의 평소실력을 나타낸다. 문제 : 어떤 사람 A[i]보다 실력이 낮은 사람이, A[1] ~ A[i-1]에 몇명이나 있는가? ex) 1등 3 2등 4 3등 1 4등 2 5등 6 6등 8 7등 5 8등 9 9등 10 10등 7 Merge Sort를 이용한 접근방법. 잘게 쪼개어서, 합쳐지는 과정에 현재 숫자가 왼쪽에 N개보다 크면 N개를 저장. 이 사진과 같이 표현이 가능하다. 작은 숫자는 오른쪽에서 왼쪽으로 넘어가면서, 자신보다 큰 숫자를 만난경우 해주는 count 이다. 이렇게 한다면, 결과를 도출해낼 수 있다. 2021. 3. 24.
[알고리즘] 감추어진 자연수들을 정렬했을 때 가장 큰 Gap 찾기 조건 - 1~M 까지의 범위에서 N개의 자연수가 입력으로 감추어진다. - M은 N에 비해 매우 크다. 이 자연수들을 정렬했을 때 가장 큰 Gap(즉, 인접한 두 자연수의 차이를 찾아라) 제공 Query(x,y)를 호출하면 x부터 y까지의 범위에서 입력 자연수들 중 가장 작은 값과, 가장 큰 값을 리턴한다. 만약 n=8, m=93 알고리즘 : 1. Qurey(1,M)을 호출하여 가장 작은 값과, 가장 큰 값을 알고 시작한다. 가장 작은 값 : T1, 가장 큰 값 : Tn 2. T1 + 1 ~ Tn - 1 구간을 (N-1)개로 균일하게 나누어 Query를 호출한다. 3. 각각 호출하여 알아낸 최소, 최대값을 이용하여 가장 큰 Gap을 찾는다. 호출하지 않은 정보들은 무시해도 된다. 이게 가능한 이유는, N-.. 2021. 3. 24.
[알고리즘] 증명에 관해서 예시로 정렬된 두 배열에서 합 찾기를 들어보겠다. x = 1, 3, 5, 9, 12, 13, 15, 20 y =2, 7, 8, 10, 11, 14, 16, 17 이렇게 배열이 주어질 때, x배열, y배열의 인자를 합쳐서 23이 있는지를 확인하는 알고리즘이다. 1. 직관 2. 증명 3. 풀이 이와 같은 3단계를 거쳐서 문제를 해결해 나가야 한다. 1. 직관 x는 왼쪽부터, y는 오른쪽 부터 이동하면서 더하고, 더한 합이 33보다 크면 y를 왼쪽으로 이동시키고, 더한 합이 33보다 작으면 x를 오른쪽으로 이동시키면 되지 않을까? 2. 증명 그러면 1번과 같은 알고리즘을 적용했을 때 빠트리는 경우가 없다는 것을 어떻게 증명할 것인가? - 빠트리는 경우가 있다면 반드시 일어나야 하는 상황을 도출하고, 그 상황이.. 2021. 3. 24.

티스토리툴바