백준 1062 : 가르침 등급 : Gold IV 1062번: 가르침 (acmicpc.net) 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 사용 알고리즘 : Brute-Force, Backtracking, Bitmasking 사용 자료구조 : Vector 백트래킹과 비트마스킹을 적절히 이용하여 풀 수 있는 문제. 탐색 완료를 점검하는 조건에서 코너 케이스가 있어 반례를 찾고 수정하는 데 약간 애를 먹었다. 1. 전체 단어 중 포함된 알파벳을 저장할 배열 chk[26]과, 현재 단어에서 포함된 알파벳을..
[백준] 2957번 : 이진 탐색 트리 - C++
백준 2957 : 이진 탐색 트리 등급 : Platinum V 2957번: 이진 탐색 트리 (acmicpc.net) 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 사용 알고리즘 : - 사용 자료구조 : Map 이진 탐색 트리의 구조와 특성을 물어보는 문제. 이진 탐색 트리에 자료가 들어가는 구조와 upper_bound를 알고있으면 쉽게 풀 수 있다. 1. Key에 삽입되는 Node 이름, Value에 Depth를 입력해주기 위해 map 를 선언. 2. 1≤N≤300,000이므로 0과 300,001 자리..
백준 12852번 : 1로 만들기 2 등급 : Silver I 12852번: 1로 만들기 2 (acmicpc.net) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 사용 알고리즘 : Dynamic Programming 사용 자료구조 : - 처음엔 BFS 문제인 줄 알았으나, 경로 저장에 적합하지 않고 시간 초과 발생. 각 정점에 대한 최소 횟수가 정해져 있으므로, 최단 거리 값을 구해 저장하는 다이나믹 프로그래밍 기법 이용. 1. 크기가 1000000인 DP 배열과 각 정점의 직전 점을 저장할 Before 배열 생성. 2. 1일 때 까지의 경로를 구하는 것이므로, N=1인 경우에는 방법이 0개. → DP[1] = ..
백준 12100번 : 2048 (Easy) 등급 : Gold II 12100번: 2048 (Easy) (acmicpc.net) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 사용 알고리즘 : Brute-Force, Backtracking 사용 자료구조 : Deque 각 블럭의 이동을 모두 직접 구현해주고, 그에 따른 최대값을 도출하는 문제. ( 전치 행렬에 대한 부분에서 헷갈리실 수 있다고 생각이 드는데, 추후에 필요하면 더 업데이트 하도록 하겠습니다 ) 1. 전치행렬로 변환시키는..
백준 4196번 : 도미노 등급 : Platinum IV 4196번: 도미노 (acmicpc.net) 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 사용 알고리즘 : SCC 사용 자료구조 : Vector 각 도미노를 SCC 단위로 나눠주고, 각 SCC에 들어오는 간선 Indegree값을 저장해 푸는 문제. 1. SCC를 구하기 위해 순방향으로 DFS, 그리고 스택에 쌓인 순서대로 역방향 DFS를 진행해준다. (기존 SCC 알고리즘) 2. 역방향 DFS를 순회할 때 처음 방문하는 정점(Vertex)에는 SCC의 번호를 달아준..