목록알고리즘 (14)
AI와 데이터 사이언스의 이론과 실전
알고리즘 자료구조 - 카드 백준 2164번
오늘은 마지막 카드를 찾는 문제를 풀어보겠습니다. 해당 문제는 이전에 사용했었던 디큐를 사용하여 풀어야합니다. 문제 자체가 쉽고 간단해서 디큐를 활용하는 방법도 간단합니다. 첫번째 카드는 버린다(pop) 두번째 카드도 최상단에서 제거한다(pop) 두번째 카드를 최하단으로 넣는다(append) 마지막 한장이 남을때까지 반복하면됩니다. 디큐는 최상단의 값과 최하단의 값 둘다 추가 삭제가 가능하고 보통의 리스트보다 속도에 이점이 있습니다. 아래는 디큐를 활용한 해당 코드입니다. from collections import deque li = deque(range(1,int(input())+1)) while True: if(len(li)>1): li.popleft() else: print(*li) break if..
알고리즘 자료구조 - 오큰수 구하기 백준 17298번
오늘은 오큰수 구하기 문제를 풀어보겠습니다. 오큰수는 본인을 기준으로 오른쪽에 있는 본인보다 큰 수를 구하는 것입니다. 아래는 하나하나의 수 마다 대조해서 푸는 방법입니다. n = int(input()) li = list(map(int,input().split())) max_li = max(li) i = 0 while i li[j]: rep += 1 else: for i in range(rep): print(li[j], end =' ') i = j break print('-1', end=' ') 이렇게 하면 답은 맞..
알고리즘 자료구조 - 스택 수열 백준 1874번
해당 문제는 스택을 작성하는 문제입니다. 스택은 후입선출을 기본으로 하고 해당문제는 1부터 n까지의 수를 오름차순으로 정렬한다고 명시되어 있습니다. 때문에 예제2에서 1과 2는 생성되자마자 pop되고 그 다음 5를 입력하는 순간 3,4,5가 생기고 5개 pop되어 [3,4]가 남습니다. 하지만 이때 그다음에 3을 pop하는 것은 후입선출의 기본 원칙인 뒤에 들어온 숫자가 가장 먼저 삭제된다는 것에 위배됨으로 NO가 뜨게됩니다. 해당 코드는 3가지 규칙으로 돌아갑니다 빈 리스트이거나 리스트의 마지막 값이 출력되길 원하는 값보다 작을 경우 PUSH로 출력되길 원하는 값까지 생성후 POP, 이때 값을 생성할때 top보다 큰 수들만 PUSH합니다. top까지는 이미 만들어진 수 임으로 두번 생성하지 않아야합니다..
이번 문제는 백준에 있는 11003번 최솟값 찾기문제입니다. 이 문제는 앞선 포스팅에서 설명한 큐를 사용하여 풀면됩니다. 큐는 선입선출을 기본으로하는 자료구조라고 설명했는데 끝방향으로 기준으로 합니다. 오늘은 양방향을 기준으로 하는 디큐 자료구조를 사용하여 최솟값을 찾아보겠습니다. 이번에 사용할 알고리즘은 순서대로 진행하여 본인을 기준으로 이전의 본인보다 큰 값과 범위를 벗어나는 값을 제거한 상태에서 최솟값을 찾아 출력합니다. 우선 순서대로 반복하는 반복문에서 이번 반복에 해당하는 값보다 큰 값을 모두 삭제합니다. 이렇게 되면 내가 제일 작은 수가 아닌 경우에 제일 작은 값이 항상 왼쪽에 위치하게 됩니다. 왜냐하면 매번 반복하기 때문에 현재값이 보는 디큐는 이전값 기준으로 이전값보다 큰 값은 항상 제거된..