알고리즘
-
[프로그래머스] 코딩테스트 Lv.0 요약알고리즘 2023. 5. 7. 11:22
이 글은 프로그래머스 코딩테스트 문제중 "코딩테스트 입문" 에 대한 내용이다. 문제에 대한 풀이가 아닌 팁들을 남기려고한다. (풀이는 아래 깃헙 링크를 참고) 문제 리스트 - https://school.programmers.co.kr/learn/challenges?order=recent&page=1&partIds=33882 풀이 코드 - https://github.com/hotehrud/acmicpc/tree/master/programmers/Lv.0 프로그래머스에서 제공하는 Lv.0 에 해당하는 100 문제를 풀어보았다. 쉬운 문제이더라도, 다른 사람의 풀이를 보면서 많은 팁들을 배우게 되었다. 그러한 내용들을 정리해보고자한다. 어떤 방식이 더 좋고 나쁘고를 말하고자 하는 것이 아니라는 것을 참고해주길..
-
비트마스크(BitMask) 는 무엇인가? :: 마이구미알고리즘 2019. 10. 20. 22:40
이 글은 비트마스크(BitMask) 기법에 대해 다룬다. 특정 알고리즘이 아닌, bit 를 활용한 테크닉이라고 할 수 있다. bit 는 low level 이 아닌 경우에는 크게 비트를 다룰 일은 없어보이지만, 분명 이해가 필요한 경우는 드물지 않다. 그렇기에, 프로그래밍 문제 풀이가 아니더라도 많은 도움이 될 것이다. 대략적인 설명이후에, 백준 알고리즘 2098번 "외판원 순회" 을 풀이한다. 백준 알고리즘 2098번 문제 "외판원 순회" - https://www.acmicpc.net/problem/2098 비트마스크는 무엇인가? 용어 그대로 비트(Bit) 에 관련된 것이다. 비트는 이진 숫자(binary digit) 를 뜻하는 말로 컴퓨터에서 사용되는 데이터의 최소 단위이다. 비트는 0, 1 의 값을 ..
-
[자료구조] 스택, 큐는 무엇인가? :: 마이구미알고리즘 2019. 9. 7. 22:35
이 글은 자료구조의 "스택, 큐" 를 다룬다. 자료구조에서 가장 먼저 나오는 기본적인 자료구조이다. 각 자료구조에 대한 깊은 설명보다는 현실적인 이해에 도움을 위해 다루려고 노력했다. 알고리즘 문제를 풀기 위해 알아야하는 지식을 위한 설명이 아닌, 현실적으로 활용할 수 있는 이해를 위한 도움에 중점을 둔다. 실제로 요즘은 자료구조를 생각하지않고도 코드를 작성할 수 있다. 예를 들어, 스택과 큐와 같은 개념은 배열로 처리하면 그만이다. 하지만 이 과정에서도 자료구조의 개념을 인지하고 활용하면 분명 코드와 개발에 도움이 된다. 본인은 왜 코딩테스트가 존재하는지도 연관이 있다고 생각한다. 자료구조를 구현하기 위한 코드를 작성해야하는가? 에 대한 글은 다른 글을 참고하길 바란다. 자료구조에서 가장 기본적인 스택..
-
거듭제곱 알고리즘 :: 마이구미알고리즘 2018. 6. 6. 06:24
이 글은 거듭제곱에 대한 알고리즘을 다룬다.거듭제곱의 성질을 이용하여 성능을 올리는 과정을 확인한다.백준 알고리즘 문제에서는 다음과 같은 문제를 해결할 수 있다.백준 1629번 곱셈 - https://www.acmicpc.net/problem/1629 거듭제곱이란 주어진 수를 주어진 횟수만큼 곱하는 연산이다.똑같은 수를 여러번 곱하기를 원할 때, 이용한다고 우리는 아마 중학교 때 배웠을 것이다. 만약 거듭제곱을 구하는 알고리즘을 작성해야한다면, 쉽게 구현할 수 있을 것이다.일반적인 방법으로 재귀함수와 반복문 방식은 각각 작성한다면, 다음과 같다. 재귀함수 거듭제곱 public static int pow(int a, int n) { if (n == 0) { return 1; } else { return a..
-
힙정렬(Heap Sort) 알고리즘 :: 마이구미알고리즘 2018. 4. 17. 09:48
이 글은 힙 정렬(heap sort), 힙 소트 라고 불리는 정렬 알고리즘을 다룬다.누구나 한번쯤은 들어봤고, 구현해본 정렬 중 하나이다.빠른 정렬에 분류되고, 시간복잡도가 같은 퀵정렬과 합병정렬과 함께 언급된다.퀵정렬 - http://mygumi.tistory.com/308합병정렬 - http://mygumi.tistory.com/309참고 링크 - https://www.geeksforgeeks.org/heap-sort/ 1. 힙 정렬이란 무엇인가?2. 힙 정렬은 어떻게 구현하는가?3. 힙 정렬은 어디에서 사용하는가? 힙 정렬은 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다.완전 이진 트리는 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리를 말한다.힙에는 부모 노드의..
-
합병정렬 알고리즘 :: 마이구미알고리즘 2018. 4. 14. 16:28
이 글은 합병정렬(merge sort) 또는 머지소트 라고 불리는 정렬 알고리즘을 다룬다.누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.빠른 정렬에 분류되고 퀵정렬과 많이 언급되는 정렬이다.이유는 분할 정복 방식을 따르기 때문이다.퀵 정렬 - http://mygumi.tistory.com/308 1. 합병정렬이란 무엇인가?2. 합병정렬은 어떻게 구현하는가?3. 합병정렬의 유용한 예는 언제인가? 합병정렬은 분할 정복 방법을 통해 구현된다.분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다.(* 이전 글에서 다룬 퀵정렬도 분할 정복 방식을 가진다.) 시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 을 가진다.또한 안정 정렬로 속한다. (안정 정렬의 의미를 모른다면 참고글) ..
-
퀵소트 알고리즘 :: 마이구미알고리즘 2018. 4. 10. 15:51
이 글은 정렬 중 퀵소트(Quick Sort), 퀵정렬이라고 불리는 정렬을 다뤄본다.누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.빠른 정렬에 분류되고 기본적인 버블 정렬처럼 많이 언급되는 정렬이다. 1. 퀵소트란 무엇인가?2. 퀵소트는 어떻게 구현하는가?3. 퀵소트는 어떻게 개선할 수 있는가? -위키- 퀵소트는 분할 정복 방법을 통해 구현된다.분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다. 시간복잡도는 최악의 경우 O(n^2), 평균적으로 O(nlogn) 을 가진다.시간복잡도가 O(n^2) 임에도 불구하고 퀵소트가 빠른 정렬에 속하는 이유에 대해 의문을 가질 수 있다.하지만 O(n^2) 은 설계를 통해 개선이 가능한 부분이다. 관련 내용은 아래에서 다루니 끝까지 읽는다..
-
LIS 최장증가수열 알고리즘 -2- :: 마이구미알고리즘 2018. 3. 18. 14:52
이전에 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) 방식의 경우에는 이분 탐색을 활용한 방식이다.구현에 대한 흐름은 다음과 같다. 배열 마지막 요소보다 새로운 수가 크다면, 배열에 넣는다.그렇지 않다면, 그 수가 들어갈 자리에 넣는다. (이분 탐색을 통해 들어..