알고리즘
-
백준 2688번 줄어들지 않아 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 2. 20:47
이번 글은 백준 알고리즘 2688번 "줄어들지 않아" 문제를 다뤄본다.핵심은 DP라고 불리는 동적계획법이다.일단 문제를 보자. 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.각 자리 수에 따라 줄어들지 않는 경우의 수를 구하면 된다.간단하게 나타..
-
백준 1377번 버블 소트:: 마이구미알고리즘 풀이/정렬 2016. 12. 28. 22:52
이번 글은 백준 알고리즘 사이트의 1377번 "버블 소트" 를 다뤄본다.정답률은 20% 대로, 200명정도이다.1377번 버블 소트 - https://www.acmicpc.net/problem/1377 이미 문제에서도 버블 소트의 소스를 보여줬다.출력되는 정답이 의미하는 건 버블 정렬이 몇단계를 거쳤는지를 알아내는 것이다.버블 정렬을 잠깐 살펴보자. (기본적으로 버블 정렬을 숙지하고 있다고 가정하겠다.)다음과 같이 주졌다고 하자. (10 4 2 5 9 1)10 4 2 5 9 1 -> 4 10 2 5 9 1 -> 4 2 10 5 9 1 -> 4 2 5 10 9 1 -> 4 2 5 9 10 1 -> 4 2 5 9 1 10위의 경우가 1단계라고 하자.그렇다면 다음이 2단계라고 할 수 있다.4 2 5 9 1 1..
-
StringBuilder vs System.out.println :: 마이구미Java 2016. 12. 28. 20:16
이번 글의 제목은 "StringBuilder vs System.out.println" 이다.글의 목적은 알고리즘 문제들의 시간을 줄이는 것이다.그렇다면 어떻게 줄일 수 있는지 천천히 살펴보자. 대부분 알고 있듯이 System.out.println은 출력을 하기 위해 사용하고 있다. int a = 123;System.out.println(a);// 123System.out.println("Hello World!");// Hello World! 간단히 보면 표준 입출력 기능을 제공해준다고 봐도 된다.그렇다면 조금 더 깊게 System.out.println을 내부적으로 어떻게 되어있는지 보자. public void println(String x) { synchronized (this) { print(x); n..
-
LIS 최장증가수열 알고리즘 :: 마이구미알고리즘 2016. 12. 10. 11:55
이번 글의 주제는 LIS 알고리즘이다. LIS는 Longest Increasing Subsequence 로써 최장증가부분수열이라는 의미이다.시간복잡도 O(n^2)을 다룰 것이고, O(nlogn)의 경우는 링크를 보자. (관련 글) 백준 알고리즘 11053번 11055번을 가지고 진행할 것이다. 최장증가수열은 무엇인지 백준 알고리즘 사이트 문제만 읽어도 알 수 있다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 위와 같은 경우가 증가 부분 수열이다. 본인은 이번 글에서 이 문제를 가..
-
ListIterator 인터페이스 활용하기 :: 마이구미Java 2016. 11. 21. 23:21
이번 글은 자바에서 활용할 수 있는 ListIterator 인터페이스를 다룰 것이다.처음보거나 사용해본 적이 없다면 굉장히 유용하게 사용할 수 있다. 백준 알고리즘 사이트 1406번 문제 '에디터'를 접근하면서 알아보겠다. 위 문제를 간략히 살펴보면, 인덱스를 임의대로 이동하면서 삽입 및 수정 등을 처리하는 문제이다.단순히 생각해보자. ArrayList를 쓸까? LinkedList를 쓸까?삽입과 수정을 자유자재로 한다? 이렇게 해석이 가능했다면, 아마 LinkedList를 떠올렸을 거라 생각한다. 잠깐 ArrayList와 LinkedList에 대해 짚고 넘어가자. ArrayList의 경우는 데이터 삽입/삭제 시 임시 배열을 생성하여 데이터를 복사하는 방식으로 구현된다.그렇기에 데이터가 많을수록 성능이 저..
-
문자열 검색 KMP 알고리즘 :: 마이구미알고리즘 2016. 10. 28. 19:11
이번 글은 KMP 알고리즘에 대해 다룰 것이다.KMP 알고리즘이란 무엇인가?이름에 대해서는 큰 의미가 없다. 그냥 사람 이름이다. 백준 5525번, 10769번, 1786번을 풀다가 알게 된 알고리즘이다.유용한 알고리즘이기에 한명이라도 더 알리기 위해 글로 다루게 되었다. (복습 목적이지만..^^) 그렇다면 어떤 알고리즘인가? 어떤 경우에 사용하는 알고리즘인가?시작해보자.시작하기에 앞서 목적은 문자열 검색에 사용되는 알고리즘이다. 문자열 검색의 예를 들어보자.문자열 ABCEDFRIEPQJDNVABRIDFNIABC 라는 문자열이 있을 때 ABCEF라는 문자열을 찾아보자.여러분들은 어떻게 하겠는가?가장 순진한 방법을 말해보겠다. ABCEDABCEFQJDNVABRIDFNIABC ABCEFABCEDFRIEPQJ..
-
백준 1021번 회전하는 큐 [Queue] :: 마이구미알고리즘 풀이/스택, 큐 2016. 10. 19. 20:27
이번 글은 백준 1021번 회전하는 큐를 다룰 것이다.정답률 33%정도이지만 쉬운 문제이다.1021번 회전하는 큐 - https://www.acmicpc.net/problem/1021Github - https://github.com/hotehrud/acmicpc 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.첫번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.오른쪽으로 한 칸 이동시킨..