백준11404번 플로이드 2021.06.20 플로이드 Solution 플로이드 알고리즘으로 해결하였습니다. input start, end 로 2차원 배열(input_map) 에 cost 저장 노선이 여러개일 경우 짧은 것으로 갱신 floyd 알고리즘으로 모든 최단 경로 찾기 결과가 inf 인 경우, 경로가 없는 것이므로 0으로 수정 (문제 조건) Source # 2021.06.20 inf = int(1e9) def floyd(input_map, V): for i in range(V): input_map[i][i] = 0 for k in range(V): for i in range(V): for j in range(V): input_map[i][j] = min(input_map[i][j], input_ma..

백준18353번 병사 배치하기 2021.06.16 병사배치하기 Solution LIS (Longest Increasing Sequence) 를 내림차순으로 변형하여 풀이하였습니다. 0 ~ N-1 을 돌며 DP[N]을 구합니다. (n) DP[N] = DP[N-i] + 1 (i = 0 ~ n-1) N-i번보다 N번이 작으면 N-i번 오른쪽에 N번이 위치할 수 있고, 이렇게 했을 때 N-i번의 최대 길이에 +1 한 것이 N번의 최대길이 후보가 됩니다. 0 ~ n-1 을 돌며 왼쪽 부분수열 중 n번이 오른쪽에 놓일 수 있는 후보를 고릅니다. +1 한 값과 비교해 DP[n]을 업데이트합니다. DP[N] 중 최댓값을 N에서 뺀 값이 정답입니다. Source # 2021.06.16 병사배치하기 # Solution :..

2021.06.12 정수삼각형 Solution DFS : 삼각형의 꼭대기에서부터 아래 or 오른쪽아래로 깊이우선탐색을 합니다. DFS로 탐색을 구현할 때 리턴하는 값은 다음과 같이 설정할 수 있습니다. 맨 아래인 경우 : 해당 노드의 값 맨 아래가 아닌 경우 : 해당 노드의 값 = 그 다음노드부터 맨 아래까지의 최대경로 이렇게 설정하면 결국 재귀로 구현한 깊이우선탐색의 최종 반환 값이 원하는 결과가 됩니다. DP : 위의 DFS에서 각 노드를 탐색할 때, 이미 탐색한 적이 있는 경우 메모이제이션 을 활용할 수 있습니다. 해당 노드부터 맨 아래까지의 경로 중 최댓값을 DP 배열에 저장하고, 이미 탐색한 적이 있는 경우 (DP 배열이 초기값이 아닌경우) 에는 메모이제이션 해둔 값을 반환하도록 합니다. Sou..

2021.06.12 퇴사 Solution DFS : 특정 일자에 상담이 가능한지 그 뒤(다음 깊이탐색)로 상담이 가능한지를 재귀적으로 깊이우선탐색합니다. 재귀함수는 다음과 같이 구현할 수 있습니다. 기저조건 : N+1일째 이상을 탐색할 경우 퇴사이므로 0을 리턴합니다. 재귀함수 정의 : 특정 날짜를 입력받아 퇴사할때까지 상담으로 받을 수 있는 금액의 최댓값을 반환하는 함수 해당 날짜의 고객을 상담할 수 있는지 확인합니다. 상담할 수 있다면 금액을 초기값으로 설정하고, 다음 탐색할 노드들을 탐색하고 그 중 최댓값을 더해 반환합니다. DP : 특정 날짜에부터 퇴사일까지 받을 수 있는 최댓값을 메모이제이션합니다. 재귀함수에서 DP에 기록이 되어있다면 반환하도록 하여, 중복된 탐색을 제거할 수 있습니다. Sou..

