전체 글 25

예상 대진표 문제 (1) - 개요

들어가는 글 안녕하세요 오랜만입니다. 한 동안 코틀린의 대해서 유용한 기능이나 팁 등을 알아보는 시간을 가졌습니다. 이러한 글을 쓰는 것은 저도 정리가 되는 부분이 있어 유용합니다. 가끔씩 생각나지 않은 부분이 있다면, 한 번씩 둘러보게 되더라고요. 이 뿐만 아니라, 남들에게 도움도 될 수 있다면 더 좋겠죠. 이러한 나날이 계속되던 중에 우연히 프로그래머스에 있는 문제를 풀어보았는데 이에 대해서 글을 써 보는 것도 좋겠다는 생각이 들었습니다. 이번 시간에는 우리가 지금까지 다뤄왔던 자료구조인 이진트리를 비트 연산을 통해 쉽게 다루 어보는 시간을 가지려고 합니다. 자세한 수학적인 설명과, 문제 풀이를 통해서 이번 글을 써 보려고 합니다. 문제 해당 문제의 출처는 다음과 같습니다. https://progra..

알고리즘 5+1 2021.07.03

Kotlin diary (3) - 컬렉션

들어가는 글 저번 시간에 스트림 함수의 대해서 다뤄보다가, 컬렉션 함수의 대해서도 좀 알아보는 것도 좋다는 생각이 들었습니다. 대략적으로 알고는 있었지만, 그래도 세부적으로 알아보는게 더 좋겠죠. 이번시간에서는 kotlin에서 다루는 컬렉션 함수의 대해서 다뤄 보도록 하겠습니다. 예제 코드는 https://play.kotlinlang.org/ 에서 확인해 보실 수 있습니다. Kotlin Playground: Edit, Run, Share Kotlin Code Online play.kotlinlang.org 컬렉션이란 kotlin이나 java나 모두 컬렉션은 가지고 있고, 사실 거의 다른 점은 거의 없습니다. 다만 이번글에서는 kotlin중심으로 진행하도록 하겠습니다. kotlin은 kotlin.colle..

알고리즘 5+1 2021.06.26

Kotlin diary (2) - 스트림 함수들

들어가는 글 이번시간에는 저번에 이어서 kotlin의 스트림 함수들의 대해서 알아보려고 합니다. 스트림함수는 여러 언어에서도 볼 수 있지만, 기분탓인지는 몰라도 kotlin은 다른 언어의 비해 스트림함수가 재미있고, 종류도 많으며, 또 사용하기 편한것이 많은 것 같습니다. kotlin에서 다룰 수 있는 스트림 함수를 10가지 주제로 나누어서 정리하였습니다. 예제 코드는 https://play.kotlinlang.org/ 에서 확인해 보실 수 있습니다. 1. 단순 반복(foreach) 가장 기본적인 것부터 살펴봅시다. 우선 간단하게 단어가 담긴 'numbers' 라는 리스트를 생성하였습니다. 리스트의 경우는 캐스팅할 수 있는 toList()라는 메서드가 있습니다. 이가 유용하게 사용될 때는 간단하게 배열의..

알고리즘 5+1 2021.06.16

Kotlin diary (1) - 자주 사용했던 것들

들어가는 글 이번시간에는 잠시 쉬어가는 글로, 제가 알고리즘 문제를 풀면서 조금씩 정리했었던 것들을 10개정도 모아보았습니다. 이렇게 이따금씩 올려보는 것도 좋을 것 같아 이렇게 올리게 되었습니다. 예제 코드는 https://play.kotlinlang.org/ 에서 확인해 보실 수 있습니다. 1. 문자열 제어 (StringBuilder 사용) 제가 아주 예전에 당황했던 것은, 문자열은 처음 선언됨과 동시, 바꿀 수 없다는 것이였습니다. 코틀린에서는 이렇게 StringBuilder를 지원합니다. 이렇게 하면 문자열을 순회함과 동시에, 해당 인덱스의 요소를 변경하거나 할 수 있습니다. fun main() { var str = StringBuilder() str.append("hello") println(s..

알고리즘 5+1 2021.05.30

Knapsack Problem(4) - 알고리즘 구현하기

○ 이어가는 글 https://kuck-su-labor.tistory.com/64 위 글에서 이어집니다. ○ 들어가는 글 우리는 이전까지 알고리즘을 짚어보면서 어떻게 동작하는 지의 대해서 알아보았습니다. 이번 시간에는 이러한 알고리즘을 직접 구현해보도록 하겠습니다. ○ 1. 완전 탐색 트리 구현 이 부분은 우리가 구현해 본 적이 있었습니다. 크게 달라지는 부분은 없기 때문에 이 부분은 생략하도록 하겠습니다. 자세한 내용은 이전글을 참조해 주세요 이전 글 : https://kuck-su-labor.tistory.com/61 우선 구현하면 다음처럼 될 것입니다. var MaxV : Int = 0 fun main() { val K : Int = 7 // 가방의 크기 val WnV = mutableListOf(..

알고리즘 5+1 2021.05.22

Knapsack Problem(3) - 알고리즘 짚어보기

