1. 구분: 다이나믹 프로그래밍, 배낭 문제 언어: Java 전략 0-1 knapsack문제를 이용하여 문제를 해결한다. 물건을 차례대로 고려한다(포함하거나 포함하지 않거나) - 배낭 무게 내에서 물건을 포함할지 말지 고르고, 또한 그 가치를 포함/비포함 중 더 큰 것을 선택한다. 방법이 2가지가 있다 1, 2차원 배열을 활용하여 문제를 해결 - d[i][j]: i번째 물건을 고려할 때, 가방의 무게가 j일때 최대 가치 - i 번 물건을 고려(꼭 포함해야 하는게 아니다) - i-1번에서 현재 물건 포함한 상황과, i-1번째에서 포함하지 않은 상황 중 더 큰 것을 선택한다. 2. 1차원 배열을 활용하여 문제를 해결 - d[j]: 가방 무게가 j일때 최대 가치 - 가방의 무게가 가장 최대일 때 부터 현재 가..

1 구분: 구현, 그래프 이론, 그래프 탐색, 브루트포스 알고리즘, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패님 트리 언어: Java 전략 1. 각각 섬들을 구분하기 BFS를 통해 각 섬들을 구분한다. 섬들에 숫자를 부여한다. 2. 각 섬들 간의 최소 거리 구하기 각 섬들을 하나의 정점으로 여기기 위해 각 섬들의 최소 거리를 구한다. 각 섬들에 대해 거리를 구하는데, 한 섬에 해당하는 모든 좌표를 모두 확인한다. 그래서 최소 거리를 구한다 구한 거리는 인접 행렬에 넣어 그래프 처럼 만든다. 3. MST - 최소 스패닝 트리 구하기 prim 알고리즘과 kruskal 알고리즘이 있는데 나는 prim 알고리즘을 사용했다. 2. 코드 package com.ssafy.webex; import java.util..

1 구분: BFS, DFS, 그래프 이론, 그래프 탐색, 부트포스 알고리즘 언어: Java 전략 1. 지역구 입력 받기 연결 리스트의 형태로 지역구를 받는다. - 노드와 링크를 받을 클래스를 생성하였다. 2. 지역구로 나누기 부분 집합을 구하는 방법으로 지역구 2개로 나눈다 - 부분 집합 하나만 선택하면, 포함되지 않는 것들끼리 또 하나의 부분 집합이 완성 부분 집합의 개수가 0이거나 n개일 경우는 제외한다. 3. 각 부분 집합이 연결되었는지 확인 BFS를 이용하여 각 지역구가 연결 되었는지 확인한다 - 한 점에서 다른 점까지 도달 가능하면 지역구들은 연결되어 있는 것이다. 두 지역구 각각 연결 여부를 확인해야 한다. 4. 차이 구하기 각각의 구역의 인구 수들을 구해서 차이의 최소를 찾는다. 2. 코드 ..

1. 구분: DFS, BFS 언어: Python 전략: BFS를 통해 전체 그래프를 모두 탐색 큐에 토마토의 좌표와 며칠인지를 append한다. -> (x,y,day) 큐에서 popleft()하여 나온 칸과 인접한(상, 하, 좌, 우) 칸이 안익은 토마토이고, 칸의 범위를 벗어나지 않았다면, 날짜를 +1하여 큐에 넣는다 -> (x,y,day++) ** 단! 동시 다발적으로 토마토가 익기 때문에 day의 초기화가 필요하다 큐가 빌때까지 위의 과정을 반복한다. 전체를 돌면서 만약 안 익은 토마토가 존재하는지 확인한다. 복잡도: 시간- 1000*1000 = 10^6 -N과 M이 최대 1000이기 때문에 공간 - 최대 10^6 만큼 입력을 받으니 그것을 받을 크기의 큐 2.코드 3. 2차원 배열의 x, y가 너..

1, 분류: 그리디 알고리즘 언어: 파이썬 2, 코드 3. 실패의 원인 indentation: 파이썬 같이 indentation이 중요한 언어는 더더욱 신경을 써야 한다. 시간 초과 : while문을 이용해 k 가 0이 아닌 경우에만 계산을 하는 조건을 걸었다. i =1인 경우 : 단위가 1인 동전의 경우를 배제했다. 이 경우는 특수한 경우로 꼭 신경을 써줘야 한다.