본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[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.
[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.
[BOJ] 백준 2056 작업 출처: www.acmicpc.net/problem/2056 Input 7 5 0 1 1 1 3 1 2 6 1 1 1 2 2 4 8 2 2 4 4 3 3 5 6 Output 23 위상정렬 (Topological sort 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 작업(정점)의 개수 N과 각 작업별 선행관계가 주어질 때, 모든 작업이 완료하기 까지 필요한 최소 시간 출력. 1번의 경우에는 항상 선행 작업이 존재하지 않습니다. ※ 해당 문제는 사이클.. 2021. 2. 24.
[BOJ] 백준 2252 줄 세우기 출처: https://www.acmicpc.net/problem/2252 Input 3 2 1 3 2 3 Output 1 2 3 N명(정점)의 학생들의 비교한 키가 일부 제공되었습니다. (방식: 두 학생의 키를 비교 ← 방향성 그래프) 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 구현 위상 정렬을 활용했으면 그 중 인접리스트 이용. ※ 해당 문제는 사이클을 형성하지 않는 Input Data이기에 코드에 .. 2021. 2. 24.
[BOJ] 백준 16637 괄호 추가하기 출처: https://www.acmicpc.net/problem/16637 Input 9 3+8*7-9*2 Output 136 길이가 N인 수식은 {+, -, x }로 이루어져 있습니다. 연산자 우선수위 동일하며, 수식을 왼쪽에서부터 순서대로 계산. ex) 3+8*7-9*2 = 136 수식에 소괄호를 추가하여 식의 순서를 바꿀 수 있습니다. ex) 3+(8×7)-(9×2) = 41 하지만, 괄호 안에는 연산자가 하나만 있어야 하며 괄호 안에 괄호가 있는 중첩된 형태는 허용하지 않습니다. ex) 3+((8×7)-9)×2, 3+((8×7)-(9×2)) ▶ 수식이 주어졌을 때, 괄호를 적절히 추가해서 최댓값 구하기. 단계별 구현 ① 완전탐색으로 괄호가 놓일 수 곳에 배치하여 수식 완성 ex) 3+(8×7)-9.. 2021. 2. 24.
[BOJ] 백준 2661 좋은수열 출처: https://www.acmicpc.net/problem/2661 Input 7 Output 1213121 "나쁜 수열": 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있는 수열. 그렇지 않은 수열을 『좋은 수열』 이라고 함. 구현 N 길이의 모든 수열 중 주먹구구 방식으로 구한 후, ex) N=4 일때, 1111 → 1112 → 1113 → 1121 → ... → 3333 좋은 수열 여부를 파악하기에는 시간제한. 길이 1→N 까지 좋은 수열인지 확인하며 길이 N인 수열을 만들어 갑니다. ← DFS ※ 코드에서 『좋은 수열』인지 판단할 때, 부분문자열의 길이를 {문자열 길이}/2 까지만 계산 while(size str.length()) { break; } // 나쁜 수열에 해당된다면 i.. 2021. 2. 24.
반응형

티스토리툴바