CS/Data Structure & Algorithm 13

공주 구하기 (덱, 큐 )

큐 관련해서 쉬운 문제인데, 분명 유명한 테이블 문제인데 이름이 생각이 안난다... 무슨... 용어가 있는데 이름이 생각이 안나서 너무 괴로운 문제였다. 여튼 문제 풀이는 간단하다. 명수만큼 덱에 넣어준 뒤, while 문을 덱 안에 마지막 한 사람만이 남을 때 까지 돌려준다. 그리고 경우를 cnt로 추적하며, 이 cnt가 K의 배수가 될 때는 이를 리스트에서 삭제시키고, (popleft()) 그 외 나머지 경우네는 popleft()를 해서 그대로 다시 오른쪽에 append 시키고, 이 반복문을 계속하다보면 최후의 왕자가 남게된다. import sysfrom collections import deque#sys.stdin=open("input.txt", 'rt')N, K = map(int, input()...

가장 큰 수 (스택)

먼저 처음 포인트는 이 숫자들을 리스트에 받아줘야하는데, 띄워쓰기로 구분되어있지 않기 때문에 항상 받아왔던 방식인 map(int, input().split()) 방식으로 받을 수가 없다. 그래서 str로 받아서 이것들을 list에 넣는뒤, 다시 int형으로 변환시켜준다.  b_num, delete = map(int, input().split())nums = []for i in range(len(str(b_num))):    nums.append(str(b_num)[i])nums = list(map(int, nums)) 그 후, 새로운 리스트를 만들어 nums에 있는 수들을 끄집어 내며 하나씩 비교해보고, 새로운 리스트에 들어있는 수보다 nums[0]에 들어있는 수가 크다면 이를 빼주고, 삭제할 수 있는 ..

역수열 (그리디 알고리즘)

원래 수열을 [0] * N 으로 초기화 시킨 뒤, 정렬이 되어있다 생각하고 1부터 경우를 생각하며, 원래 수열의 0을 역수열의 원소만큼 카운팅 하면 간단한 문제이다. 이중반복문을 돌리면서 i -> 역수열의 인덱스번호  j-> 원수열의 0을 카운팅하기 위한 인덱스 번호라 생각하고 cnt로 0을 카운팅하면서 어차피 오름차순으로 정렬되어 있기에, 앞에 더 작은 숫자가 나와있는건 신경쓰않고 오로지 0만 카운팅 해서, cnt 와 역수열의 원소값이 같아지면 그때의 i+1 값을 원수열에 넣어주고 다음 반복문을 통해 다음값을 카운팅 해주면 된다. import sys#sys.stdin=open("input.txt", 'rt')N = int(input())rev = list(map(int, input().split()))..

결정 알고리즘 (랜선 자르기)

결정 알고리즘을 이용할 때는 이분탐색을 이용하고, 문제에서 보통 답의 범위를 알 수 있다.  알고리즘은 다음과 같다. 주어진 수들 중에서 max를 찾는다. 그럼 범위는 1 ~ MAX의 수가 될 것이고, 이분탐색으로 중간값을 찾아 답이 되는지 찾아본다. 답이 되는지 찾아보기 위해, Count 함수를 만든다. 이 함수는 주어진 숫자들을 파라미터로 받은 값들로 모두 나누었을 때 그 합을 반환한다. 반환한 값과 K 값을 비교하여, 반환 값이 더 작으면 답이 될 수 없으므로 중간값 기준 더 작은 값, 즉 왼쪽을 탐색해야한다. 반환값이 K값보다 크거나 같을 때는 오른쪽을 탐색한다. 그렇게 while문을 반복하며 lt  이분탐색 기반의 가장 기본적인 알고리즘이며, 기본인 만큼 많이 쓰이고 중요한 알고리즘이니, 확실하..

탐색 & 시뮬레이션 [수토쿠 검사] (죽음의 4중 포문...)

코테 연습을 위해 알고리즘 복습을 하며 탐색의 기본격이라 할 수 있는 수토쿠 검사  알고리즘을 풀어보았다. 구간 검사를 위해 4중 포문을 돌려야하는 번거로움이 있지만, 알고리즘 자체는 그리 어렵지 않다.      3가지에 대한 검사를 해야한다.  1) 가로행에 1 ~ 9 가 다 있는지,2) 세로행에 1 ~ 9 가 다 있는지,3) 3*3 총 9개의 구간에 1 ~ 9 가 다 있는지, 먼저 9*9 총 81개의 숫자를 리스트(sudo) 에 담아준다.  sudo = [list(map(int, input().split())) for _ in range(9)] 그 뒤 check 라는 검사 함수를 만들어준다.  check 함수 안에는 1) 2) 3)을 차례로 검사해주는데 만약 거짓이 있는 순간 바로 False를 ret..

