Computer Vision 대학원생 기록지

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

비교적 간단했던 문제

def solution(name, yearning, photo):
    answer = []
    ppl_dict = dict(zip(name, yearning))
    
    for p in photo:
        score = 0
        for person in p:
            try: score += ppl_dict[person]
            except: pass
        answer.append(score)
    
    return answer

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

시간 초과로 인해 까다로웠던 문제였다.

가장 처음에는 시간을 아끼고자 dictionary를 사용하여 접근하였다.

def solution(players, callings):
    num = [i for i in range(len(players))]
    counts = dict(zip(num, players))
    
    for calling in callings:
        i = list(counts.values()).index(calling)
        winner, loser = counts[i], counts[i-1] 
        counts[i], counts[i-1] = loser, winner
        
            
    orders = sorted(counts.items())
    answers = [i[1] for i in orders]
    return answers

하지만 이런 처참한 결과를 맞이하였다.

결국 index 함수를 사용한 것이 계산 비용을 높인 것으로 추측되어 해당 line을 수정하였다.

def solution(players, callings):
    num = [i for i in range(len(players))]
    counts = dict(zip(players, num))
    for calling in callings:
        winner_i, loser_i = counts[calling] - 1, counts[calling]
        counts[calling] = winner_i
        counts[players[winner_i]] = loser_i
        
        #players update
        players[winner_i], players[loser_i] = players[loser_i], players[winner_i]
    
    return players

코딩테스트 연습 - 빛의 경로 사이클 | 프로그래머스 (programmers.co.kr)

REVIEW

• graph와 경로의 길이를 보고 bfs 문제인가 싶지만 여러 대안 경로 중에서 나은 것을 선택하는 것이 아니라, 각 node 마다 주어진 S, R, L 명령구에 따라 경로가 정해지기 때문에 bfs로 풀 필요가 없다. 
• 같은 노드여도 어느 방향에서 들어왔는지에 따라 구분되기 때문에 visited를 만들 때 3차원으로 만들어 방향 정보를 추가하였다. 따라서 node b에서 북쪽으로 나아갔다면, 다음 번에 node b에서 남쪽으로 나아갈 때는 visited 여부가 False가 된다.
• 방문한 적 없는 노드에서 시작하여 방문한 적이 있는 노드에 방문하게 된 경우 사이클이 발생한 것이다.
• 이전 사이클에서 이미 방문한 노드가 이번 사이클에서 방문한 것으로 오인되는 것이 아닌가라고 생각할 수 있지만, 동일한 경로가 아닌 이상 동일한 노드에 대하여 동일한 방향으로 방문하는 일은 없다. (각 노드마다 변하지 않는 명령구가 있기 때문이다.) 
• 또한 이러한 특성 덕분에 중복되는 경로를 answer에 추가하는 경우를 피할 수 있었다.

# direction: north=0, east=1, south=2, west=3
from collections import deque


def direction(oper, d):
    
    if oper == 'L': 
        d = (d-1)%4
    elif oper == 'R': 
        d = (d+1)%4
    return d
    
def bfs(x, y, d, width, height, graph, grid):
    
    count = 0
    start = [x, y, d]
    while True:
        # add current node to Visited
        if graph[x][y][d]:
            ans = count
            count = 0
            return ans
        graph[x][y][d] = 1
        count += 1
        
        # Move
        # to North
        if d == 0:
            x = (x+1)%height
        # to East
        elif d == 1:
            y = (y+1)%width
        # to South
        elif d ==2:
            x = (x-1)%height
        # to West
        else:
            y = (y-1)%width
        
        # change direction
        d = direction(grid[x][y], d)
        
def solution(grid):
    graph = [[[0, 0, 0, 0] for _ in range(len(grid[0]))] for _ in range(len(grid))]
    answer = []
    
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for k in range(4):
                if graph[i][j][k] != 1:
                    num = bfs(i, j, k, len(grid[0]), len(grid), graph, grid)
                    answer.append(num)
    answer.sort()
    return answer

9461번: 파도반 수열 (acmicpc.net)

REVIEW

• P(N)이 증가하는 패턴만 알아내면 어렵지 않게 풀 수 있는 문제이다.
• P(1), P(2), P(3)은 1이다. 
• P(4)부터는 패턴이 있는데 바로 P(N)은 P(N-2) + P(N-3)과 일치한다는 것이다.
• 예를 들어서 P(4)는 2로, P(2)의 1, P(3)의 1의 합과 동일하다. 
• 따라서 N > 3일 때, P(N) = P(N-2) + P(N-3)이다.

t = int(input())

for _ in range(t):
    n = int(input())
    dp = [1] * (n+1)
    if n > 3:
        for i in range(4, n+1):
            if t == 4:
                dp[4] = 2
            else:
                dp[i] = dp[i-3] + dp[i-2]
    print(dp[n])

코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr)

REVIEW

• DB 캐시에 대한 배경지식이 있어야 문제 풀기가 수월하다. 
• DB 캐시는 트래픽으로 인한 서버 다운, 웹 또는 어플리케이션 서비스 이용 속도를 개선하기 위하여 임시 데이터를 캐시에 저장하여 정보가 필요할 경우 캐시에 access하는 방식이다. 
• 필요 정보가 캐시에 있을 경우를 cache hit이라고 하며, 그 반대의 경우를 cache miss라고 한다.
• 이러한 작동방식을 그대로 코드로 구현하였다. 
• 새로운 정보가 들어올 때는 cache의 가장 오른쪽에, 기존 정보가 cache에서 탈락할 때는 가장 왼쪽 것부터 탈락하게 만들어 LRU를 구현하였다. 왼쪽에서 pop을 효율적으로 수행하기 위해 deque를 사용하였다. 
• cache hit일 경우 answer에 1을 더하였다. 그리고 cache 안에 있던 해당 city를 삭제하고 새롭게 cache 오른쪽에 삽입하였다. (가장 최근에 사용된 데이터이기 때문)
• cache miss일 경우 항상 answer에 5을 더하였다. cache가 비어있을 수도 있기 때문에 에러를 방지하고자 우선 city를 추가한 후, cachesize 초과 여부에 따라 popleft( )를 수행하였다. 

