반응형 Computer/Algorithm6 Leetcode 큐빗(Qubit)을 다룬 문제 Quantum bit (Qubit)은 양자컴퓨팅에서 사용하는 개념이라 보통 생소한 개념인데 리트코드 문제로 나와서 인상깊어서 올려본다. 458. Poor Pigs 처음에 언듯보면 바이너리서치를 쓰는 문제 같지만, 솔루션을 보고 충격받았다. Qubit 개념을 적극적으로 쓰는 문제 였다. 솔루션 설명에서도 보듯이 최근 Google, IBM, Amazon 같은 회사에서 양자컴퓨터 개념을 물어보는 문제도 종종 나오기 시작한 것 같다. 다시 본론으로 돌아오면 문제는 돼지 하나를 큐빗 하나로 가정하여 독이든 버켓 하나를 찾는 것이다. 큐빗 처럼 동작하게 하기위해서 문제에서는 몇가지 가정을 준다. 돼지는 동시에 여러 버켓을 먹을 수 있다. 독이든 버켓을 먹은 돼지는 m분후 죽는다. m분동안 다른 돼지에게 버켓을 먹일.. 2022. 8. 8. Python bisect 라이브러리 알고리즘 활용 개요 이분 탐색(Binary Search)는 알고리즘 문제를 풀다보면 많이 만나는 문제유형이다. 매번 코딩해서 바이너리 서치를 구현해도 좋지만 문제를 많이 풀다보면 매번 구현하기에 피로가 느껴지기 쉽다. 그래서 본인이 생각하는 접근이 맞는지 빨리 확인하고 문제 푸는 용도로 라이브러리를 사용하면 유용한 것 같다. 다음 리트코드 문제를 예시로 bisect 모듈을 사용 예시를 보이겠다. 34. Find First and Last Position of Element in Sorted Array 사용 예시 문제 설명 자체는 간단하다. Non-decreasing (증가하는) 순서로 주어진 리스트에서 주어진 값의 시작과 마지막 인덱스를 반환하는 문제인다. bisect.bisect_left는 타겟 값중 가장 작은 인덱.. 2022. 7. 26. 기초적인 동적계획법(Dynamic Programming) 문제 풀기 다이나믹 프로그래밍은 문제를 많이 풀어봐야지 느낌이 오는 것 같다. 그래서 이 글에서는 가장 기초적인 1~2차원 다이나믹 프로그램을 활용해야하는 문제에 내가 했던 접근을 설명할 생각이다. 계단오르기 2579번 계단오르기 우선, 이 문제의 설명을 보면 다음과 같은 제약들이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 이 조건을 모두 만족시키는 경우 중에서도 최대의 값으로 가는 경우의 점수를 구해야한다. 다이나믹 프로그래밍에선 중요한 것은 다음과 같다. 이미 계산했던 값은 계산하.. 2016. 10. 14. 동적계획법(Dynamic Programming) 입문하기 DP(Dynamic Programming)? DP는 문제를 최적화를 할 때, 사용을 주로 합니다. 불필요하게 다시 계산을 하는 일을 막아 주는 기능을 합니다. 예를 들어, 가장 기본 적인 Fibonacci(피보나치) 숫자를 구하는 경우를 생각해 봅시다. 여기서 가장 단순하게 생각할 수 있는 코드는 피보나치는 f(n) = f(n-1) + f(n-2) 즉 n번째 피보나치 숫자는 n-1번 째 피보나치 수와 n-2번 째 피보나치 수의 합과 같다 입니다. 이를 재귀 함수로 나타내면 int nth_fibonacci(int n) { if(n 2016. 10. 13. 최대공약수(GCD)와 최소공배수(LCM) 구하는 알고리즘 이런 저런 문제를 풀 때, 많이 응용되는 것이 최대공약수(Greatest Common Divisor, GCD)와 최소공배수(Least Common Multiple, LCM) 입니다. 이 포스트에서는 이 두개를 구하기 위한 알고리즘을 다룰 것 입니다. 유클리드 호제법 두 양의 정수 a, b에 대해서 b = aq + r (0 2016. 10. 13. 기본적인 자료구조 스택(Stack) 배우기 개념 Stack은 가장 기본적이고 널리 쓰이고 있는 자료구조이다. 처음에 넣은 것은 마지막에 돌려주는 Last in First Out 즉, LIFO의 특성을 가진다. 구현 기본적으로 다음과 같은 함수를 가지고 있으면 된다. push(element) pop() isEmpty() 1.C언어를 이용한 구현(배열) 이 같은 경우 stack이라는 배열과 top이라는 변수가 필요하다. top 변수는 가장 위에 있는 원소를 가르키는 것이다. 처음에 top 초기값이 -1인 이유는 인덱스 0번째 자리에도 값이 들어가야하기 때문이다. 그리고 배열을 사용했기 때문에 top이 배열 크기를 넘어서지 않도록 조심해야한다. MAX_STACK_SIZE = 100; int stack[MAX_STACK_SIZE]; int top = -.. 2016. 10. 13. 이전 1 다음 반응형