30 May 2017
|
알고리즘
프로그래밍
문제출처
예전에 2시간을 고민하고도 풀지 못했던 문제였다.
한달이 지나고 나서 다시 풀어보았는데,
시간복잡도 O(N^2)로 풀었다가 시간복잡도 O(N)으로 성능 개선하는데 성공했다. 너무 뿌듯하다!! :)
문제
A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.
You are given a zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.
The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.
For example, you are given integer X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.
Write a function:
def solution(X, A)
that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.
If the frog is never able to jump to the other side of the river, the function should return −1.
For example, given X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
the function should return 6, as explained above.
Assume that:
N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).
풀이코드
첫번째 시도
- 시간복잡도 : O(N ** 2)
- for loop 안에서 A in B 검색을 사용해서 O(N**2) 시간복잡도
def solution(X, A):
check = [False] * X
for idx, val in enumerate(A):
check[val-1] = True
if not False in check:
return idx
return -1
두번째 시도
- 시간복잡도 : O(N)
- A in B 검색을 사용하지 않기 위해서 별도의 check_sum 변수를 활용
def solution(X, A):
check = [0] * X
check_sum = 0
for i in range(len(A)):
if check[A[i]-1] == 0:
check[A[i]-1] = 1
check_sum += 1
if check_sum == X:
return i
return -1
28 May 2017
|
기본 알고리즘
알고리즘
알고리즘 이란 어떤 값을 입력으로 받아 원하는 값으로 출력하는 잘 정의된 계산 절차 를 말한다.
따라서 알고리즘은 어떤 입력을 어떤 출력으로 변환하는 일련의 계산 과정이라 할 수 있다.
자료구조
자료구조 란 데이터에 편리하게 접근하고, 변경하기 위해서 데이터를 저장하거나 조직하는 방법 을 말한다.
모든 목적에 맞는 자료구조는 없다. 따라서 각 자료구조가 갖는 장점과 한계를 잘 아는 것이 중요하다.
자료구조의 미션 : 메모리의 효율적인 사용
- 컴퓨터에는 3가지 중요한 부품이 존재하며 다음과 같은 특성을 가진다.
- CPU : 중앙정보처리장치, 레지스터, 데이터를 연산/처리하는 가장 중요한 부분, 아주 빠름 (기억 떠올리기)
- 메모리 : RAM(Random Access Memory), CPU에서 직접 접근이 가능, 사용자가 자유롭게 내용을 읽고 쓰고 지울 수 있다. 휘발성 기억장치, 빠름 (책에서 특정한 내용 찾아 읽기)
- 스토리지 : HDD, SSD, 비휘발성 기억장치, 용량이 아주 크지만 느림 (지구를 한바퀴 돌아서 찾기)
- 상기와 같은 이유로 데이터는 기본적으로 스토리지에 저장된다.
- 하지만 스토리지는 매우 느리기 때문에 CPU와 함께 일하기에는 속도면에서 부족하다.
- 따라서 어떤 프로그램을 실행하면 해당 프로그램과 데이터는 메모리로 옮겨진다.
- CPU는 메모리에 로드된 데이터를 이용해서 여러가지 일을 하게 된다.
- 그러므로 실행속도를 결정하는 것은 대체로
메모리 이며, 자료구조를 배우는 이유는 메모리의 효율적인 사용 이라고 할 수 있다.
정렬
정렬은 아래와 같은 이유로 알고리즘 연구에서 가장 기본적인 문제로 여겨지고 있다.
- 정보를 정렬하는 것 자체가 필요한 응용 분야가 있다. (ex. 은행의 고객 청구서)
- 정렬을 핵심 서브 루틴으로 사용하는 알고리즘이 많다. (ex. 바이너리 서치)
- 정렬은 역사가 길고, 기술도 풍부하다. 역사가 긴 정렬 알고리즘에는 중요한 기술이 포함되어 있다.
- 정렬 알고리즘 구현시 여러 공학적 논쟁점이 나타난다. (캐시와 가상 메모리 등 메모리 계층구조)
힙정렬과 우선순위 큐
힙은 데이터에서 최대값 (혹은 최소값)을 빠르게 찾아내도록 만들어진 자료구조 이다.
힙은 완전이진트리에 기반한 자료구조로, 부모노드와 자식노드의 대소관계에 따라 최소힙 / 최대힙으로 구분된다.
(힙이란 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나, 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조)
힙정렬
- 힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서,
내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
- 힙 정렬이 가장 유용한 경우는, 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때이다.
- 힙 정렬은 훌륭한 알고리즘이지만 퀵정렬이 일반적으로 더 빠르다. - 시간복잡도 O(n log n)
- 하지만 힙은 그 자체로 대단히 쓸만한 자료구조이며, 대표적으로 우선순위 큐 구현시에 힙이 사용된다.
우선순위 큐
- 우선순위를 가진 항목들을 저장하는 큐, 입력순서와 상관없이 우선순위가 높은 데이터가 가장 먼저 처리된다.
- 선입선출 개념에서 약간 변형을 한것으로 나중에 들어왔지만, 먼저 처리해야 하는 자료가 발생할 경우에 필요로 한다. 이러한 판단은 어떤 상황을 회피하거나, 우선 순위를 두어야 하는 상황에서 사용한다.
- 활용예시
- OS에서 프로세스 스케줄링에 우선순위 큐를 활용할 수 있다.
- 최대 우선순위 큐의 응용분야 중 하나는 공유 컴퓨터에서 작업 순서를 계획하는 것이다. 최대 우선순위 큐는 실행할 작업과 상대 우선순위를 계속 기억하고 있다. 한 작업이 끝나거나 중단될 때, Extract-max를 이용하여 대기중인 작업 중 가장 우선순위가 높은 작업을 선택한다. 새로운 작업은 insert를 사용하여 큐에 새로 들어갈 수 있다.
기본 자료구조
스택과 큐
스택과 큐는 삭제 연산에 의해 집합에서 삭제되는 원소가 미리 제한된 동적집합이다.
(삽입과 삭제의 위치와 방법이 제한된 유한 순서 리스트)
스택
- 스택 에서는 가장 최근에 삽입된 원소가 삭제된다. 스택은 후입선출(LIFO) 정책을 구현한 것이다.
- 스택에서 삽입 연산은 Push, 삭제 연산은 Pop이라 불린다.
- 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며, 스택이 넘치는 경우 stack overflow 라고 한다.
- 활용예시 : 후입선출(LIFO)의 특징을 활용하여 여러 분야에서 활용 가능하다.
- 웹 브라우저 방문기록 (뒤로가기)
- 실행취소 (undo)
- 역순 문자열 만들기
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
- 후위표기법 계산
큐
- 큐 에서는 집합에서 가장 오랜 시간 존재했던 원소를 삭제한다. 큐는 선입선출(FIFO) 정책을 구현한 것이다.
- 큐에서 삽입 연산은 Enqueue, 삭제연산은 Dequeue라 한다.
- 스택에서는 원소의 삽입, 삭제가 스택의 한 끝에서 이루어지고, 큐에서는 원소의 삽입, 삭제가 큐의 서로 다른 쪽 끝에서 이루어진다.
- 양방향 큐 (deque) - 데크 는 원소의 삽입, 삭제가 양쪽 방향에서 이루어진다.
(큐와 스택을 합친 것으로 선입선출/후입선출의 복합적인 성격이 필요한 경우에 사용)
- 활용예시 :선입선출(FIFO)의 특징을 활용한 활용예시
- 우선순위가 같은 작업 예약 (인쇄 대기열)
- 선입선출이 필요한 대기열 (티켓 카운터)
- 콜센터 고객 대기시간
해시 테이블
- 해시 테이블은 사전을 구현하는 가장 효율적인 자료구조이다.
- 이론적으로는 해시 테이블에서 원소를 찾는 것이 연결 리스트에서 원소를 찾는 것 (O(n)) 만큼 오래 걸릴 수 있지만, 실제 해싱은 성능이 탁월하다.
- 일반적으로 해시 테이블에서 원소를 찾는 데 걸리는 수행시간은 O(1)이다.
- 해시 테이블은 단순한 표현인 배열을 일반화 한 것이다.
- 일반적인 배열에 대한 직접 번지화 방법은 배열의 임의의 위치를 O(1)안에 접근하게 하는 효율적인 방법이다.
20 May 2017
|
알고리즘
프로그래밍
문제
2016년 1월 1일은 금요일입니다. 2016년 A월 B일은 무슨 요일일까요?
두 수 A,B를 입력받아 A월 B일이 무슨 요일인지 출력하는 getDayName 함수를 완성하세요.
요일의 이름은 일요일부터 토요일까지 각각
SUN,MON,TUE,WED,THU,FRI,SAT
를 출력해주면 됩니다.
예를 들어 A=5, B=24가 입력된다면 5월 24일은 화요일이므로 TUE를 반환하면 됩니다.
풀이코드
def getDayName(A,B):
days=["FRI","SAT","SUN","MON","TUE","WED","THU"]
months=[31,29,31,30,31,30,31,31,30,31,30,31]
day_total = sum(day_num[:A-1])+B
return day_list[(day_total % 7)-1]
초보몽키의 개발공부로그