from collections import deque
def solution(cacheSize, cities):
    answer = 0
    cache = deque()
    for city in cities:
        city = city.upper()
        if city in cache:
            cache.remove(city)
            cache.append(city)
            answer += 1
        else:
            cache.append(city)
            if len(cache) > cacheSize:
                cache.popleft()
            answer += 5

    return answer

다른 사람들의 코드를 보니 굳이 cache 길이를 재며 popleft( ) 여부를 결정하는 것 대신, 이렇게 deque(maxlen=cacheSize) cache 자체에 최대 길이를 설정하여 자동적으로 cache 길이 관리하는 것이 더 나아보인다.

https://programmers.co.kr/learn/courses/30/lessons/49993/

REVIEW

• deque의 popleft()를 사용하여 pop(0)보다 더 효율적으로 앞선부터 element를 추출하였다. 
• 순서에 따라야 하는 스킬만 tree에 남게하였기 때문에 skill과 tree에서 차례대로 추출된 element는 동일하여야 한다. 동일하지 않을 경우 순서가 skill과 tree의 스킬 순서가 다르다고 해석할 수 있다. 
• popleft( )로 skill과 tree의 element를 차례대로 추출하여 비교하였다. 하지만 skill에 더 이상 남은 스킬이 없는데 tree에는 있는 경우, 또는 반대로 tree에 더 이상 남은 스킬이 없는데 skill에는 있는 경우가 있을 수 있기 때문에 skill과 tree 둘다 element가 있을 경우에만 추출-비교 작업을 수행하도록 하였다. 
• 비교 과정을 status에 기록하였다. 

from collections import deque

def solution(skill, skill_trees):
    answer = 0

    for tree in skill_trees:
        # skill에 있는 기술만 추출
        tree = deque([x for x in tree if x in skill])
        skill2 = deque(skill)

        status = True
        # skill과 tree에 element가 존재할 때만 반복하여 pop from empty list 에러 방지
        while skill2 and tree:
            if skill2.popleft() != tree.popleft():
                status = False
                break
		# element가 불일치한 적이 없고 tree에만 잔여 스킬이 있는 것이 아니라면 count
        if status and len(tree) == 0: answer += 1


    return answer

다시 코드를 리뷰하니 skill에 남은 스킬이 없는데 tree에는 스킬이 아직 남아있어서 pop from empty list 에러가 발생하지 않았을 것이라는 점을 깨닳았다.

tree에는 중복되는 스킬이 없다보니, skill에 포함된 스킬만 남아있는 tree의 길이는 항상 skill보다 짧거나 동일하기 때문이다. 

따라서 어차피 while문이 끝났을 때는 tree가 empty할 테니 len(tree) == 0을 count 조건에 지정할 필요가 없었다. 

이를 반영하여 개선한 코드는 다음과 같다:

from collections import deque

def solution(skill, skill_trees):
    answer = 0

    for tree in skill_trees:
        tree = deque([x for x in tree if x in skill])
        skill2 = deque(skill)

        status = True
        while tree:
            if skill2.popleft() != tree.popleft():
                status = False
                break

        if status: answer += 1


    return answer

10845번: 큐 (acmicpc.net)

REVIEW

• 문제에서 요구하는 pop은 리스트에 사용되는 pop( ) 명령어와 다르다. pop( )은 리스트 가장 마지막 element를 추출하는 반면, 문제에서는 큐의 첫 번째 element를 추출할 것을 요구한다. 
• 문제를 리스트로 구현할 시에 가장 앞에 있는 element를 pop(0)으로 추출할 수 있지만, 시간 복잡도가 O(N)이 되어 효율적인 방법이라고 볼 수 없다. 
• 따라서 이번 문제를 구현하기 위해서는 리스트가 아닌 collections 라이브러리의 deque를 사용하였다. 
• deque에서 가장 앞에 있는 element를 추출하기 위해서는 popleft( ) 명령어를 사용하면 된다. 해당 과정의 시간 복잡도는 O(1)으로 리스트의 pop(0)보다 훨씬 더 효율적이다. 

from collections import deque
import sys

N = int(input())
# 큐 생성
queue = deque()

for n in range(N):
    cmd = sys.stdin.readline().split()

    if cmd[0] == 'push':
        queue.append(int(cmd[1]))

    elif cmd[0] == 'pop':
        # 가장 왼쪽에 있는 element 추출
        try:
            print(queue.popleft())
        # 큐에서 추출할 element가 없을 경우
        except:
            print(-1)

    elif cmd[0] == 'size':
        print(len(queue))

    elif cmd[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else:
            print(0)
 
    elif cmd[0] == 'front':
        # 가장 왼쪽에 있는 element 조회
        try:
            print(queue[0])
        # 큐에서 조회할 element가 없을 경우
        except:
            print(-1)

    elif cmd[0] == 'back':
        # 가장 마지막에 있는 element 조회
        try:
            print(queue[-1])
        # 큐에서 조회할 element가 없을 경우
        except:
            print(-1)

다른 풀이를 보니 함수를 이용한 코드가 속도가 더 빠른 듯하다.