본문 바로가기

알고리즘11

[백준] 1095번 파이썬 - 마법의 구슬 s+f개의 구슬 중 s개를 뽑는 조합의 개수를 구하고그 개수를 m이하의 사람들에게 모두 같은 개수로 나누어 주면 되는데이 때 m의 값이 최대여야 한다.첫 번째 코드# 1,000,000,000범위 -> 시간복잡도 O(N)import maths,f,m = map(int,input().split())answer = -1# 1. s+f개로 만들 수 있는 조합의 개수 구하기 -> math.comb 시간복잡도 O(logn)combs = math.comb(s+f,s)# 2. m 이하의 사람들이 모두 같은 개수의 조합을 테스트 할 수 있도록 나누기if combs 시간초과  두 번째 코드# 1,000,000,000범위 -> 시간복잡도 O(N)import sysimport mathinput = sys.stdin.readl.. 2024. 5. 10.
[프로그래머스] 178870 파이썬 - 연속된 부분 수열의 합 (투포인터 알고리즘) 문제 이름과 제한 사항 (sequence의 길이 투포인터 알고리즘이 생각났다. 투포인터 알고리즘?- 두 개의 점의 위치를 기록하면서 처리하는 알고리즘- 특정한 합을 가지는 부분 연속 수열 찾기와 같은 문제 & 정렬되어 있는 배열 문제에 대표적으로 사용됨- 시작점은 끝점보다 작거나 같다는 조건을 항상 만족해야 한다.- 시간복잡도는 O(N)         - 포인터가 N번 증가해야 알고리즘이 끝나므로 하나의 포인터의 시간복잡도는 O(N)      2 * O(N) = O(N) 이므로 합쳐도 시간복잡도는 O(N) 풀이1. start, end 각각 0으로 설정 & 두 포인터 사이의 값의 합 sumNum = sequence[start]으로 초기화    1-1. sumNum이 k보다 크거나 같으면 start += 1.. 2024. 4. 12.
[프로그래머스] 92334 파이썬 - 신고 결과 받기 각 유저가 받은 결과 메일의 수를 출력하면 되는 문제.신고한 모든 내용을 취합, 마지막에 한꺼번에 게시판 이용 정지를 시킨다는 조건 때문에 구현이 어렵진 않았다.시간복잡도는 report의 길이가 최대 200,000 이기 때문에 이중 포문을 사용하지만 않으면 통과였다. 풀이1. id_list에 있는 id를 key값으로 가지는 dictionary에 [id가 신고당한수, 신고한 id들]을 value로 넣는다.2. report를 돌며 신고한 id,신고당한 id를 변수 a,b에 저장한다.    2-1. 만약 dic[a]가 신고한 id들(dic[a][1])에 b가 존재하지 않는다면,            dic[a][1]에 b를 append하고 dic[b]가 신고당한 수에(dic[b][0])에 1을 더한다.3. di.. 2024. 4. 11.
[프로그래머스] 133502 파이썬 - 햄버거 만들기 1은 빵, 2는 야채, 3은 고기빵 - 야채 - 고기 - 빵 순서로 쌓인 햄버거만 포장한다. 풀이1. hamburger라는 배열에 재료를 하나씩 넣는다.2. 배열의 뒤에서부터 4개를 가져와 햄버거로 포장 가능한지 검사한다. (isBurger 함수)3. 만약 포장 가능하다면 answer += 1, 포장된 재료 4개는 pop() 해준다. 코드def solution(ingredient): answer = 0 hamburger = [] for i in ingredient: hamburger.append(i) if isBurger(hamburger[-4:]): answer += 1 for _ in range(4): .. 2024. 4. 8.
[백준] 24092번 파이썬 - 퀵 정렬 3 2 5 1 4 3(i=1, j=2) -> 2 5 1 4 3(i=1, j=3, A[2]와 A[3]이 교환됨) -> 2 1 5 4 3(i=2, j=4) -> 2 1 5 4 3(i=2, j=5, A[3]과 A[5]가 교환됨) -> 2 1 3 4 5(i=0, j=1) -> 2 1 3 4 5(i=0, j=2, A[1]" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/24092" data-og-url="https://www.acmicpc.net/problem/24092" data-og-image=""> 24092번: 알고리즘 수업 - 퀵 정렬 32 5 1 4 3(i=0, j=1, A[1]과 A[1]이 교환됨) ->.. 2024. 4. 4.
[백준] 24090번 파이썬 - 퀵 정렬 1 2 5 1 4 3(i=1, j=2) -> 2 5 1 4 3(i=1, j=3, A[2]와 A[3]이 교환됨) -> 2 1 5 4 3(i=2, j=4) -> 2 1 5 4 3(i=2, j=5, A[3]과 A[5]가 교환됨) -> 2 1 3 4 5(i=0, j=1) -> 2 1 3 4 5(i=0, j=2, A[1]과 A[2]가" data-og-title="24090번: 알고리즘 수업 - 퀵 정렬 1" data-og-type="website" data-ke-align="alignCenter" data-ke-type="opengraph"> 24090번: 알고리즘 수업 - 퀵 정렬 12 5 1 4 3(i=0, j=1, A[1]과 A[1]이 교환됨) -> 2 5 1 4 3(i=1, j=2) -> 2 5 1 4 3(i.. 2024. 4. 4.
[Algorithm] 퀵 정렬(quick sort) 퀵 정렬- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 동작- 호어 분할 방식     -> 리스트에서 첫번째 데이터를 pivot(기준)으로 정한다.     -> 왼쪽에서부터 피벗보다 큰 데이터를, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.      -> 큰 데이터와 작은 데이터의 위치를 서로 교환- 분할된 두 개의 배열에 대해 재귀적으로 이 과정을 반복- 한번 진행될 때마다 최소한 하나의 피벗은 최종적으로 위치가 정해진다- 퀵 정렬의 시간복잡도 : O(NlogN)      -> 삽입 정렬과 달리 데이터가 거의 정렬되어 있는 최악의 경우 시간복잡도가 O(N^2) 이다예시array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]def quick_sort(array,.. 2024. 4. 4.
[백준] 17406번 파이썬 - 배열 돌리기 4 배열이 주어지고 시계 방향으로 회전 시킬 범위 r,c,s가 주어진다.주어진 범위대로 배열을 돌리면 되는데, 회전 연산들의 순서에 따라 배열 A의 크기가 달라진다. 나는 배열 A의 크기를 구하는 countLine 함수와주어진 범위대로 배열을 회전시키는 rotateArray 함수를 만들어 주었다.(배열을 회전 시키는 것은 배열 돌리기 문제 1,2,3 을 통해 해보아서 비교적 쉽게 구현할 수 있었다.) 회전 연산의 순서를 섞어 배열 A의 최솟값을 구하는 것에서 많이 고민했는데 문제의 범위 제한은 다음과 같았다.K의 범위가 최대 6이기 때문에 permutations를 써도 될 것 같았고 (permutations의 시간 복잡도는 n!/r!)permu라는 리스트에 순열 값을 저장하여 최솟값을 계산하였다. 제출후 결.. 2024. 4. 3.
[백준] 16927번 파이썬 - 배열 돌리기 2 16927번: 배열 돌리기 2크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]www.acmicpc.net 16926 번 문제에서 회전 횟수의 범위가 1 로 늘어난 문제이다. 회전 횟수를 줄이기 위해 배열이 몇 번 회전했을 때 현재 배열과 똑같아 지는지 고민해보았고,2*(n-1) + 2*(m-1)이와 같은 사이클이 지날 때 마다 배열의 겉 둘레가 처음 배열과 같아지는 것을 확인했다. for문의 회전 범위를 R % cycle로 줄이고 제출해보니 틀렸다.. 왜?16926번 문제에서 .. 2024. 4. 2.

티스토리툴바