알고리즘36 [백준] 1931 회의실 배정 1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 내풀이 회의실 배정은 알고리즘 수업을 들을 때 예제로 나올 정도로.. TIL/SW&백준 문제 리뷰 2021. 8. 9. [백준] 2309 일곱 난쟁이 2309번: 일곱 난쟁이 (acmicpc.net) 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이.. TIL/SW&백준 문제 리뷰 2021. 8. 5. [백준] 11727 2*N 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 내 풀이 2*1 , 1*2 , 2*2 타일로 채우는 방법의 수를 찾는 것 고로 2*n 블럭 만드는 경우의 수를 2* n-2 블럭에서 만드는 경우와 2* n-1 블럭에서 만드는 경우를 고려하여 dp를 만들었다. 그것을 수식으로 DP[n] = DP[n-1] + 2 * DP[.. TIL/SW&백준 문제 리뷰 2021. 7. 31. [백준] 11053 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 내 풀이 DP 로 해결할 생각까진 했지만, .. TIL/SW&백준 문제 리뷰 2021. 7. 29. [백준] 11052 카드 구매하기 11052번: 카드 구매하기 (acmicpc.net) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된.. TIL/SW&백준 문제 리뷰 2021. 7. 28. 210713 NP vs P Polynomial problems(P) : 다형식 시간으로 해결되는 문제 ex) 정렬 : O(nlog n) , O(n^2) , 등등 Exponential problems(E) : 지수 부분이 n에 따라 무한대로 증가하는 문제 ex) n^n , n^(n^2), 2^n Interactable (Non - Computable) Problems (I) -> 결정할 수 없는 문제 ex) Halting (어떤 프로 그램이 무한 루프에 빠지는지 알아내는 알고리즘) 알고리즘에서 핵심적인 문제 : Exponential 문제를 푸는 법은 아는데 이것을 polynomial time에서 해결하는 방법, 애초에 할 수 있는지를 모름 Ex) 0/1 Knapsack -> O(nW) -> O(2^n) 되면 Exponential 이.. 미가공 필기(알고리즘) 2021. 7. 13. 210712 Matrix Multiplication , 플로이드-와샬(Floyd-Warshall 알고리즘) 모든 쌍의 최단 경로(All Pairs Shortest Path, ASP)의 대표적인 알고리즘 Matrix Multiplication 예시 플로이드-와샬(Floyd-Warshall 알고리즘) 거처가는 정점을 기준으로 최단 거리를 구하는 것 다익스트라,벨만-포드의 경우는 간선 하나씩 늘어나면서 계산, 반면 플로이드-와샬은 경유하는 정점이 하나씩 늘어나면서 계산 D : 그래프의 가중치를 담은 인접행렬 , 모든 쌍의 최단경로 비용 표시 π : 선행자 인접행렬 , 최단 경로 그 자체를 구할 때 사용 k 정점을 거쳤을 때 거리가 그대로거나 더 크다면 그대로 , 작아졌다면 값을 갱신 하는 과정 pseudo code 시간 복잡도 : O(n^3) 공간 복잡도 : O(n^2) 예시 정점의 개수 4 까지 하여 나온 행렬들.. 미가공 필기(알고리즘) 2021. 7. 13. 210709 벨만-포드(Bellman-Ford), 다익스트라(Dijkstra) 최단 경로(Shortest Path)를 찾는 대표적인 알고리즘들 중 일부 벨만-포드(Bellman-Ford) 벨만포드는 가중치가 음수일 경우에도 사용가능 ( 다익스트라와의 차이점 ) 초기화 : 간선 검사 순서 임의로 정하는 등등 앞서 정한 순서대로 모든 간선 확인하며 Relax ( 정점에 기존 보다 더 낮은 가중치로 도달할 수 있으면 값 갱신 == 최단거리 값 갱신) 해줌 정점의 개수 - 1 번 만큼 반복 시간복잡도 : ( 간선의 개수 ) * ( 정점의 개수 -1 ) => O ( 간선의 개수 * 정점의 개수 ) 다익스트라(Dijkstra) Greedy 알고리즘이라고 할 수 있음 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단경로를 구하는 알고리즘 효율적, 실생활에서 많이 사용됨 ex) gp.. 미가공 필기(알고리즘) 2021. 7. 13. 210708 최소 신장 트리 with Kruskal, Prim 알고리 최소 신장 트리 (Minimum Spannig Tree, MST) 신장 트리(spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리 //신장 트리(spanning Tree) : 모든 정점을 포함하고, 정점 간 서로 연결이 되며 사이클이 존재하지 않는 그래프 Kruskal, Prim 알고리즘은 최소 신장 트리를 구하기 위한 알고리즘 Kruskal 모든 간선들 중에서 가중치가 가장 낮은 간선부터 선택하는 방식 단, 선택하는 과정에서 사이클이 만들어지는 경우에는 선택하지 않는다 n개의 정점을 가지는 그래프일 경우, n-1 개의 간선 선택하면 종료 시간복잡도 : 간선을 오름차순으로 정렬하는 것에 수행시간 좌우되기에 최선의 선택을 한다고 가정하면, O((간선의 수) * log_2 (간선의 수).. 미가공 필기(알고리즘) 2021. 7. 10. 210708 너비 우선 탐색(BFS) & 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS, Breadth - First Search) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 즉 깊게 보다 넓게를 우선시한 탐색 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 활용함 BFS의 과정 시작 정점 방문 깊이 1인 모든 노드 방문 깊이 2인 모든 노드 방문.... (반복) 더 이상 방문할 곳 없으면 탐색 마침 노드 방문 세부 과정은 (큐에서 꺼낸) 노드를 방문하였을 경우 큐에서 꺼낸 노드 방문 큐에서 꺼낸 노드와 인접한 노드들 모두 방문 방문한 노드들 큐에 삽입, 더 이상 없다면 큐에서 노드 꺼냄 이런 과정을 반복한다 예시 시간복잡도 : 인접 행렬 사용시 : O(노드수 +간선수) 인접 리스트 사용시 : O(노드수^2) 깊이 우선 탐색(DFS, Dep.. 미가공 필기(알고리즘) 2021. 7. 9. 210707 DP - 배낭 문제 (Knapsack Problem) 배낭 문제 (0/1 Knapsack Problem) 배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정한 가치와 무게가 정해져있는 짐들을 배낭에 닮을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 0/1 knapsack = 물건 못 쪼갬 Fraction knapsack = 물건 쪼갤 수 있는 문제 사실 kanpsack 문제는 dp에 있어야... 예시 문제 해결법 시간 복잡도 , 공간복잡도 미가공 필기(알고리즘) 2021. 7. 8. 210707 그리디 알고리즘(Greedy, 탐욕) 동적 프로그래밍(DP) 을 사용할 때 너무 많은 작업을 하는 경우가 발생하기에 보완하는 목적으로 생김 차이점 : 그리디 알고리즘은 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 방법 활동 선택 문제 (Activity Selection Problem) 활동 선택 문제란, 한번에 하나의 활동만 처리할 수 있는 하나의 방에서 주어진 활동들에서 최대한 많은 활동을 처리할 수 있는 스케줄을 짜는 문제입니다. 문제를 해결하는 아이디어로는 보통 평범하게는 활동시간이 짧은 순으로 정렬하여 짧은 것부터 선택하는 등의 방법들을 생각할 수 있지만, 최적의 방법은 끝나는 시간순으로 선택하면 됩니다. 허프만 부호화 (Huffman Coding) 문자의 빈도나 확률 정보 등을 이용하여 통계적으로 압축하는 방법 압축할 문자.. 미가공 필기(알고리즘) 2021. 7. 8. 이전 1 2 3 다음 반응형