본문 바로가기
반응형

전체 글1306

[BOJ] 백준 11780 플로이드 2 출처: https://www.acmicpc.net/problem/11780 Input 5 14 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 3 5 10 3 1 8 1 4 2 5 1 7 3 4 2 5 2 4 Output 0 2 3 1 4 12 0 15 2 5 8 5 0 1 1 10 7 13 0 3 7 4 10 6 0 0 2 1 2 2 1 3 2 1 4 3 1 3 5 4 2 4 5 1 0 5 2 4 5 1 3 2 2 4 3 2 4 5 2 3 1 3 3 5 2 0 2 3 4 2 3 5 3 4 5 1 3 4 5 2 4 4 5 1 3 0 2 4 5 2 5 1 2 5 2 3 5 1 3 3 5 2 4 0 * 플로이드 와샬 (Floyd Warshall) 참고 플로이드 와샬 (.. 2021. 2. 25.
[BOJ] 백준 11404 플로이드 출처: https://www.acmicpc.net/problem/11404 Input 5 14 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 3 5 10 3 1 8 1 4 2 5 1 7 3 4 2 5 2 4 Output 0 2 3 1 4 12 0 15 2 5 8 5 0 1 1 10 7 13 0 3 7 4 10 6 0 플로이드 와샬 (Floyd Warshall)을 통해 구현할 수 있습니다. 플로이드 와샬 (Floyd Warshall) 개념 아래와 같은 가중 그래프에서 최단 경로를 찾는 알고리즘. ex) 정점 ③ → ⑤로 가는 최단 경로는 다음과 같습니다. 경로Path: ③ → ② → ④ → ① → ⑤ 비용Cost: +4 +1 +2 -4 = 3.. zoosso.tis.. 2021. 2. 25.
[BOJ] 백준 12791 Starman 출처: https://www.acmicpc.net/problem/12791 Input 1 1 2016 Output 25 1967 DavidBowie 1969 SpaceOddity 1970 TheManWhoSoldTheWorld 1971 HunkyDory 1972 TheRiseAndFallOfZiggyStardustAndTheSpidersFromMars 1973 AladdinSane 1973 PinUps 1974 DiamondDogs 1975 YoungAmericans 1976 StationToStation 1977 Low 1977 Heroes 1979 Lodger 1980 ScaryMonstersAndSuperCreeps 1983 LetsDance 1984 Tonight 1987 NeverLetMeDow.. 2021. 2. 25.
[BOJ] 백준 11652 카드 출처: https://www.acmicpc.net/problem/11652 Input 5 1 2 1 2 1 Output 1 두 가지 방법으로 문제를 해결할 수 있습니다. (정렬, Hash) 정렬 {숫자, 나타난 횟수}를 한 쌍으로 데이터를 저장한 후 아래 두 기준으로 정렬합니다. ① 나타난 횟수가 많은 순 ② 숫자가 작은 순 Hash 숫자(long long)를 key값으로 해서 나타난 횟수를 Value 값으로 저장합니다. Hash를 순회하면서 가장 많이 나타난 횟수 중 가장 작은 수를 탐색합니다. ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유.. 2021. 2. 25.
[SWEA] 3260 두 수의 덧셈 출처: SWEA Input 2 1 2 100000000000000000000000001 9 Output #1 3 #2 100000000000000000000000010 자릿수가 작지 않기 때문에 문자열 배열을 이용해서 처리 #include #include #include using namespace std; int main(){ int testCase; cin >> testCase; for (int tc = 1; tc > A >> B; // 더 작은 숫자 자릿수 채워주기 int n = A.size(), m = B.size(), len = max(n, m); if (n > m) for (int i = 0; i < n - m; i++) B = "0" + B; else for (int i = 0; i < m .. 2021. 2. 24.
[SWEA] 9780 외계인 침공 출처: SWEA Input 2 2 10 20 6 5 9 1 3 7 2 Output #1 20 #2 16 DP 관점에서 문제를 해결할 수 있습니다. (부분문제 해결) ex) 도시 = [1 2 3 4 5]가 있을 때, (도시에 사는 개구리 수와 상관없이) 많은 도시를 침공할 수 있는 경우? 1 → 3 → 5를 차례로 공격하는 경우입니다. 문제 규칙에 따르면 침공한 도시의 양옆은 납치할 수 있는 개구리가 없습니다. 결국, 도시에 사는 개구리 수에 따라 도시를 공격할 지, 아니면 다른 도시를 공격할 지 결정해야 합니다. ▶ DP[i] = max(DP[i - 2] + A[i], DP[i - 1]) : i번째 도시까지 침공했을 때 납치할 수 있는 개구리의 최대값 도시가 1개인 경우, 개구리 수와 상관없이 침공. →.. 2021. 2. 24.
[SWEA] 3408 세가지 합 구하기 출처: SWEA Input 3 1 10 1001 Output #1 1 1 2 #2 55 100 110 #3 501501 1002001 1003002 #include using namespace std; long int N, S[3]; int main() { int testCase; cin >> testCase; for (int tc = 1; tc 2021. 2. 24.
[BOJ] 백준 2884 알람 시계 출처: https://www.acmicpc.net/problem/2884 Input 10 10 Output 9 25 24시간 형식으로 표현합니다. 시간을 나타낼 때, 불필요한 0은 사용 X ex) 0:0은 자정 / 끝은 23:59 다음날 자정 1분 전 입니다. import java.util.*; public class Main{ public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int H = Integer.parseInt(sc.next()); int M = Integer.parseInt(sc.next()); // 45분 빠르게 설정 M = M - 45; // 기존 시간이 45분 미만이라.. 2021. 2. 24.
[BOJ] 백준 3665 최종 순위 출처: https://www.acmicpc.net/problem/3665 Input 3 5 5 4 3 2 1 2 2 4 3 4 3 2 3 1 0 4 1 2 3 4 3 1 2 3 4 2 3 Output 5 3 2 4 1 2 3 1 IMPOSSIBLE 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 변동된 정보를 이용하여 새로운 순위를 출력하는 문제입니다. ※ 작년 순위가 오류없이 명확하게 주어지기 때문에 (기.. 2021. 2. 24.
[SWEA] 3456 직사각형 길이 찾기 출처: SWEA Input 3 1 1 2 4 3 4 5 5 5 Output #1 2 #2 3 #3 5 직사각형 한 변을 기준으로 자기자신을 제외하고 동일한 값이 있는지 확인 모든 변이 일치하는 경우가 있으므로 answer 초기값을 임의의 한 변과 동일하게 처리 #include using namespace std; int side[3], answer; int main() { int testCase; cin >> testCase; for (int tc = 1; tc > side[i]; } bool isUnique; answer = side[0]; for (int pivot = 0; pivot < 3; pivot++) { isUnique = true; for (int target = 0; target < 3;.. 2021. 2. 24.
반응형

티스토리툴바