Outgoing Introvert

○ BFS 백준 2606 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 컴퓨터의 수. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. 출력..

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

코테 문제 시작 전에 테스트용 문제였는데 나름 잼써서.. ㅎ 원래 문제 풀 생각이 없었어서 대충 보다가 비록 시간 내에 통과하지는 못했지만..? ㅠ 아마도 맞겠지..? Write a function that given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A. For example, given A = [1,3,6,4,1,2], the function should return 5. Biven A = [1,2,3], the function should return 4. Given A = [-1,-3], the function should return 1. Wri..

○ 이분탐색 4단계 백준 2805 나무 자르기 문제 나무 M미터 필요. 목재 절단기 높이 h 지정. 한 줄에 연속해있는 나무 모두 절단. 20 15 10 17 -> h: 15 -> 15 15 10 15 -> 길이 5, 2 인 나무 들고 집에 갈 것 (총 7 미터) h : 0 ~ 양의 정수. 나무를 필요한 만큼만 집으로 가져갈 것. 적어도 M 미터의 나무를 집에 가져가기 위해 절단기 설정 높이 최댓값 구하기 입력 첫줄 - 나무의 수 N, 가져가려는 나무 길이 M. 1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000 둘째줄 - 나무의 높이. M Int { var s = 0 var e = trees.max()! var result = 0 while s < e { let mid = (s +..

△ 이분탐색 3단계 백준 1654 랜선 자르기 문제 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오..

해시 ○ 이분탐색 X 백준 10816 숫자 카드 2 이분 탐색 예제로 나와서 풀었는데, 해시로 풀어버렸다.. 해시로 푸는게 훨씬 간단하고 편한거같은데..? 이분탐색은 도대체 어떻게... 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다..

Swift에서의 정렬 메서드 sort() 와 sorted() 의 차이에 대해 알아 보았다. 둘 다 시간복잡도는 O(n log n)으로 동일하지만, 사용법이 다르다. sort Sorts the collection in place. sort() 는 배열을 제자리에서 변경하며 값을 정렬하기 때문에 원본 배열의 값이 바뀐다. 값 자체가 변경이 되는 메서드이기 때문에, 정렬하고자 하는 컬렉션은 mutable 이어야 한다. mutating func sort() var arr = [7,2,16,1] arr.sort() print(arr) // [1,2,7,16] arr.sort(by: >) print(arr) // [16,7,2,1] sorted Returns the elements of the sequence, s..

이분탐색 N개의 수가 크기 순서대로 배열되어 있을 때 특정 수 K가 몇 번째 위치에 있는지 빠르게 찾는 방법 한 가운데에 있는 수를 보자 짝수면 가운데서 앞번째 절반만 남기고 그 안에서 찾기 줄어든 범위 내에서 재귀적으로 해결 한 번에 배열이 절반씩 줄어들기 때문에 시간복잡도는 O(log n) 재귀방식 or while 반복문 사용 가능 이분탐색 응용 parametric search 최적화 문제를 결정 문제로 바꾸어 푸는 것 최적화 문제 : f(i) = 1 이 되는 i 의 최솟값을 구하여라. 결정 문제 : 어떤 i 에서, f(i) = 1 인가? 이분탐색 문제들 https://www.acmicpc.net/workbook/view/9764 백준 1920 수 찾기 백준 10816 숫자 카드 2 백준 1654 랜..

백준 1920 수 찾기 binary search 이분탐색 1단계 문제 : N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 : 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000) 다음 줄에는 N개의 정수 A[1], A[2], …, A[N] 다음 줄에는 M(1 ≤ M ≤ 100,000) 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 : M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 1차 시도 시간초과 실패 .contains 의 시간복잡도는 O(n)으로 다음과 같이 for문 안에 사용..

input n에 대하여 가장 높은 차수 O(1) 상수 시간 constant time O(n) 선형 시간 linear time ex) 반복문, 반복문이 여러개(O(n)에 수렴) O(n^2) quadratic time ex) 반복문이 중첩 O(log n) 로그 시간 log time : 입력 크기에 따른 실행 횟수의 변화가 다양한 경우. ex) 이진 탐색, for (int i = 1; i \(log_2n\) O(n log n) 선형 로그 시간 : 입력 크기의 변수가 여러 개인 경우 : O(n log m) ex) O(n) 반복문 + log m 반복문 중첩 => n log m 재귀 함수의 시간 복잡도 분석 쉬운 경우 : 팩토리얼, 합병 정렬(merge sort) - 팩토리얼: T(n) = T(n - 1) + 1 ..