문제 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 풀이 방식 문제 자체는 쉬워서 풀이할것도 없다. C++과 같은 경우 vector을 사용해 algorithm.h 에 내장된 sort 함수를 사용해주면 된다. 다만 문제가 되는 부분은 이 부분이다. // case 1 for (int i = 0; i < n; i++) cout v[i]; sort(v.begin(), v.end()); for (int i = 0; i ..

인접 행렬 (Adjacency Matrix) 두 정점 간의 연결 관계를 N x N 크기의 행렬(2차원 배열)로 나타냄. 특정 노드와 연결되어 있는 모든 노드 확인: O(N) 두 정점 간의 연결 관계 확인: O(1) 공간 복잡도: O(N^2) 정점이 많아지면 메모리 초과로 인해 사용 불가 무방향 그래프의 경우, 주대각선을 기준으로 대칭인 성질을 지닌다. 인접 행렬의 장점 & 단점 [ 장점 ] 구현이 쉬움. 두 정점간의 연결 관계 확인해야 하는 경우, 확인이 쉽다. [ 단점 ] 특정 노드와 연결된 모든 노드를 검색해야 할 경우, 노드 개수 O(N) 만큼의 시간복잡도를 지님. 전체 노드 탐색 시 시간복잡도: O(N^2) 인접 행렬 구현 //해당 인접 행렬은 무방향 그래프의 경우이다. #include using..

문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 정점의 개수가 N, 간선의 개수가 M, 시작하는 정점의 번호가 V이다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점..

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 설명 오르막 수는 수가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. - 가능: 2234, 3678, 11119 - 불가능: 2232, 3676, 91111 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하라. 0으로 시작가능. 풀이 방식 다음 이미지대로 하면 된다. 이게 DP의 방식 인지는 모르겠는데.. 이전의 값을 가지고 와서 현재의 값을 만들어 낸다. 다음..

문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 설명 스택의 특성에 따라 수열을 만들 것이다. 하지만 이 수열에 push 하는 순서는 반드시 오름차순을 지켜야 한다. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 판단하고, 어떤 순서로 push와 pop을 수행해야 하는지 알아내라. 풀이 방식 우선 문제의 이해가 조금 어려웠다. 예시를 들어 설명하자면, 예제의 size가 8인 스택에 수열을 ..