IT 정리용 블로그!

[7-1] Q : 순차 탐색(Sequential Search)을 구현해라. A :순차 탐색은 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다. 순차 탐색은 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N)이다. Line 4에서 list의 인덱스는 0부터 시작하기에 몇 번째 원소인지를 알려주기 위해 1을 더해 리턴한다. [7-2] Q : 재귀 함수를 이용해 이진 탐색(Binary Search)을 구현해라. A :이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용 가능하다. 시작점, 끝점을 기준으로 가운데에 있는 중간점을 잡는다. 중간점이 실수일 때는 소수점 이하를 버려 정수로 만든다(line 5). 중간점의 원소(..

[6-1] Q : 선택 정렬(Selection Sort)을 구현해라. A :선택 정렬은 array의 모든 원소들 중 가장 작은 것을 index 0으로 보내고, index가 1보다 큰 것들 중 가장 작은 값을 index 1로 보낸다. 그 뒤 index 2에도 마찬가지로 실행한다. 가장 작은 데이터를 앞으로 보내는 과정을 N번 반복하는 것이다. 선택 정렬은 N + N-1 + N-2 + ... 2번 연산을 진행하는데, 근사치로 N(N-1)/2번 연산을 실행하므로 O(N^2)회 연산을 수행한다. 때문에 알고리즘 문제풀이에 사용하기에는 느린 편이다. Line 8에서 파이썬의 swap이 나타난다. 다른 언어들과 달리, 파이썬에서는 line 8처럼 쓰면 두 값이 바뀐다. [6-2] Q : 삽입 정렬(Insertion..

[5-1] Q : 스택을 구현해라. A :stack은 별도의 라이브러리를 이용할 필요 없이 list에 append()와 pop() 함수를 이용해 구현한다. line 7과 10에서는 직전에 append된 7과 4가 출력되는 last in first out(first in last out) 특징을 확인할 수 있다. [5-2] Q : 큐를 구현해라. A :파이썬에서 큐는 collection 모듈의 deque 자료구조를 사용한다. Deque(Double Ended Queue)는 양 끝에서 삽입과 삭제를 할 수 있어야 하므로 양방향 연결리스트(dobuly linked list)로 구현되어 있다. 오른쪽에 삽입할 때는 append(), 왼쪽에 삽입할 때에는 appendleft(), 중간에 삽입할 때에는 insert..

[4-1] Q : 1x1 크기의 정사각형 블록으로 이루어진 NxN 크기의 지도가 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가가 지도 위를 여행하는데, 시작 좌표는 항상 (1,1)이다. 여행가가 이동할 계획서가 있다. 하나의 줄에 띄어쓰기를 하여 L,R,U,D의 문자들이 적혀 있다. 여행가가 NxN 크기의 지도를 벗어나려는 움직임은 무시된다. 첫 줄에는 N이 주어지고, 둘째 줄에는 A가 이동할 계획서의 내용이 주어진다. 여행가가 최종적으로 도착할 지점의 좌표를 공백으로 구분해 출력해라. A :사실 line 2에서 move_를 list 형태로 만들 필요 없이 input().split()만 해주면 알아서 move_에 list 형태로 들어간다. str 형태..

[3-1] Q : 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 거슬러줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구해라. A : 동전의 수를 가장 적게 주려면 가장 큰 화폐단위(500원)부터 거슬러 주면 된다. 여기서 그리디 알고리즘이 사용된다. 그리디 알고리즘은 항상 최적의 해를 보장하지 않는다. 따라서 그리디 알고리즘으로 문제를 풀었을 경우에는 그 풀이가 정당한지 확인해야 한다. 이 문제의 경우에는 가지고 있는 동전 중 큰 단위의 동전은 항상 더 작은 단위의 배수이기 때문이다. 때문에, 항상 10원짜리 30개, 50원짜리 6개를 주는 것보다 100원짜리 3개를 주는 것이 낫다. 위 코드의 경우, 동전의 수가 K라면 시간복잡도는 O(K..