개발자 지망생의 끄적끄적 개발기록

백준 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의 번호를 달아준..

백준 13460번 : 구슬 탈출 2 등급 : Gold I 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 사용 알고리즘 : BFS 사용 자료구조 : Vector, Queue BFS를 이용해 최단 거리, 4차원 Visit 배열(빨간 공, 파란 공 각각의 좌표)을 이용하여 해결. 고려해야 할 요인이 꽤 많은 문제였다. 공이 굴러간 위치를 어떻게 지정할까 고민하다 같이 끝까지 굴리고 이후에 겹칠 경우 위치를 다시 ..