반응형 PS 문제 풀이/Algospot16 [Algospot] 알고스팟 JOSEPHUS 조세푸스 문제 출처: https://www.algospot.com/judge/problem/read/JOSEPHUS# Input 2 6 3 40 3 Output 3 5 11 26 N = 6, K = 3 ▷ 숫자 = 1 2 3 4 5 6 ① 1 제외: [2 3 4 5 6] ② 4 제외: [2 3 5 6] ③ 2 제외: [3 5 6] ④ 6 제외: [3 5] [구현] -연결 리스트 이용. 리스트 크기가 넘을 때 처음부터 다시 count 하는 것만 주의하면 K 번째를 쉽게 count #include #include using namespace std; int C, N, K; void josephus(){ list survivor; // 1 ~ N 숫자 push for (int i = 1; i 2) { kill = survi.. 2021. 3. 1. [Algospot] 알고스팟 LAN 근거리 네트워크 출처: https://algospot.com/judge/problem/read/LAN Input 2 3 1 0 0 1 0 1 2 0 1 10 5 -7 -7 10 -4 10 -4 -5 0 -10 -6 6 8 -5 3 -4 6 -10 4 -7 10 9 7 7 3 9 7 5 0 8 6 Output 1.4142135624 29.7042202421 크루스칼 알고리즘 이용. ▷ (1, 2)와 연결되어 있지 않았으므로 다른 정점에서 연결해야 합니다. ▷ (0, 1)과 (1, 2)가 최소거리 이므로 연결해줍니다. ▷ Math.sqrt((1-0)2 + (2-1)2) = 1.4142135624 모든 간선이 최소 비용으로 연결해야 하는 [BOJ] 1197 최소 스패닝 트리 문제입니다. [BOJ] 백준 1197 최소 스패닝 .. 2021. 3. 1. [Algospot] 알고스팟 BOGGLE 보글 게임 출처: https://algospot.com/judge/problem/read/BOGGLE Input 1 URLPM XPRET GIAET XTNZY XOQRS 6 PRETTY GIRL REPEAT KARA PANDORA GIAZAPX Output PRETTY YES GIRL YES REPEAT YES KARA NO PANDORA NO GIAZAPX YES ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.c.. 2021. 3. 1. [Algospot] 알고스팟 FESTIVAL 록 페스티벌 출처: https://algospot.com/judge/problem/read/FESTIVAL Input 2 6 3 1 2 3 1 2 3 6 2 1 2 3 1 2 3 Output 1.75000000000 1.50000000000 for문을 이용한 완전 탐색 L개의 팀이 확보된 상태이고 하루에 한 팀만이 공연할 수 있기에 L ~ N개만큼 공연장을 대여해야 합니다. 연속된 일자라는 조건이 있기 때문에 for문을 통해서 시작일과 총 예약일수를 변화해가면 평균 대여 비용을 구합니다. ※ 출력 형식을 맞추기 위해 아래와 같이 출력(double형) System.out.println(String.format("%.12f",result)); import java.util.Scanner; public class Main.. 2021. 3. 1. [Algospot] 알고스팟 RUNNINGMEDIAN 변화하는 중간값 출처: https://algospot.com/judge/problem/read/RUNNINGMEDIAN Approach [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 높은 수를 우선순위로 하는 것과 낮은 수를 우선순위로 하는 것, 총 2개의 우선순위 큐 이용 ※우선순위 큐는 Heap 구조로 이루어져 있으므로 maxHeap, minHeap으로 변수명 설정 새로운 데이터를 입력 받을 때, 조건 [1]. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.. 2021. 2. 27. [Algospot] 알고스팟 DICTIONARY 고대어 사전 출처: https://algospot.com/judge/problem/read/DICTIONARY Input 3 3 ba aa ab 5 gg kia lotte lg hanhwa 6 dictionary english is ordered ordinary this Output INVALID HYPOTHESIS ogklhabcdefijmnpqrstuvwxyz abcdefghijklmnopqrstuvwxyz 각 단어들의 알파벳의 선후관계를 통해 위상정렬 (Topological sort) 하는 문제입니다. 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DA.. 2021. 2. 22. 이전 1 2 다음 반응형
