본문 바로가기

python9

[프로그래머스] 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.
[백준] 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.
[백준] 16926번 파이썬 - 배열 돌리기 1 첫번째 풀이2 ≤ N, M ≤ 3001 ≤ R ≤ 1,000min(N, M) mod 2 = 01 ≤ Aij ≤ 108 사실 문제 제한이 다음과 같아서 풀면서도 아.. 시간 초과 날 것 같은데 라는 생각을 하긴 했다.내 풀이대로라면 r * min(n,m) // 2 * (각 for문에서 돌아가는 while 문의 수) 만큼 계산하는데대충 계산해보아도 시간 제한 1초가 넘어가게 생겼다.진작 풀이 갈아엎을껄.. 혹시나 해서 짰는데 역시나 시간초과 문제가 생겼다. n,m,r = map(int,input().split())array = []# 하우상좌dx = [1,0,-1,0]dy = [0,1,0,-1]for _ in range(n): array.append(list(map(int,input().split()).. 2024. 3. 29.
[백준] 12933번 파이썬 - 오리문제 오리의 울음 소리가 주여지면, 몇 마리의 오리가 소리를 낸건지 최소 수를 구하는 문제이다.quqacukqauackck 첫번째 오리는 "qu_ac_k_q_uack__"두 번째 오리는 "__q__u__a____ck" 첫번째 풀이시간 초과가 난 첫 번째 코드오리 한마리당 문자열을 처음부터 끝까지 돌면서 quack를 찾는 방식으로 풀었다.dfs 방법을 사용하여 시간초과가 난 것 같다. str = list(input())duck = ["q","u","a","c","k"]if len(str) % 5 != 0: print(-1) exit()def countDuck(n_str,str): idx = 0 new_str = [] if len(str) = 5: if len(str)== 5 an.. 2024. 3. 28.

티스토리툴바