DFS, BFS그래프, tree를 어떻게 자료구조로 표현할것인가? 를 알기 위해 먼저 자료구조 Stack, Queue를 먼저 알아봤다.더보기 Java Platform SE 8 docs.oracle.comStack : FILO or LIFO 불공평한 자료구조 입구 1개 (입구와 출구가 같다)push(n) : n을 스택에 입력 / pop() : 맨 위(앞)에 있는 원소 반환 + 삭제 / peek() : 맨 위(앞)에 있는 원소 반환Stack의 자료구조는 stack, queue, arraydeque로 만들 수 있다. (하지만 왠만하면 arraydeque를 이용) Queue : FIFO 입구 1개, 출구 1개, 같은 방향으로 요소들이 흐른?다offer(n) : 큐 끝에 n 추가 / poll() : 큐 앞에 요소..

15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 과정 이전 15663번과 유사한데 수열이 무조건 오름차순으로 구성되어야한다는 차이점이 있다. 그래서 같은 수열 내에 바로 이전 숫자와 비교해서 같거나 더 클 경우에만 수열에 추가했다. 다만, 이전 숫자를 비교하는 과정에서 index가 0일 경우 이전 숫자가 없어서 잘못된 숫자가 나온다. 따라서 인덱스를 0~M-1이 아닌 1~M 까지로 저하고, 이에 맞춰서 몇몇 코드를 수정했다. 코드 #include #include #include using namespace ..

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 과정 주어진 숫자를 오름차순으로 정렬 후 (sort) 주어진 숫자들 중 M개를 뽑아서 수열을 만든다. (중복X) 다만, 이번에는 주어지는 숫자들 중 중복되는 숫자가 있다. : 그래서 같은 수열이 나올 수 있다는 것! 그래서 처음에는 if 문에 number[count] != sortNum[i]를 추가해서 이미 출력된 이전 수열의 같은 자리 숫자 number[count] vs 현재 집어넣으려는 숫자 sortNum[i]를 비교했다. 이 코드의 반례는 다음과 같다. 원..

15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 과정 이전에 풀었던 문제 2가지를 섞은 유형이다. 1부터 시작이 아닌 주어지는 숫자들을 오름차순으로 정리, 같은 수를 골라도 되지만 반드시 오름차순으로 수열을 구성할 것. 백준 15654 (DFS, 백트래킹) 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M ssin-estella.tistory...

15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 과정 [C++/백준문제] - 백준 15650, 15652 (DFS) 백준 15650, 15652 (DFS) 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하 ssin-estella.tistory.com 이거랑 비슷한 문제인데 1부터 시작이 아니다. : 때문에 오름차순으로 정렬을 해줘야한다. 본인은 포함하지..

15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 과정 처음 보자마자 다중 for문이 생각났다. 다중 for문이면 대부분 DFS로 풀 수 있던걸 생각해서 DFS로 접근 처음에는 감이 안잡혔는데, 다음 그림을 그리게 된다. 1~6까지 수를 기준으로 3개의 숫자를 가진 수..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 과정 대놓고 트리라고 하니까.. 그냥 DFS로 작성했다. 부모만 찾으면 되는 문제라 간단하지만;; vector선언과 메모리크기를 초기화하는 과정에서 vector와 array의 차이를 잘 모르고 있었던 것 같다. 나는 지금까지 왠만하면 vector의 크기를 MAX로 미리 고정하지 않고 resize를 통해 정해줬다. (그게 메모리적으로 이득이니까) 근데 이번 문제는 vector의 장점을 이용해서 하나의 index안에 여러값을 push_back 해야한다. 근데 이럴 경우, 선언 자체를 메모리값이 0인채로 해서 그런지 오류가 발생한다..

선형 구조 : 자료를 순차적으로 나열한 형태 배열 연결 리스트 스택/큐 비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 트리 그래프 그래프 구성 요소 정점(Vertex) : 데이터 간선(Edge) : 정점들을 연결하는데 사용 가중치 그래프 : 각 간선에 가중치(중요도, 거리등)가 있는 그래프 방향 그래프 : 정점간의 방향이 있는 그래프 DFS 깊이 우선 탐색 Depth First Search 막다른 길(더이상 연결된 간선이 없을 때 까지)이 나올 때까지 정점을 계속 방문 하는 그래프 끝까지 갔다가 다시 시작 정점으로 돌아오는 부분은 재귀함수로 구현할 수 있다. 그래프의 전체적인 모양을 파악하기 쉽다. void Dfs(int here) { // 방문 visited[here] = true;..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 과정 이미 문제에서 그래프라고 보여주기 때문에 DFS냐 BFS냐 만 고르면 되는데 이건 DFS가 맞다 싶어서 바로 DFS로 접근했다. 2606문제와 살짝 다른점은, 간선으로 연결된 정점 뭉치들의 개수를 알고 싶기 때문에, 연결될 때마다 answer을 추가하는게 아닌, DFS를 입력할 때 접근하지 않은 정점일 때! 이때 answer을 추가했다. 코드 #include #include using names..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 과정 한 컴퓨터 기준 연결되어있는 모든 컴퓨터를 조사하는 느낌으로 저번에 풀었던 배추벌레? 문제랑 비슷한 것을 느꼈다. 그래서 DFS로 계획을 세웠다. 코드 처음에는 이렇게 작성했는데, 터미널을 보면, 2번 컴퓨터와 연결된 컴퓨터 개수가 1개라고 찍힌다. 그 이유는 main에서 시작 컴퓨터 벡터에만 연결상태를 입력했기 때문이다. #include #include using namespace std; int node = 0; // 컴퓨터 수 int edge = 0; //..