공부
-
[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문을 돌려 물고기 크..
-
[python] Codility Lesson 7-1. Brackets공부/알고리즘 2021. 9. 3. 00:21
이전에 코딩테스트 여러곳 보면서 가끔 보았던 빈출? 문제 같다.. 코드를 작성하며 정답의 예외처리하는 부분이 아래와 같이 부분 부분있으면 좋지않은 코드라 생각한다. 어찌됫건 생각해본 흐름은 1. 예외상황으로 strStack이 비어있을때 좌측 bracket이 오면 그 순간 return 0 2. 좌측 bracket이 아닌 bracket이 들어올때 strStack에 append 3. 좌측 bracket이 들어올때 해당하는 우측 bracket이 있으면 strStack pop(), 그렇지 않다면 return 0 4. 마지막 예외로 strStack이 for문을 모두 돌고 비어있으면 return 1, 그렇지 않다면 return 0 100점이 나오긴했지만 영 코드도 더럽고 아쉬웠다. # you can write to ..
-
[python] Codility Lesson 6-3. Triangle공부/알고리즘 2021. 9. 2. 10:57
A리스트안의 원소를 이용해 각기 크기가 다른, 각각의 합이 한변의 길이보다 큰 세변의 삼각형을 구하는 문제이다. codility에서 easy태그가 달린 것은 조금만 생각해보면 술술 풀리는 문제같다. 아래 1번을 생 1. 삼각형 변 a c 이면 b+c > a, a+c > b 등을 만족한다 (핵심인듯) 2. 삼각형 변의 후보인 리스트 A를 sort 해준다. 3. for문을 돌리며 a+b > c를 만족하면 return 1, for문이 끝나면 return 0. # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(A): # write your ..