공부/알고리즘
-
[python] Codility Lesson 9-3. MaxDoubleSliceSum공부/알고리즘 2021. 9. 9. 12:03
슬라이싱이 이쁘장하게 되지않고 각각 애매하게 슬라이딩 되서 Y값이 빠지는 부분은 어떻게 하지, 각각을 어떻게 따로 구해서 더하나? 한번에 할방법 없나 이런생각 저런생각하다 "구글링 했습니다..." (출처 : https://curt-park.github.io/2018-09-14/algorithm-max-double-slice-sum/) 1. 좌측 slice를 구해주는데, 저번 문제처럼 l_max_slice_sum[i-1] + A[i] 아래와 같이 보면 이해할 수 있지만 아래와 같이 깔끔하게 생각해 내는게 쉽지 않은 것 같다. 1. l_max_slice_sum 과 r_max_slice_sum을 len(A)크기의 리스트로 생성하자. 2. X,Y,Z 중 Y를 i+1로 두고 for문을 돌려서 l_max_slice..
-
[python] Codility Lesson 9-2. MaxSliceSum공부/알고리즘 2021. 9. 9. 02:10
문제를 연습할 때, 바로 떠오르는 방법 먼저 시도해보고, 시간복잡도를 생각한 코드를 작성하고 있다. 맨 아래에 맨처음 2중 for문을 통해 풀어본 코드 (88%) 바로 아래 시간 복잡도를 고려한 코드를 첨부했다. 이번 문제는 뭔가 이전 문제와 크게 다르지 않은 것 같다. 음수관련 처리해주는데 생각이 복잡해져서 꽤나 애를 먹었다. 1. maxSum을 마이너스 끝판왕으로 설정해주고, sum을 0으로 초기값을 잡자. 2. for문을 돌면서 sum += a 해주자. 3. maxSum을 max(maxSum, sum)을 통해 갱신해주자 4. 여기서 조금 머리가 많이 아팠다 여러 예외 ( ex) 모두 마이너스일때, 섞여있을때, [3,-1,5]와 같은 경우 등.... ) 결국 sum이 음수만 아니면 sum을 갱신해줄 ..
-
[python] Codility Lesson 9-1. MaxProfit공부/알고리즘 2021. 9. 8. 20:48
easy 태그가 달린것을 보고 가볍게 풀어야지 하다 1시간 넘게 집중하고 눈이 빨게질만큼 빨게져서 해결했다 ㅠㅠ 문제에서 핵심이 되는 부분은 max값을 구할때 시간복잡도를 줄이는 것이였다. 가령, for문을 돌릴때 i가 3일때 A[3+1 : ]에서 max값을 찾고, 또 i가 11일때 A[11+1 : ] ... and so on... 처음 가장 아래에 게시해둔 가볍게 O(N^2)으로 구현해본 코드에서 바로 아래 코드에서 처럼 max값을 구할때 시간복잡도를 줄여 보았다. 생각의 흐름은 대충... 1. while문을 돌려서 maxList 딕셔너리를 생성하고, max 값의 후보를 키값 index, value값 A[index]로 저장해주자. 2. for문을 돌려서 i 보다 key값이 클때 maxval을 업데이트 ..
-
[python] Codility Lesson 8-2. EquiLeader공부/알고리즘 2021. 9. 8. 14:22
처음 문제를 보고 한동안 O(N^2)방법 밖에 생각이 들지않아 O(N^2)방법으로 먼저 작성해보고, 시간 복잡도를 줄일 방법을 생각해 보았다. 1. dic_second에서 leader를 먼저 구하자, 그런다음 leader가 없다면 return 0을 해주자. 2. for문을 돌면서 dic_first를 채워 주며, 해당 dictionory값을 dic_second에서 -1 씩 지워주자. 3. dic_first와 dic_second에서 learder에 해당하는 키값이 각각의 leader가 된다면 answerCnt += 1 해주자. 4. 예외 상황으로 leader가 dic_first의 key값으로 있는지 확인해주자. # you can write to stdout for debugging purposes, e.g...
-
[python] Codility Lesson 8-1. Dominator공부/알고리즘 2021. 9. 7. 13:19
한 두어번 제출하고 빠진 조건들 덕지덕지 붙은 포스팅 맨 아래 코드에서 큰 아쉬움을 느껴 dictionary를 활용해 작성해 보았다. 1. cntDic 딕셔너리를 생성해주자, 그리고 for문을 돌면서 dictionary안에 A[i]가 있으면 += 1, 없다면 생성 해주자. 2. cntDic[A[i]]가 전체 A의 절반보다 크면 그때의 index값을 return 해주자. 3. for문이 끝나면 return -1 훨씬 더 깔끔하고 예외에 대한 if 조건들이 많이 없어진거 같아 뿌듯하다. # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(A): # write your code ..
-
[python] Codility Lesson 7-4. StoneWall공부/알고리즘 2021. 9. 7. 00:46
이거 스택 큐로 어떻게 풀지... 아 .. 난 할수있어 하다가 3시간 허비 후 눈이 아파서 그냥 구글링 해보았다. 여기서 아래와 같이 스택구조를 생각해냄은 실로 대단한 것 같다... respect 합니다.... 인접하지 않은 같은 높이의 블록을 처리해주는게 상당히 껄끄러웠는데, 아래와 같이 스택을 이용하면 모든것이 해결된다. def solution(H): # write your code in Python 3.6 blockCount = 0 blockStack = [] for i in range(len(H)): while len(blockStack) > 0 and blockStack[-1] > H[i]: blockStack.pop() if len(blockStack) == 0 or blockStack[-1]..
-
[python] Codility Lesson 7-3. Nesting공부/알고리즘 2021. 9. 6. 21:40
7-1 의 brackets 문제의 조금 더 쉬운? 버젼 이었던 것 같다. 1. string S의 길이가 0 일때, return1. 2. '(' 와 ')' 위한 nesting_stack 리스트를 생성해주자. 3. for문을 S의 마지막 인덱스부터 돌면서 ')'를 만나면 append, '(' 만나면 nesting_stack의 크기를 확인하고 0이 아니면 nesting_stack의 마지막 인덱스가 '('이면 nesting이 되지않기 때문에 return 0, ')'이면 가장 최근에 스택에 쌓여진 ')'를 삭제 해주자! 4. for 문을 다 돌고 nesting_stack의 길이가 0이 아니면 return 0, 0이면 return 1 # you can write to stdout for debugging purpo..
-
[python] Codility Lesson 7-2. Fish공부/알고리즘 2021. 9. 3. 01:53
영어로된 문제가 난해?해서 문제해석에 시간이 걸렸다. 간략히 문제를 설명하면, 각각 배열의 인덱스는 숫자가 작을수록 그 위치가 상류임을 뜻하고, list A는 물고기 크기를, B는 물고기의 움직이는 방향을 나타낸다. 또한, 크기가 큰 물고기는 반대방향에서 다가오는 물고기를 잡아 먹는다, 물고기들의 이동속도는 같다. 이러할 때, 마지막에 살아남는 물고기의 수를 구하는 문제이다. 1. 각 리스트의 길이만큼 for문을 돌리며 내려가는 물고기를 list에 스택구조로 물고기 크기를 쌓아 올리자. 2. 내려가는 물고기 스택이 비어 있는 상태에서 올라가는 물고기를 만나면 liveUpFish += 1 3. 내려가는 물고기 스택이 비어 있지 않은 상태에서 올라가는 물고기를 만나면, 스택길이만큼 for문을 돌려 물고기 크..