차근차근정확하게

문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 문제분석DFS와 BFS를 차례대로 구현하면 된다.주의할점은 정점번호가 작은 것을 먼저 방문하므로, 인접 인덱스를 정렬을 해서 방문할 순서를 정해야..

문제BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.[조건]첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.[출력]문제의 조건에 맞는 A, B, C, D,..

문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 문제분석연결요소란, edge끼리 이어져있는 요소의 개수를 세라는 의미로서, DFS가 한번 끝난 횟수를 의미 (DFS 한번 끝난 경우 : 스택이 비어서 다음 edge값이 들어가기 전까지 )DFS가 한번 끝날때까지의 count를 기록 예제 입력예제 출력6 51 22 55 13 44 62  DFS 핵심이론방문을 기록하여, 재방문없이 모든..

문제오름차순으로 정렬하시오(첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.) 문제분석입력의 수의 범위가 많으므로, 일반적인 정렬은 선택하는데에 시간초과의 가능성이 존재한다기수 정렬을 이용하여 (O(KN)), 메모리 사용을 주의하며 작성  기수정렬 방식자릿수별로 Queue를 이용하여, 정렬하고 이후 정렬될 숫자의 최대 자릿수만큼 반복하며 정렬하는 방식시간복잡도 : O(KN) , K는 최대 자릿수정렬 수 : 601220453075328899302060 3212  7545  88990123456789일의 자리 정렬 :6020301232457588991220323045607588990123456..

문제버블정렬에 관한 이야기 진행- 인접해 있는 두 수를 swap하며 정렬 진행- (배열 크기 + 배열 제공)- 버블정렬을 진행할 때, swap하는 횟수를 구하는 프로그램을 작성하시오시간 제한 : 1초버블정렬 시간복잡도 : O(N^2)배열 범위 : 1 문제분석버블정렬로 진행할 시, 시간 초과로 인해 swap을 구하더라도 문제에 제시되어있는 시간을 지킬 수가 없다.따라서, O(NlogN)을 가진 정렬하는 방식을 채택해야함(병합 정렬 선택)병합정렬 선택시 주의할점)병합정렬이 swap되는 횟수를 구하는 것이 아닌, 버블정렬이 swap되는 횟수를 구해야함인덱스 위치의 변화를 통한 , 버블정렬의 swap 횟수를 구해야함예시2를 이동시에 5와 6을 뒤로 보내야한다 ( 버블정렬 시 swap되는 항목 )(2,5) , (..

문제- 배열의 크기 N 제공- 배열 제공 ( 개행을 통해 입력 )- 해당 배열을 오름차순으로 정렬(1 문제분석1,000,000이므로 O(NlogN)으로 해결할 수 있는 정렬 방법 탐색- 병합정렬을 이용하여, 정렬 진행  병합정렬 예시순서배열첫번째42 (set1)32 (set2)24 (set3)60 (set4)15 (set5)5 (set6)90 (set7)45 (set8)두번째32 (set1)42 (set1)24 (set2)60 (set2)5 (set3)15 (set3)45 (set4)90 (set4)세번째24( set1)32 (set1)42 (set1)60 (set1)5 (set2)15 (set2)45 (set2)90 (set2)네번째 (정렬)515243242456090set를 작은 단위의 그룹으로 나눈..

정렬정렬 알고리즘정의시간복잡도삽입대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식O(N) ~ O(N^2)버블데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식O(N^2)선택대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식O(N^2)퀵pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식O(NlogN) ~ O(N^2)힙이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해정렬하는 방식O(NlogN)병합이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식O(NlogN) + 추가적인 메모리 필요기수데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식O(N) + 추가적인 메모리 필요 병합정렬병합..

문제1번째 줄에 정렬할 수 N이 주어진다.N은 1,000,000,000 보다 작거나 같은 자연수다(주어진 N을 내림차순으로 정렬하시오) 문제분석- 자연수를 받아서, 정렬하는 문제이므로 먼저 숫자를 배열로 넣어야한다ex) 2143 -> 2,1,4,3 (분리필요)- 선택 정렬을 이용하여 문제풀이 진행과정빨간색 : 정렬된 수파란색 : 정렬해야하는 범위순서과정첫번째4123두번째4321세번째4321 슈도코드N(정렬할 수 입력)arr(N을 분리하여 배열로 저장)for(i=0 ~ arr 크기만큼 반복){ for(j= i ~ arr 크기만큼반복){ 현재 범위에서 최대 인덱스값 찾기 } if (현재 i값과 maxIdx값이 다르면){ swap (arr[i], arr[maxIdx]) }}..