결국 빛나리라

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net > 그리디 알고리즘 가장 큰 단위의 동전가치부터 순회하면서 동전의 가치가 입력받은 k보다 작은 숫자이면 해당 동전으로 k의 가치를 차감할 수 있다는 뜻이다. 따라서 해당 가치로 k를 나눈 몫(몇 번 사용할 수 있는지 그 횟수를 나타냄)을 result에 더해주고 나머지 동전의 가치로 k값을 갱신시킨다. 여기서 중요한 점은 필요한 동전의..

https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net > 큐 활용 큐의 기본 개념을 확인하는 문제이다. 만약 시간 초과가 나온다면 다음 포스팅을 참고하자. https://westshine-data-analysis.tistory.com/63?category=843975 [백준 | 파이썬3] 1753. 최단경로- 다익스트라/ 런타임에러 input() vs stdin.readline https://www.acmicpc.net/pr..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net > 스택활용 스택의 개념에 대해 이해하는 기초 문제이기 때문에 코드 자체를 생각하는 것은어려운 문제는 아니었으나 시간초과에 신경을 써야한다. sys.stdin.readline을 사용하여 시간초과가 나지 않도록 작성해주는 것이 중요하다. 본 코드에서는 sys.stdin.readline을 사용했을 때 붙여지는 줄바꿈 문자 \n을 제거하기 위해 rstrip을 사용했지만 해당 문제에선 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 위상정렬이란 사이클이 없어 순환하지 않는 방향 그래프의 모든 노드를 방향성에 어긋나지 않도록 순서대로 나열하는 정렬이다. 만일 선수과목을 고려한 수강 과목 순서를 결정하는 문제와 같이 선후관계를 지켜야하는 알고리즘 문제가 있다면 위상정렬을 수행해 문제를 해결할 수 있다. 위상정렬에선 여러가지 답이 존재할 수 있는데 이는 작동과정에서 설명할 큐에 들어가는 원소가 두개 이상일 때 발생한다, 만일 모든 원소를 방문하기 전에 검색되어야 하는 노드들이 순서대로 들어가 있는 큐가 빈다면 이는 그래프에 사이클이 존재함을 ..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net > DFS와 BFS 이전 DFS와 BFS포스팅에서는 양방향 그래프가 아니었기 때문에 노드 연결관계를 입력값으로 넣을 때 간선이 시작하는 노드의 인덱스에 간선이 도착하는 노드의 정보를 담아 그래프를 탐색했었다. 해당 알고리즘 문제에선 양방향 그래프를 구현하는 것이 주요 포인트였다. 양방향 그래프는 그래프 노드들의 인덱스 내에서 서로 연결되어 있는 노드의 인덱스에..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net > 힙 활용 힙을 활용한 다익스트라 알고리즘 구현에서 최대 힙과 최소 힙을 구현해보았었다. 해당 문제는 최대힙을 활용해 풀 수 있었다. 힙은 요소를 꺼낼때 가장 작은 값부터 뽑아온다. 이를 활용하여 가장 큰값부터 뽑아오게 하기 위해 요소에 -를 붙여서 가장 큰값을 가장 작은 값으로 변환하여 힙에 넣고 뺄 때는 -부호를 다시 붙여서 양수로 뽑히게끔 만들었다.

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net > 다익스트라 알고리즘 활용 해당 문제는 알고리즘 구현보단 데이터를 입력하는 부분에서 애를 먹었다. 처음에는 모든 데이터를 input()으로 받았더니 계속 런타임 에러가 났다. 이럴때는 sys.stdin.readline을 사용해줘야한다. 참고한 글에 따르면 input()과 stdin는 내가 어떤 input을 입력받느냐에 따라 소요시간이 달라질 수 있다고 한다. 그 이유는..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 신장트리란? 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드는 연결하기위해 모든 간선을 사용하지 않아도 된다는 점에서 모든 노드들이 연결되어있지만 최소한의 비용으로 구성되는 신장 트리를 찾아야할 때 효율적으로 사용될 수 있다. > 시간복잡도: 해당 알고리즘에서 가장 많은 시간을 요하는 곳이 간선의 정렬을 수행하는 부분으로 간선 개수가 E개 일때 O(ElogE)의 시간복잡도를 가진다. ▶ 동작과정 step 1. 간선 비용을 오름차순으로 정렬하여 최소 비용의 간선부터 ..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net > 동적계획법 이미 계산된 적이 있는 값들은 dp리스트에서 빼와 사용하고 계산된 적이 없는 값들만 재귀함수를 호출하여 계산하도록 한다. a 또는 b또는 c가 0이하이면 바로 1을 돌려주고 20초과면 dp에서 20,20,20위치에 있는 값을 가져오면 되기 때문에 funny함수의 매개변수를 20,20,20으로 두고 실행한다. 실제로 계산을 통해 dp값을 구해놓아야 하는 범위는 1에서 20 사이의 값들 이..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net > 이진탐색 활용 #1. 런타임 에러 처음에는 target number가 있는 리스트들에 대한 반복문을 돌리면서 타겟이 A리스트에 있으면 if target in A: 1을 출력하고 아니면 0을 출력하도록 했다. 하지만 역시 런타임 에러가 났다. 1초당 1억번의 연산을 할 수 있다고 하면 n과 m에 최대 100,000개의 정수가 들어가기 때문에 최악의..