반응형 알고리즘5 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. 제2회 삼성 대학생 프로그래밍 경진대회(SCPC) 참가 후기 SCPC 삼성에서 개최하는 작년부터 개최하기 시작한 대학생과 대학원생이 참가 가능한 알고리즘 대회이다. 1차와 2차는 온라인으로 진행되었고, 본선은 우면동에 위치한 삼성전자 건물에서 진행이 되었다. 나는 운이 좋게도 2차 예선에서 A, B와 C 부분 점수를 맞았는데 제출 횟수가 적어서인지 본선 진출 대상자가 되었습니다.. 본선 대회 전 대회가 진행하기 전에 대회장 앞에 여러 이벤트 부스들이 배치되어 있었다. 미니게임과 QR코드를 활용한 Quiz프로그램이 있었고, 기어s2와 다른 여러 상품을 제공하였습니다.. 2016. 10. 13. 동적계획법(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. 이전 1 다음 반응형