RUBY

출처:: www.acmicpc.net/problem/6118 분류:: 다익스트라 , bfs 1. 문제 이해 및 해결과정 - 간선의 비용이 모두 0이기 때문에 BFS로도 풀 수 있다 2. 풀이방법 1. 다익스트라 #숨박꼭질 #https://www.acmicpc.net/problem/6118 import sys import heapq sys.stdin = open("input.txt","r") n,m=map(int,input().split()) graph = [[] for _ in range(n+1)] visited=[False]*(n+1) INF=1e9 dist=[INF]*(n+1) for i in range(m): a,b=map(int,input().split()) graph[a].append((b,1)..

출처:: 유명알고리즘 대회 분류:: 1. 문제 이해 및 해결과정 - 메세지를 보내고자 하는 도시 C가 출발점이 된다. #input 3 2 1 1 2 4 1 3 2 #output 2 4 2. 풀이방법 1.다익스트라 #전보 # import sys import heapq sys.stdin = open("input.txt","r") input=sys.stdin.readline n,m,start=map(int,input().split()) graph=[[] for _ in range(n+1)] INF=1e9 dist=[INF]*(n+1) visited=[False]*(n+1) for _ in range(m): x,y,z=map(int,input().split()) #x에서 y로 이어지는 통로에서 메세지 전달시간이..

구간 합 문제 : 연속적으로 나열된 n개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제 - m개의 쿼리, 매번 구간 합을 계산하면 => O(NM) 구간 합 빠르게 계산하기 알고리즘 - N개의 수에 대해서 어떠한 처리를 수행한 뒤에 나중에 M개의 쿼리가 각각 주어질 때마다 빠르게 구한 합을 도출할 수 있도록 하면 어떨까? => 접두사 합 이용(Prefix sum) =>O(N+M) - 각 쿼리에 대해 구간합을 빠르게 개선하기 위해서는 n개의 수의 위치 각각에 대하여 접두사 합을 미리 구해 놓으면 된다 = EX) [10,20,30,40,50] => [0,10,30,60,100,150] 3~4 100-30=70 1. N개의 수에 대하여 접두사 합 (Prefix Sum)을 계산하여 배열 P에 저..

이진탐색 - 반으로 쪼개면서 탐색하기 : 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정 - 시간복잡도 O(logn) - 처리해야할 데이터의 개수나 값이 1000만 이상이면 이진탐색 떠올리자 - 구현 #10개의 수입력했을 때, 7이 몇번째 있는지 찾기 10 7 1 3 5 7 9 11 13 15 17 19 1) 재귀함수 #재귀함수로 구현한 이진 탐색 소스코드 # import sys sys.stdin = open("input.txt","r") def binary_search(arr,target,start,end): if start>end: return None mid=(start+end)//2 #목표값을 찾은 경우 if arr[mid] == target: retu..

출처:: www.acmicpc.net/problem/3665 분류:: 위상정렬 1. 문제 이해 및 해결과정 - 정해진 순위에 맞게 팀들의 순서를 나열해야한다 -> 위상정렬 - 순위정보가 주어지면, 자기보다 낮은 등수를 가진 팀을 가리키도록 방향그래프를 만든다 - 상대적 순위가 바뀌면 간선의 방향을 반대로 바꾼다 - 위상정렬을 다시 수행하면 특이 케이스가 발생할 수 있다 - 1) 사이클이 발생하는 경우(IMPOSSIBLE) 2) 위상정렬의 결과가 1개가 아니라 여러가지인 경우(?) - 일반적인 위상정렬은 N개의 노드가 출력 노드가 N번 나오기 전에 큐가 비게 되면 ? 1번의 경우이다 => 큐의 원소가 0개 특정시점에 2개 이상의 노드가 큐에 한꺼번에 들어가면? => 정렬결과가 여러가지 => 큐의 원소가 2..

출처:: k 대회 기출 분류:: 그리디 1. 문제 이해 및 해결과정 1. 첫번째 풀이 1) 동전 오름차순 정렬 후 2) 모든 경우 다해보고 나온 sum을 set에 넣음 3) 1부터 차례대로 인덱스와 값이 다른 지점의 인덱스가 만들 수 없는 최소값이다 => n이 1000이므로 2^1000 이되어 시간초과가 날 수 밖에 없다. 2. 그리디 - 거스름돈 문제는 각 화폐 단위마다 무한 개의 동전이 존재한다고 가정했는데, 이 문제에서는 동전의 수가 한정적이라는 점이 다르다 - 동전을 화폐 단위 기준으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target변수를 업데이트 하는 방법으로 최적의 해를 계산할 수 있다. ex) 1 2 3 8 네 개의 동전이 있다고 가정 1) 처음에는 금액 1을 만들 수..

출처:: 2019 카카오 신입 공채 https://programmers.co.kr/learn/courses/30/lessons/42891 분류:: 그리디 1. 문제 이해 및 해결과정 - 모든 음식을 시간을 기준으로 정렬한 뒤에, 시간이 적게 걸리는 음식부터 제거해 나가는 방식을 이용한다는 아이디어까지는 생각하였다. 2. 풀이방법 1. 그리디(최소힙) import heapq def solution(food_times, k): #전체 음식을 먹는 시간보다 k가 크거나 같다면 -1 if sum(food_times)

출처:: 2019 sw마에스트로 입학 테스트 분류:: 그리디 1. 문제 이해 및 해결과정 1번 풀이 1) n개 중에 2명이 뽑는 경우의 수 2) 같은 무게를 뽑는 경우 => 1번 - 2번 2번 풀이 1) 각 무게 마다 볼링공 몇 개 있는지 2) 경우의 수 더하기 ex) 1 2 2 3 3 이라면 [1,2,2,] 1. A가 무게가 1인 공을 선택할 때 경우의 수 -> 1*4(B가 선택할 수 있는 경우의 수 5-1) = 4 2. A가 무게가 2인 공을 선택할 때 경우의 수 -> 2*2(B가 선택할 수 있는 경우의 수 4-2) = 4 3. A가 무게가 3인 공을 선택할 때 경우의 수 -> 2*0(B가 선택할 수 있는 경우의 수 2-2) = 0 => 8가지 2. 풀이방법 1. 조합 #볼링공 고르기 # ''' 5 ..