바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

그래프 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

-> 두 점을 연결하는 길이 있는가? 이를 확인하기 위해 하나씩 방문. (특정 도시에서 다른 도시로 갈 수 있는가? 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는가?)

너비 우선 탐색(BFS, Breath-First Search)

루트 노드(or 임의의 노드)에서 시작해서 '인접한' 노드를 먼저 탐색하는 방법

1. 의미

• 가까운 것부터.
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색.
• (가중치가 동일할 때) 두 노드 사이의 최단 경로를 찾거나, 혹은 임의의 경로가 있는지 확인하고 싶을 때
  • 지구상 모든 친구 관계를 '그래프'로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
    • BFS: A와 가장 가까운 관계부터 탐색 <-> DFS: 모든 친구 관계를 다 살펴봐야 할지도...
    • 그러나 BFS가 DFS보다 좀 더 복잡한 경향 O

2. 특징

• 복잡해,, 좀 어렵지?
• 재귀적으로 동작하지 않음
• 어떤 노드를 방문했었는지 여부를 반드시 check해야 함. (그렇지 않으면 무한루프 가능 O)
  • BFS 방문 노드를 큐(Queue)에 차례로 저장, 하나씩 다시 꺼낼 수 있도록.
  • 큐는 선입선출(FIFO): 먼저 들어간 게 먼저 나온다.
• Prim, Dijkstra 알고리즘과 유사.

3. 과정

1) 시작 정점에서 깊이가 1인 모든 노드 방문

• 방문할 때마다 해당 원소가 enqueue
• 시작 정점은 dequeue

2) 깊이가 2인 모든 노드 방문

• 어떻게 보면, 시작 정점이 Queue의 첫번째 원소로 바뀐 셈.
• 이때 Queue에서 해당 원소가 dequeue됨. 
• 바뀐 원소에서 깊이가 1인 걸 탐색하고, 만약 Queue에 이미 저장되어 있는 원소라면 pass.

3) 깊이가 3인....

4) 더 이상 방문할 곳이 없으면(큐가 소진될 때) 탐색 종료

4. 구현

• deque 라이브러리를 활용, 큐.
• 시간 복잡도는 O(N) (대체로 DFS보다 BFS가 우수)

1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고 *방문 처리합니다.
2️⃣ 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리합니다.
3️⃣ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

여기서 *방문 처리란 탐색한 노드를 재방문하지 않도록 구분하는 것입니다. 즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것이죠.

from collections import deque

def bfs(graph, node, visited):
	# 그래프 탐색
    # node는 시작 정점의 default
    # visited는 graph의 node 개수만큼 False로 채워진 리스트
    queue = deque([node])
    visited[node] = True #방문 node에 방문 처리
    
    while queue:
    	# queue가 완전히 빌 때까지 반복
        v = queue.popleft() #선입선출
        print(v, end = '')
        for i in graph[v]:
        	if not (visited[i]):
            queue.append(i)
            visited[i] = True

graph = [
    [],
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

그래프 표현: 노드 간의 연결 정보는 위와 같이 2차원 배열을 통해 표현할 수 있습니다.

즉, 리스트 내 인덱스는 노드 번호를 의미하고 각 인덱스에 해당하는 원소에 해당 노드에 인접한 노드 번호가 담겨 있습니다.

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

# 정의한 BFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
bfs(graph, 1, visited)


#>>> 1 2 3 8 4 5 6 7

*참고 및 인용

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://heytech.tistory.com/56

https://school.programmers.co.kr/learn/courses/30/lessons/42842

문제 개요

카펫의 패턴
가장자리(테두리) 1줄: 갈색
나머지 중앙: 노란색

input
본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow

ex) 10, 2
*brown: 8 이상 5,000 이하
*yellow: 1 이상 2,000,000 이하

output
[카펫의 가로, 세로 크기] ex) [4,3]
*가로>=세로
*즉 두 값 중 큰 것을 가로로 세우면 됨.

나의 풀이

def solution(brown, yellow):
    x = int((brown-4)*(1/2))
    for i in range(x-1, int(x*(1/2)-1), -1):
        if (i+2)*(x-i+2) == brown+yellow:
            return [i+2, x-i+2]

후기:

같은 레벨2이지만 그저께 푼 문제와 이번 문제 간 편차가 아주 크다..

