요세푸스 문제 0 - 11866 문제 링크 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제설명 이 문제를 푸는 방법에는 여러가지가 있겠지만, deque를 이용한 방법은 시간복잡도 측면에서도 효율적입니다. 먼저 문제 설명을 간단히 해보면, 1부터 N까지의 수가 순서대로 있고, 매번 K번째 수를 제거하는 과정을 반복하여 남은 수들을 모두 출력하는 것입니다. from collections import deque N,K = map(int,input().split()) deq = deque([i for i in range(1,N+1)]) # 데크 안에 리스트 넣기 (이 부분 모르면 아래 링크!) r..

다리 놓기 - 1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 성능 요약 메모리: 31256 KB, 시간: 88 ms 분류 조합론, 다이나믹 프로그래밍, 수학 문제 설명 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽..

🤔 이중배열 컴프리헨션이란? 이중배열 컴프리헨션(Double List Comprehension)은 중첩된 리스트를 생성하는 방법 중 하나입니다. 🤯 이중배열 컴프리헨션의 기본 구조 [[expression] for element in iterable if condition] expression: 각각의 요소에 대한 계산식 또는 함수 element: 반복 가능한 객체의 요소 iterable: 반복 가능한 객체 condition: 필터링 조건식 🧐 이중배열 컴프리헨션을 사용한 예제 # 2차원 리스트 초기화 arr = [[0 for _ in range(5)] for _ in range(3)] # 2차원 리스트에서 특정 조건을 만족하는 요소 찾기 arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9..

파이썬 컴프리헨션을 이용한 리스트 생성 방법에 대해 스텝별로 자세하게 설명하겠습니다. Step 1: 기본적인 리스트 생성 먼저, 파이썬 컴프리헨션 없이 기본적인 방법으로 리스트를 생성하는 방법입니다. 다음과 같이 리스트에 원하는 요소들을 직접 입력해줄 수 있습니다. my_list = [1, 2, 3, 4, 5] 위 코드는 1부터 5까지의 숫자를 담은 리스트를 생성합니다. 이 방법은 간단하지만 요소의 개수가 많을 경우에는 코드가 길어지고 가독성이 떨어질 수 있습니다. Step 2: for문을 이용한 리스트 생성 for문을 이용하면 반복문을 한 줄로 작성하여 리스트를 생성할 수 있습니다. 이 방법을 이용하면 코드의 길이를 줄이면서도 여러 요소를 포함한 리스트를 생성할 수 있습니다. 다음은 0부터 4까지의 숫..

동적프로그래밍은 처음 들어보는 사람들에게는 어려울 수 있지만, 실제로 코드를 작성해보면 그리 어렵지 않습니다. 아래 예제는 대표적인 동적프로그래밍 문제 중 하나인 피보나치 수열을 살펴보지만, 피보나치하면 재귀를 생각하시는데 결론은 dp를 사용할때 재귀를 사용하지않고도 반복문과 배열만을 이용해서도 가능하다 입니다. 동적프로그래밍의 기본 개념과 적용 방법을 알아보겠습니다. 아래에는 1)일반적인 피보나치와, 2)TOP-DOWN 방식과 3)BOTTOM-UP 방식으로 구현한 피보나치 수열 코드가 있습니다. 코드를 따라해보면서, 동적프로그래밍의 장점과 효율성을 알아보겠습니다 💻 🔍 피보나치 수열과의 비교 동적프로그래밍의 개념을 이해하기 위해 가장 대표적인 예시인 피보나치 수열을 살펴보겠습니다. 피보나치 수열은 첫번..

🧬 이진 탐색 알고리즘 이진 탐색은 정렬된 배열에서 특정 값을 찾는 데에 사용되는 검색 알고리즘입니다. 이진 탐색의 핵심은 배열이 정렬되어 있다는 것입니다. 배열이 정렬되어 있기 때문에, 배열을 반씩 나누어서 탐색 범위를 줄일 수 있습니다. 이진 탐색은 배열의 중간 값(mid)을 선택하고, 찾으려는 값이 중간 값보다 작으면 배열의 왼쪽 반쪽을, 찾으려는 값이 중간 값보다 크면 배열의 오른쪽 반쪽을 탐색합니다. 이러한 과정을 반복하여 원하는 값이 나올 때까지 탐색합니다. 이진 탐색은 탐색 범위를 반으로 나누기 때문에, 최악의 경우에도 탐색 시간이 O(log n)으로 매우 빠릅니다. 이진 탐색을 사용하여 정렬된 배열에서 값을 찾을 때, 선형 탐색을 사용하는 것보다 훨씬 효율적입니다. 아래 그림은 이진 탐색 ..