[모두의 알고리즘] 자료구조

자료구조

 

회문찾기(큐와 스택)

 

큐: 줄서기. FIFO(First In First Out)

인큐와 디큐: 인큐는 자료를 집어 넣는 동작이고 디큐는 자료를 빼내는 동작.

 

스택: 접시 꺼내기. LIFO(Last In First Out)

뷔페에서 맨 아래 있는 접시를 꺼내려면 맨 위에 있는 접시부터 하나하나 꺼내야 한다.

푸쉬, 팝: 푸쉬는 스택에 자료를 집어 넣는 동작, 팝은 자료를 빼는 동작

 

큐와 스택은 자료를 일렬로 보관하는 특징이 있다. 리스트를 사용해 큐와 스택을 만들어 볼 수 있다.

 

큐)

qu = [] : 빈 리스트를 만들고

qu.append(x) : 리스트의 맨 뒤에 x를 추가한다

x = qu.pop(0) 리스트의 맨 앞에서 자료를 꺼낸다.

 

스택)

st = [] : 마찬가지로 빈 리스트를 생성

st.append(x) : 리스트 맨 뒤에 자료를 추가

x = st.pop() :리스트의 맨 뒤에서 자료를 꺼낸다.

 

회문찾기 알고리즘은 큐와 스택을 활용해 해결할 수 있다. 큐에서 꺼낸 문자들과 스택에서 꺼낸 문자들이 모두 같다면 그 문장은 회문

• 큐와 스택을 이용하지 않고 회문인지 아닌지 판단할 수 있는 방법을 생각해보자

for문을 사용해 판단할 수 있을 것 같다. 

def palindrome(s):
	lst = []
    
    for x in s:
    	if x.isalpha():
        	lst.append(x.lower())
    for i in range((len(lst)//2)+1):
    	if lst[0+i] == lst[-1-i]:
        	return True
        else:
        	return False

 

돌려보니 결과 확인! 한글도 확인이 되는게 신기했다.책과는 조금 다르지만 이 방법을 적기로 했다.

 

 

동명이인 찾기

딕셔너리를 이용한 동명이인 찾기.

파이썬에서 딕셔너리란 정보를 찾는 기준이 되는 키값과 그 키에 연결된 값의 대응 관계를 저장하는 자료구조이다. 예를 들어 사람과 번호를 대응시켜 딕셔너리로 쉽게 표현할 수 있다. 딕셔너리는 중괄호 { } 를 사용해 만들고, 키값과 키와 연결되는 값을 콜론(:) 으로 연결한다.

d = { “John”: 1, “Jason”: 2, “MIke”: 3}

d[“John”]

>>> 1

d[“Mike”]

>>> 3

 

찾는 키값이 없는 경우 Traceback 오류가 발생한다. 그리고 딕셔너리에서 키로 원하는 값을 찾으려면 리스트와 마찬가지로 대괄호[ ]를 사용한다. 리스트에서는 대괄호 안에 원하는 위치 번호를 넣지만 딕셔너리에서는 대괄호 안에 원하는 키값을 넣는다. 딕셔너리는 키가 중복되지 않으므로 이미 존재하는 키에 새 값을 넣을 경우 새 값으로 덮어써진다.

• 학생 번호와 이름이 주어졌을 때, 학생 번호를 입력하면 그 학생 번호에 해당하는 이름을 돌려주고, 해당하는 학생 번호가 없으면 물음표를 돌려주는 함수를 딕셔너리를 이용해 풀어라.

2번째 줄에 numer가 아닌 number... 

 

 

 

지금까지 인자들을 입력받아 와서 함수를 정의하고 인자를 받는 부분을 채워왔지만, 여기서는 직접 번호를 입력하고 딕셔너리 안에서 찾기 때문에 괄호를 안 채워도 동작한다. 

 

• 해시 테이블: 키와 값을 대응시켜 여러개의 자료를 보관하는 효율성이 높은 자료구조를 얘기하며 자바에서는 해시맵, 파이썬에선 딕셔너리, C++에서는 언오더드맵 이라고 부른다.

 

친구의 친구 찾기(너비 우선 탐색 BFS)

• 모든 친구를 찾는 알고리즘 

• 출력 결과

 

 

• 친밀도를 계산하는 알고리즘 

• 출력 결과

 

 

가짜 동전 찾기

방법 1) 하나씩 비교하기 

 

>>> N = 100 / print(find_fakecoin(0, N-1))을 하게 되면

29 가 나온다. 하나하나 비교하므로 최대 n-1번, O(n)의 계산복잡도를 지닌다.

 

방법 2) 반 씩 그룹으로 나누어 비교하기

1. 동전의 개수를 절반씩 나눈다.
2. 한쪽이 가벼울 경우 해당하는 쪽에 가짜동전이 있음.
3. 가벼운 쪽 동전을 계속 절반씩 나눠서 비교
4. 동전의 개수가 짝수고 양쪽의 무게가 같으면 가짜 동전은 없음
5. 동전의 개수가 홀수인 경우 둘로 나누면 하나가 남음. 하나를 제외하고 두 그룹을 비교
6. 동전의 개수가 홀수로 양쪽 비교 시 무게가 동일하면 나머지 하나가 가짜 동전.
7. 가벼운 쪽 동전을 계속 절반씩 나눠서 비교

 

 

 

최대 수익 알고리즘

방법 1) 가능한 모든 경우 비교하기 (최대, 최솟값 찾기와 같은 방식) 

 

 

방법 2) 한 번 반복으로 최대 수익 찾기 

 

내가 푼 방법은 먼저 제일 작은 값을 찾고 제일 작은 값의 위치 뒤에서 제일 큰 값을 찾은 뒤

그 값의 차를 구한 방법이다.

제일 작은 값의 인덱스를 찾은 후 그 인덱스부터 리스트를 다시 구성해 최대값을 찾는 알고리즘

 

책에서는 첫째 날의 주가를 최저 금액으로 잡고 끝까지 반복하고 계산해 나가는 동안 최저금액과 최대이익을 전부 구해준다. 나처럼 임의의 값을 주고 최저 점을 구해나가는게 아니라 일단 첫 번째 값을 최저로 설정하고 그거보다 작은 값이 나왔을 경우 최저금액을 변경 해나가면서 푼 게 훨씬 직관적이고 논리적이라는 생각이 들었다.