BaekJoon Online Judge 11726: 2Xn 타일링 문제 https://www.acmicpc.net/problem/11726 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 소스코드 n […]
[BaekJoon Online Judge] 1463 – 1로 만들기
BaekJoon Online Judge 1463: 1로 만들기 문제 https://www.acmicpc.net/problem/1463 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 […]
[Algorithm] Merge Sort
Python으로 구현한 Merge Sort 분할정복 (Divide & Conquer) 기법을 이용하여 정렬한다. 주어진 리스트를 원소의 갯수가 1인 리스트가 될 때까지 분할한 뒤 그 리스트들을 다시 합치는 과정에서 원소를 비교하여 정렬을 수행한다. 소스코드 vi sort.py # Merge Sort def sort_merge(arr): if len(arr)<=1: return arr ## Exception ## Divide left = sort_merge(arr[:len(arr)//2]) right = sort_merge(arr[len(arr)//2:]) ## Conquer i,j,k […]
[Linux] How to Upgrade Ubuntu
업데이트 목록 갱신 sudo apt-get update 현재 패키지 업그레이드 sudo apt-get upgrade 신규 업데이트 설치 sudo apt-get dist-upgrade
[Algorithm] Edit Distance
Edit Distance 편집 거리(Edit Distance) 알고리즘에 대해 알아보고 Python으로 Edit Distance 알고리즘을 구현해본다. ‘KITTEN’과 ‘SITTING’ 문자열 비교 편집 거리(Edit Distance)는 어떤 문자열을 다른 문자열로 바꾸기 위해 필요한 연산의 최소 횟수를 뜻한다. 한 문자열에 대해 삽입, 삭제, 변경의 연산을 몇 번에 걸쳐 바꿀 수 있는지를 기준으로 두 비교 대상의 유사도를 판단한다. ‘KITTEN’과 ‘SITTING’을 비교한다고 했을 때, […]
[Python] Memoization을 이용한 Fibonacci
Fibonacci using Memoization Legacy Fibonacci def fibo(n): return n if n < 2 else fibo(n-2) + fibo(n-1) def Main(): number = int(input(“Enter integer: “)) print(fibo(number)) if __name__==’__main__’: Main() Fibonacci using Memoization __fibo_cache = {} def fibo(n): if n in __fibo_cache: return __fibo_cache[n] else: __fibo_cache[n] = n if n < 2 else fibo(n-2) + fibo(n-1) return […]
[Algorithm] Python으로 구현한 sort
[Algorithm] Python으로 구현한 sort Python은 list 자료형에 대해 sort 메소드를 기본적으로 제공하지만 필요에 따라 직접 구현할 필요도 있고, 또 Python 언어와 알고리즘 이해를 위해 작성한다. 오름차순 정렬 list_data.sort() 내림차순 정렬 list_data.sort(reverse=True) Sort Basic 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) 거품 정렬 (Bubble Sort) 퀵 정렬 (Quick Sort) 선택 정렬 (Selection Sort) selection sort는 […]
[Algorithm] BFS
Python으로 구현한 BFS BFS 알고리즘은 Queue 자료구조를 사용한다. 그래프 노드를 순회하는데 최초 노드의 모든 자식 노드들을 먼저 탐색한다. 이후 그 자식 노드들의 자식 노드를 모두 탐색하는 과정을 반복한다. 소스코드 #!/bin/python graph = {‘A’: [‘B’, ‘C’, ‘D’], ‘B’: [‘A’, ‘E’, ‘F’], ‘C’: [‘A’, ‘G’], ‘D’: [‘A’, ‘H’, ‘I’], ‘E’: [‘B’], ‘F’: [‘B’, ‘J’], ‘G’: [‘C’], ‘H’: […]
[Algorithm] DFS
Python으로 구현한 DFS DFS 알고리즘은 Stack 자료구조를 사용한다. 그래프 노드를 순회하는데 leaf 노드인 순간까지 앞만 보고 방문한다. 만약 leaf 노드를 만나게 되면, 직전의 분기점으로 돌아가 다시 leaf 노드를 만날 때 까지 방문한다. 소스코드 #!/bin/python graph = {‘A’: [‘B’, ‘C’, ‘D’], ‘B’: [‘A’, ‘E’, ‘F’], ‘C’: [‘A’, ‘G’], ‘D’: [‘A’, ‘H’, ‘I’], ‘E’: [‘B’], ‘F’: [‘B’, […]
[Python] list, append vs. extend
Append vs. Extend Append append는 입력된 object를 list의 맨 뒤에 추가 x = [1,2,3] y = [4,5] x.append(y) print(x) [1, 2, 3, [4, 5]] Extend extend는 iterable object(list, tuple, dict)의 원소를 list의 맨 뒤에 순서대로 추가 x = [1,2,3] y = [4,5] x.extend(y) print(x) [1, 2, 3, 4, 5]