알고리즘 - SWEA/D5

[SW expert Academy] SWEA 1248번 공통조상 자바(Java)

[D5] [S/W 문제해결 응용] 3일차 - 공통조상 - 1248 문제 링크 성능 요약 메모리: 26,212 KB, 시간: 141 ms, 코드길이: 2,271 Bytes 제출 일자 2023-12-31 19:06 해결 방법 1. 공통 조상을 찾는 두개의 정점 번호를 구한다. 2. 첫번째 정점을 먼저 호출해서 HashSet에 전부 넣어줌 3. 두번째 정점을 호출하면서 HashSet에 있다면 공통 조상으로 간주하고 commonAncestor에 저장 후 return 4. 그 후 서브 트리를 구해준다. 5. 서브 트리는 divide and conquer을 통해서 자식 노드가 0이라면 0을 더하고 0이 아니라면 재귀호출을 통해서 현재 노드의 개수와 더해서 리턴해준다. 풀이 코드 import java.io.Buffe..

[SW expert Academy] SWEA 1247번 최적 경로 자바(Java)

[D5] [S/W 문제해결 응용] 3일차 - 최적 경로 - 1247 문제 링크 성능 요약 메모리: 103,844 KB, 시간: 1,449 ms, 코드길이: 2,215 Bytes 제출 일자 2023-12-31 18:34 풀이 방법 1. N명의 고객을 방문하고 집으로 간다. 2. 회사, 집 위치, 각 고객의 위치는 이차원 정수 좌표(x,y)로 줌 3. 두 위치 사이는 |x1-x2| + |y1-y2| 로 계산 4. 회사에서 출발하여 모든 고객을 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 함 5. 회사와 집의 좌표, 2~10명 사이 고객 좌표가 주어짐 6. 모두 방문하고 집으로 가는 경로 중 총 이동거리가 가장 짧은 경로의 이동거리 출력 a. 브루트 포스로 모든 경우의 수를 출력한다. b. 클래스..