Algorithm

어떤 알고리즘? 문제는 DFS를 사용하면 풀 수 있다. 친구를 노드로 관계를 엣지로 하는 그래프로 나타낼 수 있겠다는건 쉽게 생각할 수 있다. 그러면 DFS를 사용해야겠다는 생각은 어디에서 힌트를 얻을 수 있을까 주어진 친구 관계를 나타내보면 A-B-C-D-E 이렇게 일직선상인 것을 알 수 있다. 인접한 노드를 따라 최대한 깊이 들어가고 더이상 갈 곳이 없으면 이전 정점으로 돌아가는 DFS를 떠올릴 수 있겠다. 쉽게 말하자면 DFS는 세로로 한줄씩 읽어 내려가니깐 A-B-C-D-E를 찾기에 적합하다고 볼 수 있다. 구현은? 구현은 어떻게 할 것인가? DFS를 사용하되 count를 해야 할것이다. A-B-C-D-E 이렇게 5개의 노드가 직선이여야 하니깐 인접한 노드를 찾으면서 들어갈때마다 count를 1씩..

9명중 2명은 난쟁이가 아니니깐 이중 for문을 통해 백설 공주의 난쟁이가 아닌 2명을 제외하고 7명을 고르는 모든 경우의 수를 해보고 합이 100과 같으면 출력 하는 브루트포스 방식으로 풀면 되겠다고 생각했다. 그러나 내가 간과한 사실이 있었다. 2명을 제외한 7명의 키의 합이 100이 되는 경우가 한 가지 보다 더 많을 수 있다는 것 이다. 답을 찾았는데도 for문을 벗어나지 않으면 복수의 정답이 출력이 될 것이고 이는 곧 오답이다. 문제에서는 가능한 정답이 여러 가지인 경우에는 아무거나 출력 한다고 했으니깐 이중 for문을 돌리다가 정답을 찾으면 빠져 나와야 했다. 이중 for문을 한 번에 벗어나기 위해서는 레이블을 사용하면 된다 자바에서는 switch문과 반복문 앞에 lable을 지정하여 가리킬 ..

스택을 구현해보는 문제이다. 스택의 특징이라면 후입선출(Last In First Out) 배열로 구현을 해도 괜찮겠지만 자바의 linked list를 이용하면 deque은 물론 stack도 구현이 가능하기 때문에 연습해볼겸 linked list를 사용해보았다. import java.util.*; import java.io.*; public class Main{ public static void main(String[] args)throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(..

배열의 크기가 10,000,000 이하인 문제이다. 일반적으로 1초가 주어졌을 때 입력 개수(N)가 1,000,000이면 허용되는 시간복잡도는 O(n log n)이다. 그래서 자주 쓰는 O(n log n)복잡도를 가지는 정렬로 풀기에는 무리가 있다. 그래서 O(n)을 가지는 계수정렬을 이용해야한다.[1초가 주어졌을 때 N 0) 3. 정렬 하고자 하는 배열(원래 배열)을 순회를 하고 값에 해당하는 counting 배열을 1만큼 감소를 시키고 그 값이 해당 값의 정렬된 배열의 인덱스가 된다. ex) arr[3] 이 4 이면 counting[4]--의 값이 4가 들어갈 정렬된 배열의 인덱스 (감소를 계속 시켜 나가야함) 따라서 코드는 import java.io.*; public class Main { publ..

입력이 백만까지 주어지는 문제이기 때문에 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀어야 한다. 병합정렬, 힙정렬, 퀵정렬 등이 있는데 여기서 퀵정렬은 최악의 경우 O(n^2)의 복잡도를 가지기 때문에 퀵정렬로 풀면 오답처리가 된다. 따라서 최악과 평균이 둘다 O(nlogn)인 병합정렬과 힙정렬로 풀 수 있는데 나는 병합정렬로 풀었다. 병합정렬(merge sort)이란? 분할 정복 알고리즘의 하나인 병합정렬은 다음과 같이 작동한다 분할 : 먼저 정렬되지 않은 리스트(배열)를 원소가 하나밖에 남지 않을 때까지 절반으로 나눈다. 정복 & 병합 : 나누어진 요소들을 두 개씩 정렬시키면서 합쳐 나간다. 병합정렬의 특징? 병합정렬은 분할과정에서 수행 시간이 logN 정렬자체에서 수행시간이 N이 필요하므로..

이 문제를 브루트포스로 풀게 된다면 N과 M이 20000인 경우에 20000*20000이라 대략 4억번의 연산 횟수가 시행될 것이고 보통 1초당 약 연산횟수가 1억회라고 생각 하기때문에 시간 제한이 1초인 이 문제를 틀리게 될 가능성이 높다. 따라서 이분탐색으로 문제를 풀어보자 우선 A와 B를 배열로 입력받고 B를 정렬한뒤 A값을 토대로 B를 이분탐색 한다. 따라서 이분탐색으로 문제를 풀면 B를 정렬하는 시간복잡도가 O(M logM) 이고 이분탐색이 O(logM)이며 이분탐색을 A의 크기인 N만큼 시행할것이니 대략 O(n log n)의 복잡도를 가질것이다. 정렬된 B를 A값으로 이분 탐색이 끝나면 인덱스를 기준으로 왼쪽이 항상 A보다 작은 B의 값이므로 인덱스 값이 선택된 A의 값보다 작은 B의 수이다...

빅오 표기법의 정의를 기반으로 하는 복잡도 문제이다. 보통 어떤 함수를 빅오로 표현하면 계수를 제외하고 최고차항만 나타낸다. 정의에 따라 생각해보자면 O(g(n)) = f(n) 일때 c * g(n)이 f(n)의 상한값이라고 할 수 있다. (c는 상수이다) 예를 들어 g(n) = n 이고 f(n) = 2n+1 이라고 하면 모든 n>= n0 에 대하여 f(n)

문제는 다음과 같다. 수행 횟수와 시간 복잡도를 구하는 문제이다. 우선 직관적으로 반복문이 3개가 중첩되어 있으므로 O(n^3)의 복잡도를 가질것으로 보인다. 그냥 반복문에다가 count를 넣으면 간단히 해결될 문제이지만 그러면 문제를 푸는 의미가 없다. 따라서 다른 풀이가 필요하다. [풀이 1] 삼중 for문을 분석해보면 첫번째 for문은 1부터 n-2 두번째 for문은 i+1부터 n-1 세번째 for문은 j+1부터 n 까지 반복된다. 먼저 1부터 10까지 반복하는 for문 하나의 수행 횟수를 시그마로 나타내보면 다음과 같다. (윗끝 - 아랫끝 + 1) = (10 - 1 + 1) = 10 이다. 따라서 위의 삼중 for문을 시그마 공식으로 나타내면 그리고 순차적으로 시그마 공식을 계산해보면 ⬇️ ⬇️ ..

문제 자체는 매우 심플하다 신기한건 2005년도 정보올림피아드 지역본선 초등부 문제였던 것 첫번째 방법이다. 아마 대부분이 이렇게 풀었을 것이다. import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int A = scanner.nextInt(); String B = scanner.next(); System.out.println(A*(B.charAt(2)-'0')); System.out.println(A*(B.charAt(1)-'0')); System.out.println(A*(B.charAt(0)-'0')); System.out.println..