백준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 : 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])

인구이동 Solution BFS 모든 나라를 돌면서 국경선을 공유할 나라를 묶는다. 국경선을 공유한 나라의 인구수를 업데이트한다. 인구이동이 없을 때까지 반복한다. 2019.10.19 C++ 풀이 #include #include #include using namespace std; const int MAX = 55; int map[MAX][MAX][2]; bool check[MAX][MAX]; pair rememMap[MAX*MAX]; int N,L,R; queue myQ; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int BFS(int y,int x,int nowIdx,int nextIdx){ int count = 0; int sumMap = map[y][x]..

2021.03.28 문제 링크 문제설명 NXN 크기의 시험관 바이러스는 1번부터 K번 중 하나 1초마다 상하좌우 방향으로 증식하며, 번호가 낮은 바이러스 먼저 증식. 증식하려는 곳에 이미 바이러스가 있으면 증식 안함. S초 뒤에 주어진 좌표에 바이러스 종류를 찾는 문제 solution 바이러스 목록을 만듭니다. (맵을 돌며 바이러스가 있다면 해당 번호 목록에 넣음) S초 동안 바이러스가 퍼집니다. 네 방향을 돌며 바이러스가 퍼집니다. 이미 바이러스가 있다면 퍼지지 않습니다. 퍼진 바이러스는 기존 바이러스 목록에 포함시킵니다. (for loop에 영향받지 않도록 새로운 목록에 담아서 나중에 추가하는 방식으로 구현) 주어진 좌표에 있는 바이러스 종류를 리턴합니다. 구현1. 30564KB, 1004ms 한번 ..

2020.02.18 백준17135 캐슬디펜스 풀이 궁수 위치 3개를 뽑는 경우의 수를 조합으로 찾는다. simulation을 이용해 그 때 제거한 적의 수를 구하고 경우의 수 중 최댓값을 찾는다. 변수 inMap : 초기 map 상태 nextMap : 게임을 진행하면서 변화하는 map length : 각 열에서 가장 위에있는 적부터 옮길 수 있도록 하기 위해서 맨 위 행 번호를 기록한 변수 nextLen : 초기 길이 변수 만큼만 적을 옮기도록 최적화하기 위해 변화하며 사용할 length 변수 check : 처음 input에서 이미 담은걸 안담도록 만들기 위해 사용한 변수 함수 search : 궁수의 위치를 받아서 제거할 수 있는 적의 위치를 반환하는 함수 kill : 궁수가 적을 제거하는 함수 move..