728x90 CS17 배열 vs ArrayList vs Set 무엇이 더 빠를까? https://www.acmicpc.net/problem/27622 27622번: Suspicious Event Input begins with a line containing an integer N (1 ≤ N ≤ 1000) representing the number of events in the given record. The next line contains N integers Ai (−1000 ≤ Ai ≤ 1000; Ai ≠ 0) each representing an event in chronological order. It is gua www.acmicpc.net 궁금증은 해당 문제로 해결하였습니다. 문제 지문을 번역해드리자면 0이상의 상수 = 로그인 0이하의 상수 = 로그아웃 로그인하지 않고 .. 2023. 3. 1. 강한 연결 요소 (Strongly Connected Component) 강한 연결 요소 (Strongly Connected Component)는 SCC라고 불리는 알고리즘 입니다. 유향 그래프에서 특정 노드에서 다른 노드들을 걸쳐 다시 특정노드로 돌아올 수 있으면, 노드들이 강하게 연결되어 있다 라고 합니다. DFS를 배우셨다면, 조금 쉽게 이해하실 수 있을거 같습니다. ex) https://www.acmicpc.net/problem/26146 26146번: 즉흥 여행 (Easy) 1번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지만, 2번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지 않으므로, 답은 No가 된다. www.acmicpc.net 1에서 2를 걸쳐 3으로 갔다가 다시 1로 돌아올 수 있음, 1에서 4로 갔다가 다시 돌아올 수 있.. 2023. 1. 26. 백트래킹(Backtracking) 백트래킹(Backtracking)은 답을 찾아가는 도중, 정답이 아닐거 같으면 뒤로 돌아가서 다시 답을 찾아가는 과정을 통해 해답을 구하는 방식의 알고리즘입니다. DFS을 알고 있다면, 이해하기 쉽습니다. DFS : 1번 방문한 곳은 다시 방문하지 못한다. 백트래킹 : 1군데를 여러번 방문할 수 있다. ex) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IO.. 2023. 1. 25. SPFA(Shortest Path First Algorithm) SPFA(Shortest Path First Algorithm) 알고리즘은 "음수 간선을 포함한 데이크스트라 알고리즘"으로 이해하면 편한 "벨만 포드 알고리즘"을 개선한 알고리즘 입니다. BFS - 데이크스트라 - 벨만포드(SPFA)로 학습을 진행하시면 편합니다. 벨만 포드는 "모든 간선에 대해 업데이트를 진행"하지만, SPFA는 "바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행"합니다. 벨만포드를 학습하지 않고, SPFA를 학습하셔도 태그로 벨만포드가 들어간 문제를 대부분 해결하실 수 있습니다. ex) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주.. 2023. 1. 24. 이전 1 2 3 4 5 다음 728x90
