Algorithm76 [알고리즘] 최소비용 구하기 (백준 1916번) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 한 시작점에서 나머지 노드까지의 최소 거리를 구하는, 전형적인 다익스트라 문제다. 사실 다익스트라 문제는 이번이 처음 풀어보는데 생각보다 시간이 오래걸렸다. 계속 8%에서 넘어가질 않아서 한참 고민하고 있었는데 알고 보니 버스는 단방향인데 나는 양방향으로 생각하고 문제를 풀었다.... Solution dist 배열에서 시작점 dist[start] = 0이고 나머지는 무한대로 초기화한다. 각 노드의 edge 정보들을 저장해놓는다... 2020. 10. 2. [알고리즘] 구슬 탈출 2 (백준 13460번) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성 기출 문제이다. 삼성 기출에서 자주 나오는 맵에서 물체들을 동시에 움직이는 시뮬레이션 유형이다. BFS를 활용하여서 빨간 공이 구멍에 빠지는 최단 시간을 알아내야한다. Solution 시뮬레이션 문제 중 물체를 동시에 움직이는 문제는 항상 까다롭다. 이 경우는 보드를 기울일 때 고려해야할 상황이 많다. 상하좌우로 기울일 때, 어떤 공을 먼저 움직여야 동기화가 될 지 움직이다 다른 공을 만나면 멈춰야 됨 움직이.. 2020. 10. 2. [알고리즘] 줄 세우기 (백준 2252번) 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net N, M의 크기만 봐도 알 수 있지만 그래프 완전탐색 문제이며 N은 정점, M은 간선의 수를 나타낸다. 정확히는 위상 정렬 문제다. 각 노드보다 앞서 있는 노드들이 먼저 출력되어야 하는 형태를 가진다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStre.. 2020. 9. 28. [알고리즘] 집합 (백준 11723번) 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 가장 기본적인 비트마스크 문제다. 총 M의 크기가 최대 3백만이고 메모리 허용량이 4MB 밖에 되지 않기에 비트마스크를 필히 활용해야 한다. Solution 비트마스크 연산 방법대로 분기해서 처리했는데도 시간초과가 나서 당황했는데 자바의 bufferedReader와 bufferedWriter를 써주지 않아서 그랬다. 참고로 all 연산은 1~20까지의 수를 추가하는 것인데 이는 (0~20) = SET의 21 추가후 - 1 (1~20) = SET에서 - 1 이기에 최종적으로는 SET에 21을 추가후 .. 2020. 9. 28. 이전 1 ··· 5 6 7 8 9 10 11 ··· 19 다음
