알고리즘 문제408 [BOJ][3665] 최종 순위 문제 : https://www.acmicpc.net/problem/3665 위상정렬 문제다.등수가 3등인 사람은 1, 2등이 정해지는 경우 3등이 정해진다.이를 그래프로 나타내면 위와 같다. 1등은 앞에 아무도 없는 경우 1등이다.2등은 1등이 정해져서 화살표가 없어지면 2등 앞의 등수가 아무도 없게되고 2등이 정해진다.3등도 마찬가지로 1, 2등이 정해지면 3등이 정해진다. m개 등수가 바뀌는 쌍이 주어지면 2개 화살표를 반대로 바꾼다.만약 m이 2이고 (1,2), (2,3)이 입력값으로 주어지면 위 그림과 같이 화살표가 바뀐다.이때, 1, 2, 3 사이에는 싸이클이 생겨서 1등을 정할 수 없게 되서 IMPOSSIBLE을 출력한다.모든 등수 뿐만 아니라 2개 이상의 등수 사이에 위와 같이 싸이클이 발생.. 2019. 1. 19. [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. [BOJ][1181] 단어 정렬 문제 : https://www.acmicpc.net/problem/1181 문제 조건 중 단어가 여러 번 입력된 경우 한 번씩만 출력을 하라는 항목이 있다.그래서 중복을 제거하기 위해 set을 이용해서 풀었다.그리고 set의 정렬 조건을 수정하였다. 정렬 조건은만약 비교하는 문자열 2개의 길이가 다르다면 앞에 있는 문자열이 길이가 더 짧은 경우 true, 앞에 있는 문자열이 길이가 더 긴 경우 false를 반환.문자열 2개의 길이가 같다면 사전순 정렬로 되어있으면(앞에 있는 문자열 < 뒤에 있는 문자열) true, 아닌 경우 false를 반환한다. C++ set.insert 의 시간복잡도는 O(log(set.size()) 이므로, 총 시간복잡도는 대략 O(NlogN) 소스코드 : https://gist... 2019. 1. 6. [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. 이전 1 ··· 60 61 62 63 64 65 66 ··· 68 다음
