본 문제는 백준 알고리즘(https://www.acmicpc.net/)에게 있습니다. 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 예제 # 입력 3 1 # 출력 1 2 3 # 입력 4 2 # 출력 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 Coding - Python3 대표적인 순열 문제로 푸는 방식만 익히면 쉽게 문제를 풀 수 있다. for 문을 이용하는 방식과 재귀함수를 이용하는 방식이 있는데, 재귀 함수로 푸는것이 이해하기 쉽다. 아래 코드는 stack 과 재귀 함수를 이용하여 문제를 풀었다. # -*- coding: utf-8 -..

본 문제의 저작권은 프로그래머스(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)을 비교한다. 같다: 인덱스를 반환한다. 목표값이 중간값보다 작다: 중간값의 인덱스보다 작은 왼쪽에서 다시 찾는다. (오른쪽은 버려도된다..

파이썬 정렬 메소드 파이썬에서는 정렬을 할때 sort() 와 sorted() 메소드를 사용한다. sort() sort() 메소드는 리스트를 오른차순으로 정렬해준다. >>> data = [3, 6, 12, 7, 10, 99, 23, 5, 9] >>> data.sort() >>> data [3, 5, 6, 7, 9, 10, 12, 23, 99] sorted() sorted() 메소드는 오름차순으로 정렬 후 새로운 리스트를 반환해준다. >>> data = [3, 6, 12, 7, 10, 99, 23, 5, 9] >>> sorted(data) [3, 5, 6, 7, 9, 10, 12, 23, 99] 파이썬에서는 어떤 정렬 알고리즘을 사용할까? 흔히 알고리즘을 배우면 아래 5가지 정렬 알고리즘을 배운다. 선택 정..