본 문제의 저작권은 프로그래머스(https://programmers.co.kr/)에 있습니다. 문제 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. Coding - Python3 처음에는 뒤에 0을 붙여서 모두 같은 자릿수를 만든다음 크기를 비교하면 된다고 생각했다. 하지만, 반례가 존재한다. [12..

본 문제의 저작권은 프로그래머스(https://programmers.co.kr/)에 있습니다. 문제 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solu..

DFS 와 BFS 에 대한 글은 아래 글을 참고한다. 2020/03/29 - [Algorithm] - 그래프 BFS, DFS 알고리즘 (with Python3) 그래프 BFS, DFS 알고리즘 (with Python3) 그래프 탐색 알고리즘에는 대표적으로 BFS 와 DFS 가 있다. 본 글에서는 아래 그래프를 가지고, BFS 와 DFS 의 탐색 알고리즘을 살펴본다. BFS 너비 우선 탐색을 BFS 라 부르고, Breadth Frist Search 의 약자이.. memostack.tistory.com 미로찾기 알고리즘 DFS, BFS 알고리즘을 이용해서 미로찾기 알고리즘을 구현할 수 있다. 문제 풀이의 핵심은 2가지이다. 미로 찾기 문제를 풀때는 미로를 모형화하여 그래프로 나타내는 것. 자료구조(Stack..

BFS 에 대한 개념은 아래 글을 참고한다. 2020/03/29 - [Algorithm] - 그래프 BFS, DFS 알고리즘 (with Python3) 탐색 알고리즘 BFS 응용 모든 노드를 탐색(방문)하면서 노드(Node)간의 비용(Cost)을 같이 구한다. 문제 사람들간의 친밀도를 구한다. 사람: 노드(Node) 친밀도: 비용(Cost) 예를들어, 사람과 사람 사이의 친밀도를 1 이라 한다. A ~ M 까지 사람이 있을때, A를 기준으로 각각의 사람들과의 친밀도를 구한다. A 와 B는 친밀도가 1이다. B 와 D는 친밀도가 1이다. A와 D는 친밀도가 2이다. ... Coding - Python3 본 글에서는 파이썬을 이용하여 문제를 풀이한다. BFS 알고리즘으로 노드를 탐색하는것은 동일하다. 단, ..

그래프 탐색 알고리즘에는 대표적으로 BFS 와 DFS 가 있다. 본 글에서는 아래 그래프를 가지고, BFS 와 DFS 의 탐색 알고리즘을 살펴본다. BFS 너비 우선 탐색을 BFS라 부르고, Breadth Frist Search 의 약자이다. 해당 노드와 같은 레벨(Level)의 노드를 먼저 탐색을 하기 때문에 붙여진 이름이다. 위 그래프를 예로 탐색 순서를 나열하면, 아래와 같은 순서로 탐색을 하게된다. A - B - C - D - E - F - G - H - I - J - K - L - M 코드 아래 코드는 unittest 기반으로 작성했다. 알고리즘은 bfs() 메소드를 참고한다. # -*- coding: utf-8 -*- import unittest def bfs(graph, start): """..

Palindrome 팰린드롬은 한국말로 회문이라고 한다. 회문은 거꾸로 읽어도 같은 문자열이 되는 문자열을 말한다. 예를들어서, "mom", "bob", "12321" 과 같은 문자열을 말한다. 팰린드롬을 확인하는 방법은 여러가지가 있겠지만, 큐와 스택의 특성을 이용하면 쉽게 찾을 수 있다. 큐는 FIFO 특징을 가지고 있고, 스택은 LIFO 특징을 가지고 있다. 큐와 스택에 대한 개념은 아래글을 참고한다. 2020/03/28 - [Algorithm] - 큐(Queue) 와 스택(Stack) 자료구조 로직(Logic) 큐와 스택에 각각 문자열을 담는다. 큐에서 꺼낸값과 스택에서 꺼낸값이 모두 같다면 회문이다. 예를들어서, 12321 이라는 회문이 있을때, 큐와 스택에 각각 담는다. => queue: 12..

큐와 스택은 문제를 해결하면서 굉장히 많이 사용하는 자료구조이다. 큐(Queue) 큐는 먼저 들어온 원소가 가장 먼저 나간다는 특징이 있다. 이러한 특징을 FIFO(First-In First-Out) 이라고 한다. 큐에 원소가 들어가는 것을 인큐(enqueue) 라고 하고, 반대로 나가는 것을 디큐(dequeue)라고 한다. 예를들어, [1, 2, 3, 4] 라는 데이터를 큐에 담고 뺀다고 해보자 1을 넣는다. => queue: 1 2를 넣는다. => queue: 1, 2 값을 뺀다. => 1이 나온다. => queue: 2 3를 넣는다. => queue: 2, 3 4를 넣는다. => queue: 2, 3, 4 값을 뺀다. => 2가 나온다. => queue: 3, 4 값을 뺀다. => 3이 나온다. =..

이진 탐색 알고리즘 이진 탐색(Binary Search) 알고리즘은 순차 탐색 알고리즘보다 더 빠르게 탐색할 수 있다. 빠르게 탐색할 수 있는 이유는 둘로 분할(이분)하여 탐색하기 때문이다. 예를들어, 1000페이지까지 있는 책이 있을때 630페이지를 찾으려고 한다. 우리는 대충 책을 펼쳐서 페이지를 확인한다. 그때 500페이지라면 630 페이지는 500페이지보다 뒤에 있으므로 앞 페이지를 살펴볼 필요가 없어진다. 하지만, 이진 탐색을 하려면 위 예제와 같이 탐색할 데이터 그룹이 정렬이 되어 있어야한다는 조건이 있다. 코딩 반으로 나누어서 중간 값과 목표값(target)을 비교한다. 같다: 인덱스를 반환한다. 목표값이 중간값보다 작다: 중간값의 인덱스보다 작은 왼쪽에서 다시 찾는다. (오른쪽은 버려도된다..

버블 정렬 버블 정렬(Bubble Sort)은 바로 옆의 원소와 크기 비교를 하여 위치를 바꾸는 방법이다. 바로 옆의 원소와 크기 비교를 하고 스왑을 하면 되기 때문에 구현하기 쉬운 알고리즘이다. 코딩 아래 코드는 unittest 기반으로 작성되었다. # -*- coding: utf-8 -*- import unittest class Exam12(unittest.TestCase): @classmethod def setUp(cls): pass def test_bubble_sort(self): data = [2, 6, 3, 4, 8, 9, 1, 10] n = len(data) for _ in range(n-1): for i in range(n-1): if data[i] > data[i+1]: data[i], ..

퀵 정렬 퀵 정렬(Quick Sort)은 병합 정렬(Merge Sort)과 비슷하게 재귀 호출을 하여 정렬을 한다. 다만 퀵 정렬은 기준점과 미리 비교를 한다는 차이점이 있다. 코딩 아래 코드는 unittest 기반으로 작성되었다. 일반적인 퀵 정렬 # -*- coding: utf-8 -*- import unittest class Exam11(unittest.TestCase): @classmethod def setUp(cls): pass def test_quick_sort(self): """일반적인 퀵 정렬""" def _quick_sort(data, start, end): # 종료 조건: 정렬을 할 원소가 1개 이하인 경우 if start >= end: return # 피봇 설정 (편의상 맨 마지막 원..

병합 정렬 병합 정렬(Merge sort)은 그룹을 반으로 나눈다음 합칠때 크기에 맞게 합친다. 이 과정을 재귀적으로 수행한다. (그림 참고) 코딩 아래 코드는 unittest 기반으로 작성되었다. 일반적인 병합 정렬 # -*- coding: utf-8 -*- import unittest class Exam10(unittest.TestCase): @classmethod def setUp(cls): pass def test_merge_sort(self): """일반적인 병합 정렬""" def _merge_sort(group): # 재귀 종료 조건: 그룹이 없을때 n = len(group) if n

삽입 정렬 삽입 정렬(Insertion Sort)은 첫번째 원소부터 하나하나 차례대로 비교해가면서, 자신보다 큰 값이 나타나면 그 큰 값 앞에 놓는 방식이다. 예를들어, [2, 4, 5, 1, 3] 이 있을때, 비교 대상 2 / 정렬 후 [2, 4, 5, 1, 3] 비교 대상 4 / 정렬 후 [2, 4, 5, 1, 3] 비교 대상 5 / 정렬 후 [2, 4, 5, 1, 3] 비교 대상 1 / 정렬 후 [1, 2, 4, 5, 3] 비교 대상 3 / 정렬 후 [1, 2, 3, 4, 5] 코딩 일반적인 삽입 정렬 unittest 기반으로 작성되었다. test_insertion_sort() 를 참고한다. # -*- coding: utf-8 -*- import unittest class Exam09(unittes..

정렬 정렬(sort)은 자료의 크기를 순서대로 나열하는 것을 뜻한다. 예를들어 아래와 같은 경우를 말한다. • 입력: 정렬할 리스트(예: [35, 9, 2, 85, 17]) • 출력: 순서대로 정렬된 리스트(예: [2, 9, 17, 35, 85]) 선택 정렬 정렬에는 여러가지 방법이 있는데, 본 글은 선택 정렬(Selection Sort)에 대한 내용이다. 다른 방법의 정렬 알고리즘은 아래 글을 참고한다. 2020/03/21 - [Algorithm] - 삽입 정렬 (Insertion Sort) 알고리즘 (with Python3) 2020/03/25 - [Algorithm] - 병합 정렬 (Merge Sort) 알고리즘 (with Python3) 2020/03/25 - [Algorithm] - 퀵 정렬 (..

대학교 과제로 교수님들이 하노이탑 알고리즘을 많이 내준다. (하지만 난 비전공자라 해본적이 없음. 글 쓰면서 오늘 처음 구현해봤다.) 하노이탑 알고리즘 하노이탑은 총 3개의 기둥이 존재한다. (그림 참조) 왼쪽부터 1번째, 2번째, 3번째 기둥이라 할때, 1번째 기둥에서 3번째 기둥까지 원반들을 모두 옮겼을때, 최소 걸린 횟수를 구하는 것이 이번 알고리즘의 목표이다. (단, 그림 아래와 같은 조건이 존재) 목표 첫번째 기둥에서 세번째 기둥으로 원반을 모두 (동일한 순서로) 옮긴다. 제약 조건 원반은 한번에 하나씩만 옮길 수 있다. 옮기는 과정에서 밑에 원반보다 큰 원반이와서는 안된다. (그래서 두번째 기둥을 활용해야 함) 문제 풀이 원반이 1개 일때 첫번째 기둥에서 세번째 기둥으로 옮긴다. 원반이 2개 ..

피보나치 알고리즘 피보나치(Fibonacci) 수열은 첫번째와 두번째 원소가 0 과 1이고, 세번째 원소부터는 이전 원소 두 개의 합인 수열을 말한다. 예를들어, 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Python3 코드 아래 코드는 unittest 기반으로 작성했다. 전체 로직은 fibo() 메소드를 참고한다. # -*- coding: utf-8 -*- import unittest class Exam06(unittest.TestCase): @classmethod def setUp(cls): pass def fibo(self, k): if k == 1: return 0 elif k == 2: return 1 return self.fibo(k-1) + self.fibo(k-2) def ..

최대공약수 구하기 1을 제외한 공통 약수 중 최댓값을 최대 공약수(Greater common factor)라고 한다. 예를들어, 4 와 6 의 최대공약수는 2 이다. 15와 40의 최대 공약수는 5 이다. 최대 공약수는 두 수 중 작은 수보다 클 수 없다. 따라서 초기값을 두 수중 작은 값으로 하여 1씩 감소하면서 두 수를 나눴을때 나머지가 없는지 확인한다. 예를들어, 4와 6 중 4가 작다. 4와 6을 4로 나눈다. (4는 나누어 떨어지지만, 6은 나누어 떨어지지 않는다) 3으로 나눈다. (4는 나누어 떨어지지 않는다, 6은 나누어 떨어진다) 2로 나눈다. (둘 다 나누어 떨어진다) 따라서 2가 최대 공약수이다. Python 코드 아래 코드는 unittest 기반으로 작성했다. 주요 로직은 gcd() ..

팩토리얼 문제 1부터 n 까지의 곱, 팩토리얼(factorial)을 구하기 1! = 1 2! = 1 * 2 3! = 1 * 2 * 3 예제. 팩토리얼 구하기 아래 예제는 unittest 기반으로 작성했습니다. 그렇다고 알고리즘을 파악하는데 어려움은 없을것 같습니다. 팩토리얼을 구하는 방법에는 2가지 방법이 있다. test1(): 단순히 for 문을 이용하여 팩토리얼을 구한다. test2(): 재귀함수(recursive)를 이용하여 팩토리얼을 구한다. n! = n * (n-1)! 라는 점화식을 이용하여 재귀함수로 풀 수 있다. # -*- coding: utf-8 -*- import unittest class Exam04(unittest.TestCase): @classmethod def setUp(cls):..

중복을 제거할때는 set 집합을 이용한다. 집합의 특징 중복이 없다. (집합 내의 원소들은 서로 다른 원소를 가진다) 순서가 없다. (원소간의 순서를 가지지 않는다) 중복된 원소를 제거할때, 집합(set)을 이용하면 효율적이다. 예제. 동명이인 찾기 n 명의 주어진 이름들이 있을때, 동명이인인 이름을 찾는다. 예제 입력: Tom Mike Jerry Tom 예제 출력: Tom 코드 2가지 방법으로 풀어볼 수 있다. test1() 메소드와 같이 집합을 이용하는 방법. test2() 메소드와 같이 하나 하나 모두다 비교해서 답을 찾는 방법. # -*- coding: utf-8 -*- import unittest class Exam03(unittest.TestCase): """n 명의 주어진 이름들이 있을때, ..

순열 [1, 2, 3]의 순열은 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 이다. 이처럼 같은 원소가 중복되지 않고, 조합하여 나올 수 있는 모든 경우의 집합을 뜻한다. 재귀와 스택을 이용해서 순열을 생성하는 코드를 작성한다. 코드 아래 2가지 자료구조를 사용한다. Stack stack: 원소를 담을 스택 boolean[] chosen: 이미 포함한 원소를 구분하기 위한 불리안 배열 private static void search(Stack stack) { if (stack.size() >= n) { System.out.println(stack.toString()); } else { for(int i=1; i= n) { System..

멱집합 구하기 Stack과 Recursive를 이용하여, 멱집합 (Power Set) 을 구한다. {1, 2, 3} 집합의 부분 집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이다. (공집합 포함) Java 코드 재귀함수 search() search() 메소드를 생성한다. private static void search(Stack stack, int k) { if(k >= n + 1) { System.out.println(stack.toString()); // 부분 집합을 출력한다. } else { // k를 부분집합에 포함한다. stack.add(k); search(stack, k + 1); // k를 부분집합에 포함하지 않는다. stack.pop..