본문 바로가기
반응형

전체 글1306

[SWEA] 4007 간담회 참석 출처: [SWEA] SW 문제해결 심화 - 그래프 Input 1 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 Output #1 10 임의의 정점 [x]과 나머지 정점들을 [i]라고 했을 때, [i] → [x] → [i]까지의 최단 거리 비용이 가장 큰 비용을 구하는 문제입니다. 구현 플로이드 와셜 알고리즘을 이용해서 모든 정점들의 최단 거리 비용을 구할 수 있지만, [1 ≤ N ≤ 50,000, 1 ≤ M ≤ 500,000]이기에 TLE 발생 그렇기에 다익스트라(Dijkstra) 이용 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로.. 2021. 2. 25.
[SWEA] 4066 All Pair Shortest Path 출처: [SWEA] SW 문제해결 심화 - 동적 계획법 Input 1 3 3 1 2 1 2 3 2 3 1 3 Output #1 0 1 3 5 0 2 3 4 0 모든 정점에 대해 최단 거리 비용을 구해야 하므로 플로이드 와샬 (Floyd Warshall)을 이용합니다. 플로이드 와샬 (Floyd Warshall) 개념 아래와 같은 가중 그래프에서 최단 경로를 찾는 알고리즘. ex) 정점 ③ → ⑤로 가는 최단 경로는 다음과 같습니다. 경로Path: ③ → ② → ④ → ① → ⑤ 비용Cost: +4 +1 +2 -4 = 3.. zoosso.tistory.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre.. 2021. 2. 25.
[BOJ] 백준 2610 회의준비 출처: https://www.acmicpc.net/problem/2610 Input 8 7 1 2 2 3 4 5 5 6 4 6 6 7 7 4 Output 3 2 4 8 첫째 줄에 구성되는 위원회의 수 K 그 다음 K줄에는 각 위원회의 대표 번호를 오름차순 출력 ※ 한 위원회의 대표가 될 수 있는 사람이 둘 이상일 경우, 그중 한 명만 출력 결과 설명 - 위원회는 총 3개로 구분. - 대표는 각 연결 그래프에서 거리비용이 제일 작은 정점이며, 정점 [4], [6]이 대표가 될 수 있지만, 그 중 한개 출력 - 정점 [8] 같이 단일 정점도 위원회 소속 및 대표 가능. ① 각 정점별로 최소비용을 모두 구해야하기에 플로이드 와샬 (Floyd Warshall)으로 구현 플로이드 와샬 (Floyd Warshall.. 2021. 2. 25.
[BOJ] 백준 16466 콘서트 출처: https://www.acmicpc.net/problem/16466 Approach 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com 1차 티켓팅에서 팔린 티켓 목록을 알고 있으므로 그 티켓들을 제외하고 가장 낮은 번호의 티켓을 구하면 됩니다. 1차에서 최대 구매한 개수는 1,000,000개 이지만 티켓들의 총 개수는 231- 1 입니다 (만약 1차에서 1~1,000,000 번호까지 구매했다면 .. 2021. 2. 25.
[BOJ] 백준 7567 그릇 출처: https://www.acmicpc.net/problem/7567 Input (((( Output 25 그룻의 개수는 최소 3개 이므로 첫번째 그릇을 기준으로 시작해서 괄호 모양이 같은지 비교합니다. - 같으면 + 5 - 다르면 + 10 * 탐색할 때마다 기준(pivot)을 바로 앞에 위치한 그릇 모양으로 갱신합니다. ※ 첫번째 그릇이 놓이는 높이 10cm를 초기값으로 둡니다. #include int strlen(const char* s, int len = 0) { while (s[len]) len++; return len; } char str[50 + 5]; int main() { // freopen("input.txt", "r", stdin); scanf("%s", str); char pivo.. 2021. 2. 25.
[BOJ] 백준 5926 Cow Lineup 출처: https://www.acmicpc.net/problem/5926 Input 6 25 7 26 1 15 1 22 3 20 1 30 1 Output 4 ① Hash를 통해 중복되지 않은 소(cow)들의 종류 수를 확인합니다. ex) 1 3 7 → 총 3마리 ② 소들에게 새로운 ID를 부여합니다. (발견된 종류 순서로 부여) 1 → 1 / 3 → 2 / 7 → 3 ③ (새로운 ID까지 부여된) 소들은 x 좌표 기준으로 오름차순 정렬합니다. (merge sort) ④ end 좌표를 확장해가며 소들의 종류가 빠짐없이 포함되는 지점을 찾습니다. ⑤ end 지점을 찾은 후 start 지점을 조정하여 최적(최소) 범위를 조정합니다. 첫번째 s = 1일 때, 모든 종류의 소를 포함하려면 e = 5 하지만 s =.. 2021. 2. 25.
[BOJ] 백준 7573 고기잡이 출처: https://www.acmicpc.net/problem/7573 Input 7 10 6 2 2 2 4 6 2 7 4 3 3 5 6 Output 3 [Jungol] 1437 같은 모양 찾기문제와 달리 그물의 크기가 변합니다. [Jungol] 정올 1437 같은 모양 찾기 출처: [Jungol] 정올 1437 같은 모양 찾기 Input 10 0000000001 1110011100 0100101000 0100101000 1111111111 0000101000 0000001000 0010010000 1111110000 0010010001 3 100 111 100 Output 2 ① 이중 fo.. zoosso.tistory.com ▶ 그물의 크기는 길이 L에서 만들 수 있는 사각형 입니다. ex) L =.. 2021. 2. 25.
[BOJ] 백준 14670 병약한 영정 출처: https://www.acmicpc.net/problem/14670 Input 3 1 3 4 2 99 1 4 1 1 2 4 99 3 4 1 99 1 5 Output 3 2 1 2 3 1 YOU DIED 어떤 약의 이름, 효능과 중복되지 않음을 보장되므로 Hash Table에 약의 효능 = key, 약의 이름 = value로 두어서 증상에 대해 해결 가능한지 빠르게 확인할 수 있습니다. ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com STL #include #in.. 2021. 2. 25.
[BOJ] 백준 7785 회사에 있는 사람 출처: https://www.acmicpc.net/problem/7785 Input 4 Baha enter Askar enter Baha leave Artem enter Output Askar Artem ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com STL #include #include #include #include #include #include using namespace std; map member; int main(){ // freopen("input.tx.. 2021. 2. 25.
플로이드 와샬 (Floyd Warshall) 개념 아래와 같은 가중 그래프에서 최단 경로를 찾는 알고리즘. ex) 정점 ③ → ⑤로 가는 최단 경로는 다음과 같습니다. 경로Path: ③ → ② → ④ → ① → ⑤ 비용Cost: +4 +1 +2 -4 = 3 플로이드 와샬을 이용해서 정점 [u] → 정점 [v]로 가는 최단 거리를 구할 때, 아래의 두 개의 테이블을 이용합니다. - 최단 거리 비용을 나타내는 테이블 D - 최단 거리 경로를 구할 수 있는 테이블 P 시뮬레이션 ▶ 초기 테이블 상태 - (테이블 D) 『INF』: 현재 시점에서 바로 연결되어 있지 않기에 무한대. - (테이블 P) 『NIL』: 경로가 없다. ▶ 중간 경로로 정점 [1] 추가 정점 [1]을 중간 경유하여 최단 거리 비용 테이블 D가 갱신됩니다. · [4] → [1] → [2.. 2021. 2. 25.
반응형

티스토리툴바