본문 바로가기

자료구조76

[Baekjoon] 1874. 스택 수열 # Problem 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,0.. 2021. 4. 15.
[Baekjoon] 2798. 블랙잭 # Problem 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주.. 2021. 4. 15.
[Baekjoon] 2920. 음계 # Problem 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8부터 1까지 차례대로 연주한다면 descending, 둘 다 아니라면 mixed 이다. 연주한 순서가 주어졌을 때, 이것이 ascending인지, descending인지, 아니면 mixed인지 판별하는 프로그램을 작성하시오. 입력 첫째 줄에 8개 숫자가 주어진다. 이 숫자는 문제 설명에서 설명한 음이며, 1부터 8까지 숫자가 한 번씩 등장한다. 출력 첫째 줄에 ascending, descending, mixed 중 하나를 출력한다. # My Answe.. 2021. 4. 15.
[코딩 + 알고리즘 완주반] 24일차. 백트래킹 # 백트래킹 - 제약조건만족 문제에서 해를 찾기 위한 전략 - 해를 찾기 위해 조건을 점진적으로 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단하는 즉시 backtrack( 다시 이 후보군을 체크하지 않음) 하고 다른 후보군으로 넘어가 최적의 해를 찾는 방법 - 모든 경우의 수를 상태공간트리 (State Space Tree) 를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - Promising : 해당 루트가 조건에 맞는지 검사하는 기법 - Pruning (가지치기) : 조건에 맞지 않으면포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법 # N-Queen 문제 N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제 퀸 : 수직, 수평, 대각선 이동 가능 Pr.. 2021. 4. 14.
[코딩 + 알고리즘 완주반] 23일차. 최소 신장 트리 - 프림 알고리즘 (Prim's algorithm) # 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방법 ( 크루스칼 알고리즘은 전체에서 가장 작은 간선) 1. 임의의 정점을 선택하여 연결된 노드 집합에 삽입 2. 선택한 정점에 연결된 간선들을 간선 리스트에 삽입 3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서 ( 전에 넣었던 간선들 포함 간선리스트에서 가장 최소인 값 ) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 이미 있다면 skip (cycle 방지) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 있지 않다면 해당 간선을 선택 ( 최소신장트리에 삽입 ) (해당 간선에.. 2021. 4. 13.
[코딩 + 알고리즘 완주반] 22일차. 최소 신장 트리 # 신장 트리 (Spanning Tree) 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 모든 노드 포함, 모든 노드 서로 연결, 사이클 존재하지 않음 # 최소 신장 트리 (Minimum Spanning Tree, MST) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 Spanning Tree Kruskal's algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) # Kruskal's algorithm(크루스칼 알고리즘) 가중치가 가장 작은 간선부터 연결 ( 사이클일 경우 넘어감 ) # Union-Find 알고리즘 - 사이클이 생기는지 확인하는 알고리즘 Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘 Di.. 2021. 4. 9.
반응형

티스토리툴바