알고리즘 문제풀이/프로그래머스7

• 

  [2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr import heapq INF = 987654321 def f(graph,s,n): dist = .. 알고리즘 문제풀이/프로그래머스 2021. 5. 8.

• [2018 KAKAO BLIND RECRUITMENT] 셔틀버스 programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr def append_waiting(start,end,datetimes): global waiting while datetimes: if start 알고리즘 문제풀이/프로그래머스 2021. 5. 8.

• [2019 카카오 개발자 겨울 인턴십] 불량 사용자 programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr def change_v_to_bit(v): bit = "" for i in range(len(v)): bit += str(v[i]) return bit def is_in(bit): global result if bit in result: return True return False def match(ban,user): if len(ban) != len(user): return.. 알고리즘 문제풀이/프로그래머스 2021. 5. 5.

• [프로그래머스lv.3] 정수 삼각형 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 깊이를 i 라고 봤을 때 i-1 번째 깊이엣 ㅓ어떤 숫자를 선택했느냐에 따라 결과값이 달라진다. 즉 dp 문제이다. 깊이를 i, i번째 배열에서의 인덱스를 j라고 해보자 i번째깊이의 j번째 수의 합의 최대값은 무엇일까? 답은 i-1번째 깊이의 j-1번째수까지의 최대값과 j번째수까지의 최대값중 큰 값 + i번째깊이의 j번째 수일 것이다. dp[i][j] = i번째 깊이의 j번째 인덱스가 가지는 합의 최댓값이다. 즉 dp[i][j] = max(dp[.. 알고리즘 문제풀이/프로그래머스 2021. 5. 4.

• [프로그래머스lv3] [2020 카카오 인턴십] 보석 쇼핑 programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 gems에서 보석을 차례대로 반복문에 넣는다. 큐에 차례때로 보석을 넣어준다. 또한 보석의 수를 효율적으로 계산하기 위해 dict를 따로 만들어 요소의 수를 기록한다. set을 통해 큐에 모든 보석이 들어갔는지 확인한다. 모든 요소가 들어갔다면 현재 상태를 저장한다. 나중에 답 비교를 위해 우선순위 큐에 [큐길이, 시작위치] 로 저장한다. 큐의 첫번째 보석의 수가 2 이상이라면 현재 큐를 한 번 pop를 해주고 해당 보.. 알고리즘 문제풀이/프로그래머스 2021. 5. 4.

• 

  [프로그래머스lv.3] 순위 programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 풀이 그래프를 그려본다. 그래프를 그려보고 경로가 다른 노드들과 모두 이어져 있는 노드를 찾는다. 4는 모든 녀석과 이어져 있다. 1은 3을 모르고 2는 6을 모르고 3은 1을 모르고 5는 3을 모르고 6은 2를 모른다. 여기서 4라는 모든 경로와 이어진 노드를 어떻게 찾을 수 있을까? 플로이드 와샬을 활용하면 된다. 플로이드 와샬은 모든 노드의 최단거리를 찾아준다. 그 점을 이용해서 노드가 이어져 있는지를 확인한다. 최단거리가 존재하지 않다면 경로가 없다는 것이다. 백준의 [245.. 알고리즘 문제풀이/프로그래머스 2021. 5. 4.

• [프로그래머스.lv3] 입국심사 programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 풀이 (시간초과) 심사관이 일이 끝나는 시간 리스트를 만든다. 각 심사관의 시간만큼 더한 후 가장 일이 일찍 끝나는 심사관을 찾는다. 그 심사관에게 일을 맡긴다. 해당 심사관의 일이 끝나는 시간을 늘려준다. 심사관 수를 t라고 했을 때 한명을 처리하는데 가장 작은 심사관을 찾기 때문에 O(t)만큼 걸린다. n명을 처리하니 시간복잡도는 O(tn)이다. t는 최대 100000이고 .. 알고리즘 문제풀이/프로그래머스 2021. 5. 3.