DFS와 BFS 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로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(..
1. 그래프의 정의 그래프라 하면 일반적으로 '정점(노드)'와 '간선(엣지)'으로 이루어진 자료구조를 의미한다. 또한 간선의 방향 유무에 따라서 단방향 그래프와 무방향 그래프(양방향 그래프)로 나뉜다. 2. 그래프의 표현 그래프를 표현하는 방식은 크게 인접 행렬 그래프와 인접 리스트 그래프 2가지로 나눌 수 있다. 일반적으로는 인접행렬 방식을 많이 사용하며, 경우에 따라 인접리스트 방식을 사용한다. 2-1. 인접 행렬 그래프 - "모든 정보를 저장" - 장점 : 직관적이며 쉽게 구현 가능 - 단점 : 불필요한 정보의 저장이 많으며, 그래프의 크기가 커지면 메모리 초과가 발생할 수 있음 - 구현 : int 형의 2차원 배열을 주로 이용하며, 이동할 수 있으면 1, 없으면 0으로 표기함 2-2. 인접 리스트..
1. Stack 스택(Stack)은 컴퓨터의 가장 기본적인 자료구조 중 하나이다. 후입선출(Last in, First Out, LIFO)의 형태를 가지고 있는 자료구조로 가장 마지막에 입력된 데이터가 가장 먼저 제거되는 구조이다. insert()를 통해서 원하는 위치에 데이터를 넣을수도 있지만 보통 append()를 사용하여 마지막에 데이터를 추가한다. 그리고 꺼낼 때에는 pop()을 사용하여 마지막 데이터를 꺼낸다. 2. Queue 스택과 반대로 선입선출(First in, First Out) 형태의 자료구조가 큐이다. 큐에 데이터를 넣을 때는 스택과 마찬가지로 마지막에 데이터를 추가하지만, 데이터를 꺼낼 때에는 가장 앞에 있는 것을 먼저 꺼낸다. 3. Dequeue 파이썬에서는 덱(Deque)이라는 것..
계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같..
연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이..
가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30,..