○ 이어가는 글 https://kuck-su-labor.tistory.com/62 위 글에서 이어집니다. ○ 들어가는 글 우리는 Knapsack Problem을 해결하기 위해서 다음과 같은 순서로 알고리즘을 구성할 수 있다고 했습니다. 1. 기본적으로 알고리즘은 재귀를 이용한 완전 탐색을 사용합니다. 2. 이를 통해서 한 번의 노드 탐색이 끝나고, 최대로 담을 수 있는 V값을(한 번의 순회로 얻어진) 구합니다. 3. 다음 순회를 진행할지 결정하는 지표 FV를 구합니다. 이는 가성비대로 선택, 남는 공간은 분할하여 최대로 담아 얻어진, 순회로 얻을 수 있는 최대의 예상 값입니다. 4. V와 FV를 비교하여 만약 FV가 V의 값보다 작다면 ( FV < V ) 앞으로의 순회에서 FV보다 큰 값이 나올 확률이 ..

알고리즘 5+1 2021.05.14

Knapsack Problem(2) - 근사 알고리즘 적용하기

○ 이어가는 글 https://kuck-su-labor.tistory.com/61 위 글에서 이어집니다. ○ 들어가는 글 우리는 이전 글에서 다음과 같은 의문점에 대해서 알아보았습니다. 순회 초반에 값을 얻었다면, 굳이 계속 순회할 필요가 있을까? 중간에 멈출 방법이 없을까? 그 때문에 순회를 계속 속행해야 하는지에 대한 여부를 우리는 구해야 합니다. 그렇다면 어떻게 이를 구할 수 있을까요? 우선 우리가 생각할 수 있는 것은, 순회 도중 지금까지 구한 가장 큰 가치의 값 V가 있을 때, 앞으로 구할 수 있는 최대 가치 FV가 V보다 작다면 우리는 굳이 순회를 돌 필요가 없습니다. 왜냐하면 어차피 돌아도 V보다 큰 값은 나올 수 없기 때문에, 순회를 계속해도 V의 값은 변함이 없을 겁니다. 우리는 이전 글..

알고리즘 5+1 2021.05.10

Knapsack Problem(1) - (재귀로 구현하기)

○들어가는 글 우리는 지금까지 tree(이진 트리) 알고리즘과 greedy 알고리즘을 알아보았습니다. 이제 우리는 이 2가지 알고리즘 (이진트리 + 근사 알고리즘) 을 이용해서 좀 더 효율적인 knapsack 알고리즘을 만들어 보려고 합니다. 오늘의 경우는 구현 부분보다는 이론적으로 어떻게 만들 것인지의 대해서 설명해 보겠습니다. ○ 재귀로 구현한 knapsack 알고리즘 우리는 재귀로 구현한 tree 알고리즘으로 knapsack 알고리즘을 구현해 본 적 있습니다. 우선 간단하게 knapsack 알고리즘에 대해 짚고 넘어가도록 하죠 아랫글을 읽으셨다면, 그냥 넘어가셔도 상관없습니다. 이전 내용 : https://kuck-su-labor.tistory.com/52?category=968397 각각 W의 무..

알고리즘 5+1 2021.04.30

탐욕 알고리즘(2) - (greedy 알고리즘 활용 - 강의실 배정문제 )

○들어가는 글 저번 시간에는 greedy 알고리즘에 대해서 알아보았습니다. 마지막 부분에서 우리는 이 greedy 알고리즘이 항상 해를 반환해 주지는 않는다는 점을 알아보았습니다. 이번 시간에는 1개의 예제 문제를 풀어보면서, 간단하게 greedy 알고리즘을 구현할 때 신경써야 할 것들이 무엇인지 알아보려고 합니다. ○ 강의실 배정문제 강의실 배정의 문제입니다. N개의 강의가 있고, 각 강의의 시작 시각과 종료 시간이 있을 때, 서로 겹치지 않는 선에서 가능한 많은 강의를 듣는 방법을 구하는 것입니다. 시작 시각 S와 종료 시간 F 가 주어진 임의의 강의 N개가 있을 때, 서로 겹치지 않으면서 최대한 많이 수강하는 방법을 구하시오. ○ 최적 조건의 증명 (탐욕 선택 속성의 만족) 저번 시간에 우리가 알 ..

알고리즘 5+1 2021.04.21

탐욕 알고리즘(1 - greedy 알고리즘 소개)

○들어가는 글 우리는 지금까지 트리 알고리즘과 완전 탐색의 대해서 알아보았습니다. 그중에서 완전 탐색을 이용한 knapsack 알고리즘을 구현해 보기도 하였습니다. ( https://kuck-su-labor.tistory.com/52 ) 하지만 이러한 완전 탐색은 시간복잡도가 높아서 비효율적이라는 이야기도 했었습니다. 따라서 우리는 Greedy 알고리즘을 같이 사용하여 완전 탐색알고리즘의 성능을 높이는 knapsack 알고리즘을 구현해보려고 합니다. 지금까지 완전 탐색을 진행했었으니, 이제는 Greedy 알고리즘을 확인해 보면 되겠죠. 이번 글에서는 Greedy 알고리즘에 대해서 알아보고, 어떠한 특징이 있는지 간단히 알아보려고 합니다. 그리고 다음에는 간단한 실습으로 이 부분을 마무리 지으려고 합니다...

알고리즘 5+1 2021.04.15