Study Blog

정렬이란? - 이름, 학번, 학점 등의 특정 키를 기준으로 대소 관계에 따라 데이터의 집합을 일정한 순서로 바꾸어서 늘어놓는 작업이다. - 값이 작은 데이터부터 앞쪽에 늘어놓는 것: 오름차순(ascending order) 예) a = [1, 2, 3, 4, 5] - 값이 큰 데이터부터 앞쪽에 늘어놓는 것: 내림차순(descending order) 예) a = [5, 4, 3, 2, 1] - 정렬 알고리즘은 시간 복잡도에 따라 성능이 좌우되고, 성능이 좋은 알고리즘일수록 구현 방법이 어려워진다. 정렬 알고리즘의 시간복잡도 - O(n²): 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬(최악 O(n²), 최선O(n log n)) - O(n log n): 병합 정렬, 퀵 정렬, 힙 정렬 - O(n): 도수 정렬..

8퀸 문제란? - 재귀 알고리즘을 설명할 때 자주 나오는 예제로, 19세기 수학자인 '카를 F. 가우스'가 오답을 발표한 것으로 유명. 8퀸 문제의 조건 - 8개의 퀸이 서로 공격하여 잡을 수 없도록 8 x 8 체스판에 배치하라. 이 문제는 총 92가지 해결 방법을 얻을 수 있고, 아래 그림은 92가지 해결 방법 중 한가지이다. 이 문제를 해결하는 데 사용하는 문제 풀이 방법은 분기작업(branching, 차례대로 가지가 뻗어 나가듯이 배치 조합을 열거하는 방법)과 분할 정복법(분할 해결법, divide and conquer, 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법)을 이용하여 해결할 수 있다. 한 가지 주의할 점은 문제를 분할할 때 작은 풀이법에서 원래의..

AWS에서 우분투 리눅스를 설치하고, 우분투 리눅스에 탄력적 IP를 할당하고 가상호스트를 설정하여 브라우저 주소창에 해당 IP를 넣고 접속했을 때 설정해둔 사이트가 나타나게끔 할 수 있다. 가상호스트란? 가상 호스트 서버를 이용하여 하나의 도메인 안에서 여러 개의 홈페이지를 제공해주는 서비스이다. AWS 우분투 CLI 화면에서 가상 호스트를 설정하는 순서는 다음과 같다. 1. sudo apt-get upgrade && apt-get update 명령어를 입력하여 변경 사항을 적용해준다. 2. sudo apt-get install nginx 명령어를 입력하여 nginx를 설치한다. 3. cd /var/www 명령어를 입력하여 최상위 디렉토리 아래 var/www/ 디렉토리로 이동해준다. 4. 이곳에서 ls ..

하노이의 탑이란? - 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키며 기둥 3개를 이용해서 원반을 옮김. 하노이의 탑 조건 (1) 크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작(작은 원반이 위에, 큰 원반이 아래에 위치) (2) 이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮김 (3) 원반은 1개씩 옮길 수 있으며, 큰 원반은 작은 원반 위에 쌓을 수 없음 그룹으로 묶어서 옮기기 - 원반이 3개일 때 - 원반이 2개일 때 - 원반이 4개일 때 원반을 옮기는 과정을 코드로 구현 def move(no: int, x: int, y: int) -> None: # 원반 no개를 x기둥에서 y기둥으로 옮김 if no > 1: move(no - 1, x, 6 - x - y) p..

순수한 재귀란? - 재귀 호출을 여러 번 실행하는 함수 def recur(n: int) -> int: if n > 0: recur(n - 1) print(n) recur(n - 2) x = int(input("정숫값을 입력하세요.: ")) recur(x) 실행 결과 정숫값을 입력하세요.: 4 1 2 3 1 4 1 2 - 순수한 재귀는 위와 같이 실행 과정이 복잡. 매개변수를 4가 아닌 3이나 5라면 어떤 결과를 출력할 지 간단히는 알 수 없음. 하향식 분석과 상향식 분석 위 코드를 하향식 분석(Top-down)방법과 상향식 분석(Bottom-up)방법으로 분석해보자. recur(4)의 실행 과정은 다음과 같다. 1. recur(3)을 실행한다. 2. 4를 출력한다. 3. recur(2)를 실행한다. 위 ..