B_log

문제 문제 상황 - 트래픽을 계산하는데에 조건에 맞춰 최대로 겹치는 개수는 구한다. 해결 전략 - 우선 주어진 시간을 계산하기 쉽게 전부 초(sec)로 변환해준다. 그리고 float의 경우 계산에 오류 발생 가능성이 크기 때문에 소수점 세자리가 제한인 것을 고려해 1000을 곱하여 정수로 처리해준다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 # 날짜를 넣으면 시작시간과 종료 시간을 반환하는 함수 # 날짜는 고정되어 있으므로 시간, 분, 초만 생각하면 된다. def time_log(line): # 2016년 9월 15일은 고정, 종료 시간, 프로세스 시간 yymmdd, hhmmss, process = l..

문제 programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스�� programmers.co.kr 문제 상황 - 스테이지에 도달한 사람과 통과한 사람수를 계산해서 정렬한다. 해결 전략 - 레벨을 기준으로 순회하며 stages에서 통과한 사람과 도달한 사람으로 구분하여 카운팅한다. - 실패율을 인덱스와 함께 튜플로 선언해 다시 리스트로 만든 뒤, 내용물을 기준으로 정렬하고 마지막에 순서대로 인덱스를 담는다. 단, 0번째의 경우 실패율에 존재하지만 실제로는 1부터 N..

문제 문제 상황 - 프로세스에 작업 우선순위를 정하는 문제다. 단순히 들어온 순서대로 작업이 진행되는 것이 아니라 작업이 대기열에 올라온 후 완료될 때까지 시간의 합 평균이 가장 작게 작업을 하는 순서를 정하는 문제이다. 소수점 이하는 버리고 그 평균 시간을 출력한다. 해결 전략 - 최소, 혹은 최대의 요소를 선택할 때 heap 자료구조를 사용한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import heapq def solution(jobs): heapq.heapify(jobs) # 작업의 수 cnt = len(jobs..

문제 - 이진 탐색으로 페이지를 검색할 때, A와 B 중 누가 더 빨리 찾는 지를 찾는다. 문제 상황 - 찾아야할 페이지, 책의 전체 쪽 수가 주어진다. 비긴 경우는 0을 출력한다. 해결 전략 - binary search를 사용하며 search 횟수를 기록하여 비교한다. binary search 함수를 따로 만들어 검색하게 하면 될 것 같다. 재귀로 만들 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 def binary_search(target, counts, start, end): c = int((start + end)/2) # target과 만났을 때, count 출력 if c == target: ret..

최적 부분 구조 - 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 최적 부분 구조 조건을 성립한다고 한다. (예시) - 서울에서 부산을 가는 최단 경로의 경우 이 최단 경로가 대전을 지난다고 가정한다. 이 때, 최단 경로는 (서울, 대전)의 최단경로, (대전, 부산)의 최단 경로를 찾아서 이으면 구할 수 있다. 즉 부분문제를 통해 전체의 최적해를 구할 수 있으므로 이는 최적 부분 구조라고 할 수 있다. 최적 부분 구조가 존재하지 않을 경우 - 서울에서 부산으로 향하는데 고속도로의 통행료 합이 3만원을 초과하지 않는 최단경로를 찾을 때, 대전에서 부산으로 가는 경로가 2가지 있다. 통행 시간 통행료 경로 A 2 시간 1만원 경로 B 1 시간 2만원 - 이 두 경로 중 어느..

문제 문제 상황 - 숫자 string과 제거할 숫자의 개수를 입력받아 숫자를 제거하여 얻을 수 있는 가장 큰 숫자를 찾는다. 해결 전략 - number의 자리가 최대 100만 자리 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def solution(number, k): stack = ["0"] # 처음 빈문자를 넣었으므로 0을 지우기 위해 k를 하나 증가시킨다. k += 1 for i in range(len(number)): if k == 0: stack.append(number[i]) continue while k > 0: # 비어있지 않으면 number[i]로 계속 비교해 나간다. stack의 마지막 값보다 # number[i]가 더 크면 stack..

문제 문제 상황 - 하노이의 탑을 옮기는 과정을 리스트에 담아 출력한다. 해결 전략 - 하노이의 탑에서 중요한 것은 시작점, 경유점, 도착점이 바뀐다는 사실과 전체 문제가 부분 문제로 이루어져있다는 사실이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # 출발노드, 경유노드, 도착노드, 판의 수 def hanoi(start_node, pass_node, desti_node, n): global result if n == 1 : return [start_node, desti_node] else : result.append(hanoi(start_node, desti_node, pass_node,n-1)) result.append([start_node, desti_node]) ..

문제 문제 상황 - 주어진 문자열 내에 존재하는 회문을 찾아 그 가장 긴 길이를 반환하는 문제이다. 해결 전략 - 주어진 조건이 2,500자로 O(N^2)을 해도 6,250,000로 매우 안정적인 범위이다. 회문을 검사하는 함수를 만들고 검사할 시작점과 끝점을 탐색하며 양 끝이 같아질 경우만 그 사이 리스트를 회문 검사 하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def is_palindrome(lst): if len(lst)%2 == 0 and lst[:len(lst)//2] == lst[len(lst)//2:][::-1]: return True elif len(lst)%2 == 1 and lst[:len(lst)//2] == lst[(len(lst)//2)+1:][:..