레벨1 만큼 간단했던 문제!

결론: 레벨2인데 많이 어려웠다 !!!!ㅜㅜ

재귀는 아직 나에게 익숙하지 않았고 + 소수 찾는 아이디어도 익혀야했다. (에라토스테네스의 체 등.)

덕분에 순열 알고리즘도 공부했고, 소수 찾기 유형은 앞으로 껌이 될 예정🤩 매일매일 재귀랑 더 친해지는 중

사실 재귀 알골 대신 훨씬 효율 좋은 파이썬 모듈(itertools-permutations)이 있는데,

배운 것 적용도 해보고 모듈 의존적이지 않기 위하여 두 가지 방식 각각 시도해보았다

https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제 개요

input
숫자가 적힌 문자열 numbers
*길이 1 이상 7 이하인 문자열
*각 숫자는 0~9
*"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다

return
흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지, 소수 개수

EX
"17" -> 3
"011" -> 2

Idea

• 순열 구하는 방법(1. permutations 모듈 2. 재귀) : 👉 https://lets-hci-la-ai-withme.tistory.com/47
• 소수 구하는 방법:👉 https://velog.io/@cjy0029/소수-구하는-방법 
  • 소수에는 1 미포함, 2,3,... 포함
  • N의 소수 판별: 2부터 N-1까지 루프를 돌면서 나눠보는 방법(나머지가 없을 때)
    • 비효율적
  • "어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 규칙이 있다."
  • 에라토스테네스의 체
    • 2부터 순회를 하면서 2의 배수를 모두 지워주고, 3부터 순회를 하면서 3의 배수를 모두 지워주고, 4는 이미 지워졌으니 패스하고, 5의 배수를 지우고..
    • 주어진 수의 제곱근까지만 확인해보면 끝난다.

1. python itertools-permutations 활용

from itertools import permutations
def solution(numbers):
    nums = []
    for i in range(len(numbers)):
        nums += [int(''.join(x)) for x in list(permutations(numbers, i+1))]
    
    answers = []
    answers += [x for x in nums if (x in [2,3])]
    for x in nums:
        sqrt = int(x**(1/2))
        for i in range(1,sqrt):
            if x % (i+1) != 0:
                if i+1 == sqrt:
                    answers.append(x)
                continue
            else:
                break
    nums = len(set(answers))
    return nums

2. 재귀 알골 이용

def solution(numbers):
    answers = []
    def permutation(numbers, r):
        used = [0 for _ in numbers]
        def generate(chosen, used):
            if len(chosen) == r:
                chosen = int(''.join(chosen))
                if (chosen in [2,3]) and (chosen not in answers): #2,3은 sqrt값이 1이므로 이하 for문이 실행되지 않음
                    answers.append(chosen)
                
                sqrt = int(chosen**(1/2))
                for i in range(1, sqrt):
                    if chosen % (i+1) != 0:
                        if (i+1 == sqrt) and (chosen not in answers):
                            answers.append(chosen)
                            break
                        continue
                    else:
                        break
                return

            for i in range(len(numbers)):
                if not used[i]:
                    chosen.append(numbers[i])
                    used[i] = 1
                    generate(chosen, used)
                    used[i] = 0
                    chosen.pop()

        generate([], used)

    for i in range(len(numbers)):
        permutation(numbers, i+1)
    answer = len(answers)
    return answer

• append 하기 전, 중복 제거 필요
•  '구분자'.join(리스트)
  • map(''.join, 리스트)로 처리하면 빠름
• 순열 알고리즘 내에서, 모든 단어를 리스트에 저장하는 것이 아니라, 소수인 것만 filter 해서 저장 ←이때 에라토스테네스의 체

순열(순서 o) vs 조합(순서x)

순열(Permutation): 서로 다른 n 개의 대상에서 r 개를 뽑아 일렬로 배열한 것.

순열 알고리즘 구현 방법

1. 파이썬 모듈 사용

2. 재귀

3. 중복 for문 (리스트가 길어지면 너무 비효율적)

1. 파이썬 모듈 사용

• 파이썬 내장 itertools 패키지의 permutations 모듈 활용
• 만들어진 순열과 조합은 튜플의 형태로 리스트에 담겨서 반환된다. -> ([(0, 1, 2), ...])

from itertools import permutations

