알고리즘 문제/SW Expert Academy5 [SW Expert Academy] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE "이 문제는 가장 짧은 경로를 '효율적으로' 찾는 것이 목적이 아니다." 라는 것을 보아하니 모든 경로를 방문하는 dfs를 구현해서 풀어보라는 문제같다.나는 외판원순회(TSP)로 풀었다. N+2개의 좌표간 최단 거리를 구해서 배열에 저장해둔다.메모이제이션을 위해 (방문한 고객 인덱스들, 현재 좌표 인덱스) 를 인덱스로 하는 배열을 하나 만든다.이 배열에는 현재 좌표 인덱스부터 아직 방문하지 않은 고객들을 모두 방문한 후 집으로 돌아가는 경로 거리 중.. 2019. 1. 8. [SW Expert Academy][2819] 격자판의 숫자 이어 붙이기 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE 만들 수 있는 서로 다른 일곱 자리 수를 구하는 문제이므로 set을 이용했다.수를 이어 붙여서 7자리 수를 만들어야 하므로 DFS를 이용했다.(0, 0) ~ (4, 4)를 시작 지점으로 상하좌우 dfs를 돌리면서 수를 이어붙인다.이어붙인 수가 7개가 되면 set에 만든 문자열을 넣는다.탐색을 모두 마친 후 set의 size가 정답이 된다. 소스코드 : https://gist.github.com/fpdjsns/92ce5fc97f0fb363b588979.. 2019. 1. 5. [SW Expert Academy][1206] View 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE 하나의 빌딩에서 조망권에 드는 세대 수를 찾으려면 왼쪽 2채, 오른쪽 2채의 높이만 비교하면 된다.따라서 i 번째 빌딩에서 조망권에 드는 세대 수를 구하려면, i-2, i-1, i+1, i+2 번째 빌딩 높이 중 최대를 구한다.그리고 i번째 빌딩과 구한 최대 높이의 차이를 구한다. 구한 차이가 정답이 될 수 있는 세대 수이다.만약 높이의 최대 값보다 i번째 빌딩 높이가 작다면 정답이 될 수 있는 집은 없다. 하나의 TC의 시간복잡도는 O(빌딩 수 *.. 2019. 1. 5. [SW Expert Academy][1984] 중간 평균값 구하기 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Pw_-KAdcDFAUq&categoryId=AV5Pw_-KAdcDFAUq&categoryType=CODE 10개의 수를 입력받으면서 모든 수를 더한다.입력 받은 값들 중 최소 값, 최대 값을 구한다.10개 수를 모두 더했으면 더한 값에서 최소 값, 최대 값을 빼준다. 그리고 8을 나눈다. (최소, 최대 값 빠졌으므로 8개임)이 때 실수값으로 계산을해야 소수점 첫째 자리를 구할 수 있다.구한 값에 + 0.5를 한다. (반올림)그리고 정수화 해주면 정답이 된다. (정수화하면 소수점들은 모두 없어지므로) 시간복잡도는 O(T). 처음에는 최소와 최대가 같은 경.. 2019. 1. 3. [SW Expert Academy][2047] 신문 헤드라인 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5QKsLaAy0DFAUq 입력받은 문자열 s를 앞에서부터 탐색하면서 소문자인 경우('a' 이상 'z' 이하인 문자) 대문자로 만들어준다. 문자 = 문자 - 'a' + 'A'cs 소문자를 대문자로 만드는 방법은 소문자 'a'를 뺀 후 대문자 'A'를 더해주면 된다.시간복잡도는 O(|s|). 소스코드 : https://gist.github.com/fpdjsns/53707ccb4e14ef90887175aeae2af24c 2019. 1. 3. 이전 1 다음