ComDoc ComDoc

우리가 흔히 사용하는 방식은 중위 표기법(infix notation)인데, 연산 기호를 중간에 넣습니다. ex) 1 + 2 연산기호가 앞에 오는 전위 표기법(prefix notation)도 있고.. ex) + 1 2 연산기호가 뒤에 오는 후위 표기법(postfix notation)도 있습니다.. ex) 1 2 + 전위 표기법은 폴란드식 표기법(PN, Polish Notation), 후위 표기법은 역 폴란드식 표기법(RPN, Reverse-Polish Notation)이라고도 하는데요. 이런 표기법들은 괄호를 쓸 필요가 없고, 또 스택으로 구현할 수 있습니다. 자세한 건 글 마지막 링크들을 참고하시고요. 간단하게 느낌만 살펴보도록 하겠습니다. 후위표기법 : 5 6 + 7 * 2 / 중위표기법 : ((5 +..

수식에 열고 닫는 괄호 쌍을 체크할 때도 스택을 이용할 수 있습니다. 수식을 인자로 받아 수식에 괄호가 빠졌을 때 나 홀로 있는 괄호의 위치를 반환하는 함수를 구현해 봅시다. 예를 들자면 '2.4 + 23/12 + (3.141592 * .21' 코딩해 보죠.. def check_bracket(text): stack = [] for i in range(len(text)): if text[i] == '(': stack.append(i) elif text[i] == ')': stack.pop() return stack print(check_bracket('2.4 + 23/12 + (3.141592 * .21')) 간단히 개념만 잡는 정도로 작성해 보았습니다. 위 코드의 경우 문제가 있습니다. 주어진 문자열에서..

프로그래밍 언어를 구현할 때도 스택을 사용합니다. 좀 더 자세히 말씀드리면 함수의 호출은 스택으로 구현됩니다만, 이 부분을 자세히 설명드리는 것은 이 글의 범위를 벗어난 것 같습니다. 혹시 이 부분에 대해 궁금하신 분은 다음 사이트를 참고하시기 바랍니다. https://dojang.io/mod/page/view.php?id=1376 스택으로 재귀 구현 흉내 내기를 해보겠습니다. 먼저 재귀의 가장 흔한 예인 팩토리얼을 만들어 봅시다. 5 팩토리얼은 다음과 같죠.. 5! = 5*4*3*2*1 = 120 코딩을 합니다. # 팩토리얼 2019-06-01 def factorial(n): if n == 1: return n return n*factorial(n-1) print(factorial(5)) # 120 리..

앞으로 읽으나 뒤로 읽으나 같은 단어, 구절, 숫자 등을 회문(palindrome)이라고 합니다. 스택은 '(깔끔하게 정돈하여) 쌓은 무더기'라는 뜻입니다. (아래) 먼저 쌓은 것부터 꺼낼 수 없고 (가장 위) 마지막 쌓은 것부터 꺼낼 수 있습니다. 파이썬에서는 list의 append 메소드가 push와 같고 list에는 pop 메소드도 있으니 list를 바로 쓰시면 됩니다. 스택을 이용해서 넣었다 빼면서 원문과 같은 지 확인하면 됩니다. def is_palindrome(word): s = [] for i in range(len(word)): s.append(word[i]) for i in range(len(word)): if s.pop() != word[i]: return False return Tru..

십진수의 진법 변환 (기수 범위: 2~9) def change_base(num, base): stack = [] while num > 0: stack.append(num % base) num = num // base result = '' for _ in range(len(stack)): result += str(stack.pop()) return result print(change_base(7, 2)) # 111 * (언패킹 등에서) 사용하지 않는 변수는 _ 을 사용하는 관례가 있습니다. 스택에 연연하지 않고 파이썬스럽게 코딩한다면... 이런 느낌? def change_base(num, base): stack = [] while num > 0: stack.append(num % base) num = nu..

스택(Stack ADT) 스택(stack)을 영한사전에서 찾아보면 '(보통 깔끔하게 정돈된) 무더기'라고 되어 있습니다. (차곡차곡) 물건을 쌓아 올리면 아래 것은 빼기가 어렵죠? 마지막에 쌓은, 제일 위의 것을 먼저 꺼내 쓸 수 밖에 없습니다. 이를 LIFO(= last-in, first-out = 후입 선출) 또는 FILO(= first-in, last-out = 선입 후출)라고 하며, 이와 같은 형태의 자료 구조를 스택이라고 합니다. 스택에 자료를 집어넣는(=쌓아주는) 것은 push, 스택에서 자료를 꺼내는 것은 pop이라고 합니다. 리스트와 클래스를 이용해서 스택 추상 자료형을 만들어 보겠습니다. class Stack: def __init__(self): self.data = [] def push..

요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation) 전설에 의하면 1세기에 유대인 로마 전쟁 당시 역사가 플라비우스 요세푸스와 40명의 유대인이 로마 군인에게 붙잡힐 위기에 처했다. 유대인 병사들은 포로로 잡히느니 죽음을 택하기로 했다. 사람으로 원을 만든 다음 사람이 남지 않을 때까지 매 세번째 병사를 죽여나가기로 작전을 세웠다. 요세푸스와 다른 한명은 일찍 죽음을 당하는 위치에 서고 싶지 않아 어디에 서야 최후까지 생존할 수 있을 지 빨리 계산해야 했다. n명의 사람이 원을 만들고 매 m번째 사람을 죽이는 프로그램을 구현하시오. 그리고 마지막으로 남을 두 사람을 계산하시오. 리스트 먼저 리스트를 이용해 보겠습니다. (문제를 보고 처음 떠오른 거라...

원형(순환형) 연결 리스트에서는 단방향 연결 리스트와 같은 노드를 사용합니다. 단방향과 다른 점은 원형 연결 리스트에서는 생성시 헤드의 링크(next 프로퍼티)가 자기 자신을 가리킨다는 것입니다. 여기에 삽입을 하면 최종적으로 마지막 요소의 링크가 헤드를 가리키게 되죠. 복잡한 양방향 연결 리스트를 만들지 않고 간단하게 역방향 탐색을 할 수 있다는 것이 원형 연결 리스트의 장점입니다. 원형 연결 리스트에서는 노드의 끝을 지나 계속 탐색하면 결국 역방향에 있는 노드로 이동할 수 있습니다. 다만 이렇게 수정할 경우 show 함수가 무한 루프에 빠집니다. show 함수의 조건문을 head에 다다르기 전에 멈추도록 수정해야 합니다. class Node: def __init__(self, element): sel..