마이구미의 HelloWorld 마이구미의 HelloWorld

이 글은 합병정렬(merge sort) 또는 머지소트 라고 불리는 정렬 알고리즘을 다룬다.누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.빠른 정렬에 분류되고 퀵정렬과 많이 언급되는 정렬이다.이유는 분할 정복 방식을 따르기 때문이다.퀵 정렬 - http://mygumi.tistory.com/308 1. 합병정렬이란 무엇인가?2. 합병정렬은 어떻게 구현하는가?3. 합병정렬의 유용한 예는 언제인가? 합병정렬은 분할 정복 방법을 통해 구현된다.분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다.(* 이전 글에서 다룬 퀵정렬도 분할 정복 방식을 가진다.) 시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 을 가진다.또한 안정 정렬로 속한다. (안정 정렬의 의미를 모른다면 참고글) ..

이 글은 정렬 중 퀵소트(Quick Sort), 퀵정렬이라고 불리는 정렬을 다뤄본다.누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.빠른 정렬에 분류되고 기본적인 버블 정렬처럼 많이 언급되는 정렬이다. 1. 퀵소트란 무엇인가?2. 퀵소트는 어떻게 구현하는가?3. 퀵소트는 어떻게 개선할 수 있는가? -위키- 퀵소트는 분할 정복 방법을 통해 구현된다.분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다. 시간복잡도는 최악의 경우 O(n^2), 평균적으로 O(nlogn) 을 가진다.시간복잡도가 O(n^2) 임에도 불구하고 퀵소트가 빠른 정렬에 속하는 이유에 대해 의문을 가질 수 있다.하지만 O(n^2) 은 설계를 통해 개선이 가능한 부분이다. 관련 내용은 아래에서 다루니 끝까지 읽는다..

이 글은 백준 알고리즘 문제 14890번 "경사로" 를 풀이한다.접근 방법은 단순 문제 이해를 통한 구현이 된다.2017 삼성 SW 역량 테스트 기출문제이다.문제 링크 - https://www.acmicpc.net/problem/14890 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.경사로는 낮은..

이 글은 백준 알고리즘 문제 14891번 "톱니바퀴" 를 풀이한다.2017 삼성 SW 역량 테스트 기출 문제이다.시뮬레이션을 통한 하드코딩으로 풀 수도 있다.본인의 접근 방법은 덱(dequeue) 과 같은 개념과 재귀를 활용해 문제를 해결한다.문제 링크 - https://www.acmicpc.net/problem/14891 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞..

이 글은 백준 알고리즘 문제 10837번 "동전 게임" 을 다뤄본다.정올(KOI) 중등부, 고등부 출제 문제이다.규칙을 찾아 단순한 구현을 통해 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/10837 영희와 동수는 동전 던지기 게임을 하고 있다. 이 게임은 K번 라운드로 구성되고 다음과 같은 규칙들을 따른다:한 라운드에서 영희와 동수는 한 번씩 동전을 던지고 항상 영희가 먼저 던진다. 동전을 던져 앞면이 나오면 1점을 얻고, 뒷면이 나오면 점수를 얻지 못한다. 한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시점에서도 게임은 바로 끝난다. 위 표에서 영희와 동수의 점수가 0과 2가 되는 것이 불가능한 이유는 ..

이 글은 디자인 패턴 중 MVC, MVP, MVVM 패턴을 다룬다.현재 프론트엔드, 백엔드, 앱 개발에서 많이 들리는 용어이다.다른 패턴도 있지만, 현재 주로 사용하고, 알려져있는 패턴이라고 볼 수 있다. MVC => Model - View - ControllerMVP => Model - View - PresenterMVVM => Model - View - ViewModel MVC 패턴은 크게 Model-View-Controller 3가지로 나눈 소프트웨어 개발 방법론이다.현재에는 프레임워크 자체에 적용되어있어, 자연스럽게 접할 수 있고, 접하고 있을 것이다. 웹, 앱 개발시 많이 사용되고 있어, 다음과 같이 표현하기도 한다.사용자가 Controller 를 조작하면, Controller 는 Model 을..

이전에 LIS 알고리즘을 다룬적이 있다.다뤘던 글의 시간복잡도는 O(n^2) 이라면, 이번에는 O(nlogn) 을 다룬다.또한, 응용된 LIS 추적도 살펴본다.결론적으로 가장 긴 증가하는 부분 수열 시리즈(1 ~ 5) 등과 같은 문제들을 해결할 수 있다.이 방식은 이분 탐색을 요구한다.LIS O(n^2) - http://mygumi.tistory.com/69이분 탐색 - http://mygumi.tistory.com/72참고 링크 - http://www.crocus.co.kr/681 O(nlogn) 방식의 경우에는 이분 탐색을 활용한 방식이다.구현에 대한 흐름은 다음과 같다. 배열 마지막 요소보다 새로운 수가 크다면, 배열에 넣는다.그렇지 않다면, 그 수가 들어갈 자리에 넣는다. (이분 탐색을 통해 들어..

이 글은 백준 알고리즘 3085번 "사탕 게임" 을 풀이한다.방법은 브루트 포스(노가다)를 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/3085 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 문제는 인접한 두 칸을 고른 후, 고른 칸을 서로 교환(swap)한 ..