arr = [0, 1, 2, 3, 4, 5]

print(list(permutations(arr, 3)))

https://juhee-maeng.tistory.com/91

→모듈 사용하는 게 대체로 가장 빠르다고 함..

2. 재귀

2.1 DFS, 백트래킹과 상당히 유사하다.

• permutation([0,1,2,3], 2)
  = ([0],permutation([1,2,3], 1)) + ([1],permutation([0,2,3], 1)) + ([2],permutation([0,1,3], 1))+ ([3],permutation([0,1,2], 1))
• permutation([0,1,2,3], 3)
  = ([0],permutation([1,2,3], 2)) + ([1],permutation([0,2,3], 2)) + ([2],permutation([0,1,3], 2))+ ([3],permutation([0,1,2], 2))
  = ([0],{([1], permutation([2,3],1)) + ([2], permutation([1,3],1)) + ([3], permutation([1,2],1))}) + ([1]. { ~

def gen_permutations(arr, n):
    result = []

    if n == 0:
        return [[]]

    for i, elem in enumerate(arr): 
        for P in gen_permutations(arr[:i] + arr[i+1:], n-1):
            result += [[elem]+P]
              
    return result

2.2

def permutation(arr,r):
    arr = sorted(arr)
    used = [0 for _ in arr]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return #used[i] = 0로 돌아가는데, 다시 for문 거치는 게 아니라, 바로 이어져서 i값이 유지됨.
        
        for i in range(len(arr)): #arr은 함수 외부에 정해져 있음(상수수)
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0 #순열 하나 만들고 나서, 다시 0으로 initialize
                chosen.pop() #return이 없으므로 for문이 끝난 후에도 if문 다시 돌고, if문 만족 못하므로 for문 새로 시작됨

    generate([], used)

좋은 코드라고는 하나 개인적으로 이해하는 데 시간이 걸렸음. 

arr: 리스트
r: 리스트 중 뽑을 개수

[for문 안에서]
chosen: 순열 구성하는 원소 리스트
used: chosen에 들어간 원소 index 위치에 해당 원소의 사용 여부를 0/1로 알려주는 리스트(즉 arr와 연동됨) (*디폴트는 0으로 채워짐)

• 함수 정의문에는 return의 위치가 중요함. for문이 모두 종료되었대도 return이 다른 곳에 있다면 다시 iteration 거침.
  • 여기도 for문의 상단 if문을 거쳐야 return되는데, for문이 종료되고 if문으로 돌아갔을 때 if문 조건이 성립되지 않으므로 return이 실행되지 않음. 즉, 다시 for문으로 돌아가 처음부터 실행됨. (물론 이 상황에서 used와 chosen은 이전 로그가 반영된 상태이므로 i값이 슉슉 점프하게 됨.
• generate 함수 정의문 내부에 generate가 사용된 재귀형식임.
  • 내부 generate이 실행될 때 if문 만족되면 바로 return 일어나므로, 내부 generate 실행 직전 i값이 그대로 보존된 상태로 used[i]=0 코드로 넘어감.
  • 만약 내부 generate 실행될 때 if문 만족 못 하면 for문으로 넘어가고, 결국 내부 generate가 종료되려면 내부 if문이 만족될 때까지 iter iter iter..
• if not False:
  • if not 이하가 False일 때 조건문 시행됨
  • python에서 False에 해당하는 것
    • False (Bool)
    • 0,0L,0.0과 같은 숫자 0 값
    • 다음과 같은 빈 시퀀스 :
      • 빈 목록 []
      • 빈 사전 {}
      • 빈 문자열 ''
      • 빈 튜플
      • 빈 세트
      • None개체
      • [0] 혹은 [0,0,..]은 아님.!!!
• 실행 원리 예시

permutation('ABCD', 3)

>>>

i: 0, chosen: ['A'], used: [1, 0, 0, 0]
i: 1, chosen: ['A', 'B'], used: [1, 1, 0, 0]
i: 2, chosen: ['A', 'B', 'C'], used: [1, 1, 1, 0]
['A', 'B', 'C']
i: 3, chosen: ['A', 'B', 'D'], used: [1, 1, 0, 1]
['A', 'B', 'D']
i: 2, chosen: ['A', 'C'], used: [1, 0, 1, 0]
i: 1, chosen: ['A', 'C', 'B'], used: [1, 1, 1, 0]
['A', 'C', 'B']
i: 3, chosen: ['A', 'C', 'D'], used: [1, 0, 1, 1]
['A', 'C', 'D']
i: 3, chosen: ['A', 'D'], used: [1, 0, 0, 1] ............

https://cotak.tistory.com/70

https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations

https://www.delftstack.com/ko/howto/python/if-not-condition-in-python/

https://school.programmers.co.kr/learn/courses/30/lessons/42840

문제 개요

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5,/ 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...
*시험은 최대 10,000 문제. 문제의 정답은 1, 2, 3, 4, 5중 하나.

input
answers: 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열
ex. [1,2,3,4,5]

return
가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아서
ex. [1]
*가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬.

나의 코드

def solution(answers):
    n = len(answers)
    fir = [1,2,3,4,5]*(n//5)+[1,2,3,4,5][:(n%5)]
    sec = [2,1,2,3,2,4,2,5]*(n//8)+[2,1,2,3,2,4,2,5][:(n%8)]
    thir = [3,3,1,1,2,2,4,4,5,5]*(n//10)+[3,3,1,1,2,2,4,4,5,5][:(n%10)]

    def compare(data):
        cnt = 0
        for idx, i in list(enumerate(data)):
            if i == answers[idx]:
                cnt +=1
        return cnt

    fir_val = compare(fir)
    sec_val = compare(sec)
    thir_val = compare(thir)

    lst = sorted([(1,fir_val), (2, sec_val), (3, thir_val)], key=lambda x: x[1], reverse=True)
    answer = [lst[0][0]]
    for (idx, val) in lst[1:]:
        if val == lst[0][1]:
            answer.append(idx)

    return answer

모범 코드

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result

• [idea] 리스트 내 원소에 특정 패턴이 반복되는 경우
  • pattern 변수 통해 반복되는 부분만 따오기
  • [idx % (패턴의 길이)] 인덱스 처리.
• for문 순환하여 세 명의 score 병렬 계산 (어차피 answers와 세 명의 대답 length가 동일함)
• score = [0,0,0] 처리 후 한꺼번에 score[x] +=1
• 마지막 출력 처리하는 건.... 나 왜 저렇게 짰지?🫢 모범코드대로 하는 게 당연할 따름. idx 순서대로 처리되니 더더욱?!

간단한 문제였다! 코드 더 효율적으로 짜기.

문제를 풀기 전 이해하고 있어야 하는 아이디어

x, y의 두 수의 합이 정해져 있을 때, 두 수의 곱(x*y)이 최소화되려면
x+y = a를 성립하는 (x,y)조합 중 (최대, 최소) 조합이어야 한다.

ex1) 합이 10인 경우

1 10 =10 (최소의 곱)
2 9 =18
3 8 =24
4 7 =28
5 6 =30

1 5 =5 (최소의 곱)
2 4 =8
3 3 =9

https://school.programmers.co.kr/learn/courses/30/lessons/86491

문제 개요

input
sizes: 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 (ex. [[60, 50], [30, 70], [60, 30], [80, 40]])
*원소 개수 최소 1
*명함 가로, 세로는 최소 1, 최대 100

return
지갑의 크기 (ex. 4000)

나의 코드

def solution(sizes):
    big = []
    small = []
    for [x,y] in sizes:
        if x >= y:
            big.append(x)
            small.append(y)
        else:
            big.append(y)
            small.append(x)
    answer = max(big)*max(small)

    return answer

* 아이디어만 잘 알고 있으면 아주 간단한 문제.

https://school.programmers.co.kr/learn/courses/30/lessons/42627

문제 개요

input
: jobs = [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열

return
: 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마
*소수점 이하의 수는 버림

*하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리

문제 이해

input:  [[0, 3], [1, 9], [2, 6]]

우측보다 좌측의 경우, 프로세스 총소요시간(요청부터 처리될 때까지 총시간)의 평균이 적다.

return: 9 (총 27 // 3)

문제 결론

• 대기 시간이 없는 경우와 있는 경우를 구분한다.
  • 대기 시간이 있는 경우 if문 내부에서 현재 시각 now를 조절함으로써, '대기 시간이 없는 경우'와 state를 일치시킨다.
  • 현재 시각 now 계산 식 & 프로세스 총 소요시간 계산 식을 if문 외부에서 공유: waitlst의 heappop 처리.
• 대기 시간이 없는 경우: 소요 시간이 짧은 것을 우선순위로 처리 → heappop (자동 min 정렬)
  • jobs에서 원소를 하나씩 꺼내어 waitlst에 heappush. 즉 jobs 대신 waitlst를 heap으로 처리. 
• 대기 시간이 있는 경우: jobs에서 가장 이른 것을 꺼내어 waitlst에 heappush.

자주 활용되는 아이디어이므로 확실히 기억할 것

문제 이해 프로세스

1. 작업의 요청부터 종료까지 걸린 시간 = 기다린 시간(변수) + 프로세스 진행 시간(상수)

2. '기다린 시간(변수)'은 해당 프로세스가 요청된 시각이 직전 프로세스 종료 시각보다 '이전인가' '이후인가'에 따라 계산 방법이 다르다.

→ 시각과 시간 구분하자

→ 직전 종료 시각을 어떻게 구하는가..? (생각의 무한루프 ♾️🥲)

→ 초깃값은 어차피 a가 가장 작은 값으로 결정되어 있으니 이후 점화식 잘 세우면 된다 (ps: 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리)

→ 일단 '기다린 시간'을 경우에 따라 나누어보자. (경우 = if문으로 구현)

→ 처음에는 '직전 프로세스 종료 시각'을 end로 지정했는데, 오히려 헷갈려서, 현재 시각 'now'로 대체하였다 **

현재 프로세스: [a,b]

1️⃣ if 현재 시각(now) >= 현재 프로세스 요청 시각:

기다린 시간 = 기존 now - a

프로세스 총 소요시간 = (기존 now-a) + b == (업데이트 완료한 now) - a

프로세스 끝난 후 현재 시각 업데이트 now = 기존 now+b

2️⃣ elif 현재 시각(now) < 현재 프로세스 요청 시각:

기다린 시간 = 0

프로세스 총 소요시간 = b == (업데이트 완료한 now) - a

프로세스 끝난 후 현재 시각 업데이트 now = a+b

3. 그런데 어떻게 정렬하지.. (생각의 무한루프 ♾️🥲 again)

끄적이다 겨우 알아낸 사실:

- 상수인 것을 제외하고 변수인 것을 비교하자. 

- 프로세스 소요시간이 짧은 것부터 정렬해야 한다.

- 조건에 의해, 작업을 수행하고 있지 않을 때에는, 먼저 요청이 들어온 작업부터 처리해야 하므로 → 현재 시각 이전에 요청된 프로세스 먼저 처리하고 → 나머지를 처리해야 한다.

- 현재 시각 이전에 요청된 프로세스 즉 대기 중인 프로세스를 waitlst에 저장 1️⃣

- 단, 대기 중인 프로세스가 없는 경우도 있다! 2️⃣ 

▶ waitlst가 비어 있지 않은 경우 1️⃣
    → jobs 리스트에서 소요시간이 가장 짧은 것을 먼저 waitlst에 heappush
    → 단 waitlst 내부에서는 '소요시간'을 기준으로 정렬해야 하므로, for문 heappush 시 인덱스 위치를 바꾼 채로.

▶ waitlst가 비어 있는 경우(=요청이 가장 이른 다음 프로세스가 현재 시각 이후에 요청될 때) 2️⃣ 
    → 시각을 옮겨주어 다음 프로세스가 바로 시작될 수 있도록 세팅한다: now = 요청시각
    → 가장 이른 프로세스를 jobs 리스트에서 heappush, 마찬가지 인덱스 위치를 바꾼 채로.

▶ 1️⃣&2️⃣ 거친 후
→ now += 소요시간
→ 프로세스 총 소요시간: now - 요청시각
→ total.append(now - 요청시각)

▶ 서로 다른 계산식을 가지는 1️⃣&2️⃣를 잘 처리함으로써 결과적으로 동일한 state가 되도록 일치시킴
→ now 및 total 계산식을 간단히 공유할 수 있게 됨.

▶ 마무리: int(total / len(jobs)) OR total // len(jobs)

*소수점 이하의 수는 버림 조건 매우 주의
*조건 상 분모가 0이 될 수 없으므로 해당부분은 pass.

나의 코드

from heapq import heapify, heappop, heappush

def solution(jobs):
  j_len = len(jobs)
  heapify(jobs)
  now = 0
  total = []
  waitlst = [] #waitlst의 위치 중요

  while len(total)<j_len:
    while jobs and (jobs[0][0] <= now):
        next = heappop(jobs)
        heappush(waitlst, (next[1],next[0]))

    if jobs and waitlst == []:
      next = heappop(jobs) #jobs에서 다음 활동 next 직접 꺼내기
      now = next[0] #next 진행되도록 시간 세팅
      heappush(waitlst, (next[1], next[0])) #next를 waitlst에 직접 추가
    
    x,y = heappop(waitlst)
    now += x #프로세스 진행하였으므로 진행시간 포함하여 현재 시간 업데이트 
    total.append(now-y)
  
  answer = sum(total)//j_len
  return answer

• 현재 시각 now의 업데이트 아이디어 중요 ⭐
• indentation & while문 & if문 조건 엄밀하게 설정해야 함 ⭐
• 리스트를 heap으로 변환 안 하더라도, 리스트 자체로 heappop 바로 쓸 수 있구나.
• jobs는 리스트 그대로 두고, wait할 원소를 pop하기만 함 → waitlst에서 사용되지 않은 원소를 jobs로 되돌릴 필요 없음
• waitlst가 heap이며, waitlst 내에 새로운 원소가 들어올 때마다 힙정렬. (heappop, heappush 시 자동 힙정렬)
• waitlst가 비어있을 때 jobs 리스트 첫번째 원소의 시작 시간으로 now를 맞춤 

while len(total)<j_len:

• 이때 while jobs 하면 안 됨. jobs가 모두 pop되어 빈 리스트가 되더라도, waitlst에는 처리할 작업이 남아 있을 수 있음.

while jobs and (jobs[0][0] <= now):

• "jobs 리스트가 비어있지 않고" and "jobs[0][0] <= now" 동안에 계속.

if jobs and waitlst == []:

• "jobs 리스트가 비어있지 않고" and "waitlst는 비어있을 때" 한번.

heappush(waitlst, (next[1],next[0]))

• heap은 기본적으로 원소의 0index를 기준으로 정렬하므로, 이같이 인덱스 뒤집어 힙정렬 처리 필요.

다른 코드

import heapq

def solution2(jobs):
    answer, now, i = 0, 0, 0
    start = -1 
    heap = []
    
    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        
        if len(heap) > 0: # 처리할 작업이 있는 경우
            cur = heapq.heappop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
            i +=1
        else: # 처리할 작업이 없는 경우 다음 시간을 넘어감
            now += 1
                
    return answer // len(jobs)

왜 틀렸을까 .. 19번 실패

19번 관련 테스트케이스 모두 통과인데,,

아래 코드!

from heapq import heapify, heappop, heappush
from collections import deque

def solution(jobs):
  j_len = len(jobs)
  heapify(jobs)

  end = 0
  total = 0
  while jobs:
    waitlst = []

    while jobs[0][0] <= end:
        a = heappop(jobs)
        waitlst.append(a)
        if len(jobs) == 0:
            break

    if waitlst:
      waitlst.sort(key=lambda x: x[1])
      waitlst = deque(waitlst)
      next = waitlst.popleft()

      end+= next[1]
      present = (end-next[0])
      for i in waitlst:
        heappush(jobs, i)

    else:
      next = heappop(jobs)
      end += (next[0]+next[1])
      present = next[1]

    total += present

  answer = int(total/j_len)
  return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42584

개요

prices: 초 단위로 기록된 주식가격이 담긴 배열

return: 가격이 떨어지지 않은 기간은 몇 초인지

[1, 2, 3, 2, 3] → [4, 3, 1, 1, 0]

나의 코드

from collections import deque

def solution(prices):
  answer = []
  idx_prices = deque(enumerate(prices))
  for _ in prices:
    idx, n = idx_prices.popleft()
    t = len(prices)-idx
    for i in range(t):
      if i == t-1:
        answer.append(t-1)
      else:
        if n > prices[idx+i+1]:
          answer.append(i+1)
          break
        else:
          continue
  return answer

정답 도출은 쉬웠으나, 시간 효율 문제 개선이 어려웠음.

• for _ in range(len(prices)-idx)에서 len 부분이 시간복잡도 심각.
  어차피 _ 사용할 거 아니라면,  for _ in prices로 대체
• 하나의 for문 안에 len(prices)-idx를 여러번 사용하였는데, 실행마다 len의 시간복잡도가 거듭되므로,
  t라는 변수에 저장한 후 t를 호출하는 게 훨씬 나음
• list 사용을 최소화할 것! reverse문도 안 먹혔던 이유 → queue와 deque를 이용하자 (pop, popleft..)
• enumerate 사용하지 않을 방법 모색해보자.

시간 초과 (실패) 코드

from collections import deque

def solution(prices):
  answer = []
  idx_prices = deque(enumerate(prices))
  for _ in range(len(prices)):
    n = idx_prices.popleft()
    try:
      small_idx = [x[0] for x in idx_prices if x[1]<n[1]][0]
      answer.append(small_idx-n[0])
    except:
      answer.append(len(prices)-n[0]-1)

  return answer

- try, except 이하가 애초에 비효율적이긴 하였음: 리스트 모두 완성 후 첫번째 원소만 사용하는 것이기 때문.

- 이외 이유는 상단에 기술.

모범 코드

1. 큐 활용

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        c = prices.popleft()

        count = 0
        for i in prices:
            if c > i:
                count += 1
                break
            count += 1

        answer.append(count)

    return answer

2. 빠르며 깔끔

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        if stack != []:
            while stack != [] and stack[-1][1] > prices[i]:
                past, _ = stack.pop()
                answer[past] = i - past
        stack.append([i, prices[i]])
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42583

문제 개요

[input]
bridge_length: 트럭 수
weight: 다리가 견딜 수 있는 무게
truck_weights: 트럭 별 무게

[return]
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지

나의 코드

def solution(bridge_length, weight, truck_weights):
    answer = 0
    road = [0]*bridge_length
    x = truck_weights.pop(0)
    sum_weight = 0 

    while len(truck_weights)>=0:
        sum_weight-=road[0]
        road.pop(0)
        road.append(0)
        if sum_weight+x <= weight:
            road[-1]=x
            sum_weight+=x
            answer+=1
            if len(truck_weights)>0:
                x = truck_weights.pop(0)
            else:
                answer+=bridge_length
                break

        else:
            answer+=1

    return answer

• 시간초과 문제
  • sum 함수가 시간초과 요인임! : 
    sum_weights=0 한 후
    루프 돌 때마다 weight을 -+= 하는 게 훨씬 좋음.
  • 리스트의 맨 처음 원소를 pop하고 싶을 때, pop(0)은 시간초과 가능하므로
    아래 두 가지 대안
    1) .popleft()
    2) truck_weights.reverse() 이후 .pop()
• TypeError: 'NoneType' object is not subscriptable
  - 코랩에서 if문에 화살표 가리키더라도,  첫 코드부터 혹은 그 코드자체가 처음부터 틀렸다는 게 아니라,
    여러 번 루프 돌린 후 해당 if문에 문제가 생겼다는 거
  - 문제의 코드: road = road[1:].append(0) 
     → None을 반환함, road[1:] 처리 후, 다음 줄에서 append. 따로 실행해야 함 (최종 코드에는 아예 pop(0)으로 대체)
  - 본 에러메시지는, 주로 리스트가 비어있는데 index에 접근하는 등, 빈 리스트에 특정 처리를 하면 발생.

모범 코드

1. 리스트.reverse 이후 pop() & deque 함수 사

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step

2. 간결함

def solution(bridge_length, weight, truck_weights):
    q=[0]*bridge_length
    sec=0
    while q:
        sec+=1
        q.pop(0)
        if truck_weights:
            if sum(q)+truck_weights[0]<=weight:
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
    return sec

*sum 함수 수정 필요

• "while 변수: "
  0이나 null값일 경우 False이기때문에, 빈리스트가 아니라면 True가되어 실행되는 함수
  ex) while truck_weights: / while q:

https://school.programmers.co.kr/learn/courses/30/lessons/42587

문제 개요

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다.

(숫자가 클 수록 더 중요한 문서)

input
-priorities: 문서의 중요도가 순서대로 담긴 배열
-location: 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지.

return
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지.

나의 코드

def solution(priorities, location):
  pri_tuple = list(enumerate(priorities))
  target_tup = pri_tuple[location]
  i=0
  while target_tup in pri_tuple:
    (max_idx,max_val) = sorted(pri_tuple, key=lambda x: x[1], reverse=True)[0]
    max_value = (max_idx,max_val)
    if pri_tuple[0][1] != max_val:
      back_lst = pri_tuple[0:pri_tuple.index(max_value)]
      del pri_tuple[0:pri_tuple.index(max_value)]
      pri_tuple.extend(back_lst)
    else:
      pri_tuple.pop(0)
      i+=1
  answer = i
  return answer

• 나의 아이디어:
  현재 리스트에서 max값을 찾고 → 리스트의 첫번째 원소~max값 직전 원소까지 그대로 슬라이싱하여
  → 리스트 맨 끝에 갖다 붙임: max값이 리스트의 맨 앞에 위치하게 됨 → 해당 max를 pop하여 제거 (i +1)
• 매개변수 location이 원본 priorities에 대한 index 값이므로, 원본 index 값을 저장하기 위해 enumerate 사용
  → priorities 리스트의 각 원소가 (idx, value)의 튜플 형태로 저장됨
• while문을 사용 (단, 무한루프의 위험 있으므로 while true는 지양하는 것이 좋음)
• max값을 찾기 위해 튜플로 이루어진 pri_tuple 리스트를 sorted함 (정렬 기준이 value값이므로, key, lambda를 이용)
• 추가 테스트케이스에서 문제가 생겼던 부분 😂
  1) while target_tup in pri_tuple에서, while문 내부의 pri_tuple이 새로 업데이트될 때 마다, 해당 while문의 pri_tuple도 함께 바뀜
  2) 따라서 max_value, max_idx, max_val도 함께 업데이트됨
  3) max_value자체가 튜플 형태이고, pri_tuple 리스트 애 max_value의 대상이 되는 원소 자체는 바뀌지만, 해당 원소 내부의 내용이 바뀌지는 않음 (초반에 enumerate로 정의되었기 때문에) → max_value의 max_idx와 pri_tuple.index(max_value)값은 엄연히 다름!!! 아예 다른 내용을 가리킴.
• pop은 디폴트로 맨 마지막 값을 삭제하지만, 원하는 인덱스의 원소를 삭제할 수도 있음
• 리스트의 조작: del 리스트[삭제할 원소 슬라이싱] / 리스트.extend(연장할 리스트 내용)

https://dojang.io/mod/page/view.php?id=2281 

모범 풀이

1. any 함수의 활용

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

• 원소 하나씩, 하나씩. any니까 괜찮음
• [(i,p) for i,p in enumerate(priorities)]
  list comprehension에서 튜플을 다루는 법! 단순하지만 유용함
• ⭐⭐ 파이썬의 any, all 함수 ⭐⭐
  any() : 하나라도 True인게 있으면 True
  all() : 모두 True여야 True 반환
  →  아큐먼트로 iterable한 객체를 받음. (ex list)
  →  이 객체를 돌면서 조건을 검사해 답을 True/False의 답을 반환
  any(x, y for y in y_list) = True/False
  any()는 특히 대소비교를 할 때 사용하면 sort보다 실행시간을 많이 줄일 수 있다. 예를 들어 어떤 수와 어떤 리스트의 원소들을 비교하는데 해당 수가 리스트 안의 max값보다 큰지만 알고 싶다고 하자. 이 때, sort를 사용한 뒤 비교하면 리스트를 모두 정렬하기 때문에 시간이 걸린다. 하지만 any를 쓰면 리스트 내에 해당 수보다 큰 수가 있기만 하면 바로 True를 return하고 끝내기 때문에 시간이 덜 걸린다. 
  
  if 조건과 함께 다음과 같이 사용할 수도 있다.

cur = 3
temp = [1,3,6,2]
if any(cur<num for num in temp):
	print("There exist number that is larger than 3")

2. deque의 활용 -> 효율성 향상

def solution(p, l):
    ans = 0
    m = max(p)
    while True:
        v = p.pop(0)
        if m == v:
            ans += 1
            if l == 0:
                break
            else:
                l -= 1
            m = max(p)
        else:
            p.append(v)
            if l == 0:
                l = len(p)-1
            else:
                l -= 1
    return ans