한방향 연결리스트 및 연산(삽입, 삭제, 탐색)

class Node: #기본 노드 클래스 def __init__(self, key=None): self.key = key self.next = None def __str__(self): #객체를 호출하면 이 함수가 호출된다. return str(self.key) 한방향 연결리스트 (SinglyLinkedList) => 노드들이 한 방향으로 연결된 리스트 head node와 tail 노드가 있고, 특정 key값을 찾는데 걸리는 시간은 가장 앞인 head노드로부터, 떨어진 거리의 시간과 같다. 삽입연산(pushFront(), pushBack()) / 삭제연산(popFront(), popBack()) / 탐색연산 / 제거연산 이 있다. 그렇다면, 이 한방향 연결리스트를 구현해보자 class SinglyLink..

연결리스트 (Linked List) 기본개념

A라는 [3, 9, -1, 2, 5] 배열이 있을 때 중간에 값을 insert 하려면 데이터값들이 밀리기 때문에 많은 시간이 걸리며 Worst case의 경우 n만큼의 시간이 걸려 O(n)의 시간복잡도를 가진다. 연결리스트는 순차적 자료구조로, 이런 경우 더 효율적인 연산을 가능하게 해준다. 가장 기본적인 연결리스트의 구조이며, 각 노드들은 (data값(key값), link(next노드를 가르키는 값)) 두가지 정보를 담고있다. 그리고 가장 앞의 노드는 head 노드이며, 마지막 노드가 가르키는 값은 NULL값이다. 이제 앞에서 O(n)의 시간이 걸렸던 insert 연산을 다시 해보자. B와 C 사이에 K라는 값을 대입하고자 할때, K값을 갖는 노드를 하나 만들어주고, B노드를 next를 K노드로, K노..

큐를 활용한 문제 [Josephus problem]

Jesephus problem은 이번에 배운 큐를 이용하여 풀 수 있는 대표적인 문제다. Joesphus(n, k) => n 총 인원 k => 몇번째 사람마다 제외할것인가 가령 Joesphus(5, 2)일때 5명 중 2번째 마다 제외해서 마지막에 누가 남는지 알아보는 것이다. 이때 [1, 2, 3, 4, 5] 큐를 만들어서 enqueue와 dequeue를 이용하여 풀어보자 [1, 2, 3, 4, 5] 1은 dequeue하고 바로 enqueue => [1, 2, 3, 4, 5, 1] 2는 해당되기 때문에 dequeue만 실행 => [1, 2, 3, 4, 5, 1] 3은 dequeue하고 바로 enqueue => [1, 2, 3, 4, 5, 1, 3] 4는 해당되기 때문에 dequeue만 실행 => [1, ..

Queue (FIFO, 순차적자료구조)

순차적 자료 구조 중 Last In First Out에 대표적으로 Stack이 있었다면, First In First Out 자료 구조에는 큐(queue)가 있다. 먼저 들어온 구조가 리스트 front에 자리잡고 스택과 같이 차곡차곡 쌓이다가 pop될때 (큐에서는 dequeue 라고한다), front에 있는 자료가 나가는 구조이다. stack에서 배웠던 push가 enqueue, pop이 dequeue로 표현된다. 이 큐를 파이썬을 사용하여 클래스로 구현하면 다음과 같다. class Queue: def __init__(self): self.items = [] self.front_index = 0 def enqueue(self, value): #push와 같은 역할 self.items.append(value..

Infix(중위표기법) -> Postfix(후위표기법), 그리고 스택 계산

중위표기법(Infix) 이란, 우리가 보통 연산을 할때 쓰는 방법이며, 피연산자(operand) 사이에 연산자(+,-,*,/)가 존재한다. 2 + 3 * 5 라는 식이 있을 때 '2', '3', '5' => 피연산자이고, '+', '*' 는 연산자, 그리고 이 모든것을 포함하여 토큰이라 부른다. 연사자도 두가지로 나뉜다. 이항연산자(항을 2개 요구) 2+3 에서 '+'는 이항연산자 라 할 수 있다. 단항연산자(항을 1개 요구) +6 에서 '+'는 양수임을 나타내는 연산자이며, 단항연산자이다. 후위표기법(Postfix) 이란 연산자가 피연산자 뒤에 오는 수식이다. 컴파일러가 사용하는 방식으로 스택을 사용하는 방법에 많이 등장한다. 그럼 앞의 2 + 3 * 5 수식을 Infix->postfix로 변환해보자...