2021.05.17 공유기설치 Solution 가장 인접한 두 공유기 사이의 최대거리를 x라고 하겠습니다. x의 최소값은 두 집이 인접할 때의 거리인 1이고, 최대값은 가장 오른쪽집 - 가장 왼쪽집이 됩니다. (1 = C: return True else: return False def solution(N, C, home): ret = None home.sort() dist = [] for i in range(N): for j in range(i+1, N): if home[j]-home[i] not in dist: dist.append(home[j]-home[i]) dist.sort() # Binary Search start = 0 end = len(dist) - 1 if CanBuild(N, C, hom..

2021.05.17 카드정렬하기 Solution 계속해서 두개씩 합치는 작업을 해야하고, 합쳐진 묶음은 하나의 묶음이 됩니다. 합치는 작업의 횟수는 결국 N-1번이고, N-1동안 최소로 합치는 작업을 하기 위해서는 계속해서 제일 작은 두 묶음을 합쳐야합니다. 이를 위해서 Heap 자료구조를 사용해서 가장 작은 값 두개를 pop 해서 합한 값을 push 하도록 구현하였습니다. import heapq N = int(input()) myHeap = [] result = 0 for _ in range(N): heapq.heappush(myHeap, int(input())) while len(myHeap) > 1: num1 = heapq.heappop(myHeap) num2 = heapq.heappop(myHea..

2021.05.10 실패율 Solution index는 스테이지-1로 되도록 리스트를 사용. 스테이지에 도달했던사람, 클리어하지 못한스테이지 인원 파악 스테이지에 도달했지만 아직 클리어 하지 못한 사람이 속한 스테이지를 notClear에 기록. 현재 속한 스테이지 전까지는 도달 후 클리어한 경우이므로 visited에 기록. 인원으로 튜플리스트 만들기. 튜플은 (실패율, 스테이지)로 이루어짐. 튜플리스트 sorting (실패율은 내림차순, 스테이지는 오름차순) sorting된 튜플리스트에서 스테이지만으로 리스트 구성 def solution(N, stages): answer = [] visited = [0 for _ in range(N)] notClear = [0 for _ in range(N)] for n..

2021.05.10 안테나 Solution 이 문제는 정답이 중간값이라는 것을 파악하는 게 핵심이다. 이외의 다른 곳에 설치하면 이동하는 쪽 반대에서 거리가 더 발생하게 된다. 정렬한 뒤 중간값을 출력해주면 된다. 홀수개일 경우 중간값(index : N//2)에 안테나를 설치하면 최소값이다. 짝수개일 경우 중간값이 두개이고 두개가 정확히 동일하다. 따라서 그 중 작은 값을 선택하면 된다. N = int(input()) homes = list(map(int, input().split())) homes.sort() if N % 2 == 0: print(homes[N//2 - 1]) else: print(homes[N//2])

2021.05.10 국영수 Solution 조건대로 lambda를 이용해 정렬 import sys sys.stdin = open('input.txt', 'r') N = int(input()) students = [] for n in range(N): tmp = list(map(str, input().split())) for i in range(3): tmp[i+1] = int(tmp[i+1]) students.append(tmp) students.sort(key=lambda x:(-x[1], x[2], -x[3], x[0])) for n in range(N): print(students[n][0])

가사검색 2021.04.20 Solution1 Hashing & Slicing & BruteForce query를 슬라이싱합니다. ? 가 접미사인 경우, ? 전까지 슬라이싱 합니다. ? 가 접두사인 경우, 뒤집어서 ? 전까지 슬라이싱 합니다. 전부 ? 인 경우, IsAll 변수에 표시합니다. words와 query를 비교합니다. 길이를 비교합니다. (다르면 더이상 확인할 필요 없습니다. => 거짓) query가 전부 ? 인 경우, 더이상 확인할 필요 없습니다. => 참 words의 접두사 / 접미사와 슬라이싱한 query를 query의 길이만큼 전부 비교합니다. 이미 확인된 녀석은 Dictionary로 값을 기억하고 있다가 해당 쿼리가 다시 나타나면 그 값을 그대로 사용합니다. 결과 : 효율성 테스트케이..