학습 노트/알고리즘 (Python) 7

Stack #2

서론 이전에 정리했던 Stack의 구조와 동작 방식을 이해하고, 문제를 풀며 이를 응용해 본다. 본론 Q1 스택에 push 되는 값들이 오름차 수열이 되는지를 판단해, 불가하면 'NO'를 가능하다면 작업의 순서를 push는 '+'로 pop은 '-'로 출력하도록 하면 된다. Q1_Python Stack class Stack2(): class Empty(Exception): pass def __init__(self): self.stk = [] def is_empty(self) -> bool: return not self.stk def push(self, val): self.stk.append(val) def pop(self): if self.is_empty(): raise Stack2.Empty return..

Stack #1

Stack 구조 Stack은 기본적으로 위와 같이 출구와 입구가 하나인 구덩이의 모습을 한다. 폰 스택(phone stack) 놀이와 같이 바닥에 깔려 있는 내 전화에서 벨이 울린다고 위에 있는 다른 전화를 건들지 않고 내 것만 쏙 빼서 확인할 수 없다. Stack도 마찬가지이다. 가령 index 4에 접근하기 위해서는 7, 6, 5를 순서대로 접근한 후에야 4에 접근할 수 있다. 이러한 특징 때문에 Stack을 LIFO(Last In First Out/후입 선출) 구조라고 정의하기도 한다. Pointer Stack에 현재 저장돼 있는 데이터의 수를 나타낸다. 고정길이 스택의 경우 Pointer

선형 데이터 구조와 탐색

서론 선형 데이터 구조 자료의 순서를 유일하게 결정할 수 이쓴 구조를 말 한다. 수학적으로 n 번째 자료를 탐색한 다음 n + 1 번째로 탐색할 자료가 유일한 구조다. 시각적으로는 위와 같다. 왼쪽이 n 다음 n + 1 이 유일하므로 선형구조이고, 오른쪽이 n 다음 n + 1 이 복수이므로 비선형구조이다. 형태에서 느껴지듯 주로 리스트와 배열이 이에 해당하고, 조금 더 확장하면 위와 같이 다차원의 배열과 리스트도 선형구조에 포함된다. 본론 선형 데이터의 탐색 이러한 선형구조의 데이터를 탐색하는 방법에는 크게 두 가지 방식이 있다. 순차탐색 (Linear Search) 첫번째 자료부터 마지막 자료까지 순차적으로 탐색하는 방식으로, 최종적으로 자료의 수 만큼 탐색하게 된다. 따라서 계산량은 O(n) 이 된다..

Q1. 방 배정 하기

서론 파이썬 문법을 마무리 한 날 남은 시간 동안 문제를 한 번 풀어보기로 했다. 문제는 군 복무 중이던 시절 남는 시간에 공부라도 해보자 해서 구해뒀던 한국정보올림피아드 초등부 문제로, 지금은 주관이 바뀐 탓인지 홈페이지에서 구할 수가 없다. C언어는 1학년때 배웠었고, 입대한 건 2학년이 끝난 후였고, 공부를 시작한 건 상병이 다 돼서였으니 이미 기억의 저편으로 사라져 버린 언어에 대한 지식과 손 코딩의 한계로 딱히 제대로 건드려 볼 수가 없었다. 실제 문제 풀이는 Python으로 작성할 생각이고, 적당한 코드 리뷰 후에는 Swift로 옮겨볼 생각이다. 본론 문제 답 Egg's import math import datetime as date #initial data tot_num = 0 max_for..

Python #3

서론 이전 시간에 풀다 남은 276번 부터 290번 까지. 파일 입출력을 건너 뛰고 에러 처리에 해당하는 4문제 가량을 진행했다. 본론 276번 부터 280번 까지는 이전의 271번 부터 275번 까지 문제의 연장선이다. 따라서 이전의 코드를 개선하는 방향으로 진행했다. 문제와 조건은 다음과 같다. Account 인스턴스에 저장된 정보를 충역하는 display_info 메서드 추가할 것. 단, 잔고는 세자리마다 쉼표를 출력할 것. 입금 횟수가 5회가 될 때 잔고 기준 1%의 이자가 발생 되도록 할 것. 생성된 Account 인스턴스를 리스트에 저장할 것. 반복문을 사용해 100만원 이상인 고객의 정보를 출력할 것. 입금과 출금 내역이 기록되도록 코드를 업데이트 할 것. 각각을 출력하는 deposit_hi..

Python #2

서론 이전 시간에 각자의 페이스에 맞겨 진행했더니 Egg > Whale > Rabbit 순서대로 진도의 차이가 났다. 큰 차이는 아니었지만 이는 각자가 제대로 된 페이스 메이커의 역할을 해 주지 못한다는 이야기로. 먼저 진행하고 있던 사람이 후위의 사람의 진행을 도와줄 수는 있으나. 이 또한 선행자의 학습 흐름을 끊은 행위기에 비효율적이라 판단했다. 따라서 문제는 한 화면을 통해 공유하여 선행고 후위의 간격을 질정 수준으로 조율하고, 너무 오래 걸리는 경우 함께 답을 확인하고 코드리뷰를 하는 방식으로 진행했다. 본론 이번에 진행한 부분은 이전 시간에 이은 131번 부터로, 어차피 모든 모듈을 알 수 없으니 이후 실습하면서 하나씩 알아 가는 것으로, 함수도 유지보수 및 코드의 효율화를 위해 필요하며 이후에..

Python #1

서론 홈페이지를 만들어 보겠다고 삽질할 때도, 앱을 만드는 중에도 이제는 머리가 굳은 건지 원래도 멍청했던 게 이제야 티가 나는 건지 슬슬 공부를 떠나서 프로젝트에 돌입하며 한계를 느끼기 시작했다. 보고 이해하는 것과 처음부터 내가 생각한 것을 구현하는 것은 상당히 큰 차이가 있다. 이걸 메꾸기 위해 다른 공부가 필요하다고 생각했다. Swift를 공부하고, 가장 많이 사용하기는 하지만 진입이 쉽고, 자료가 많기로는 Python을 따라가기 힘들다. 따라서 알고리즘 자체를 공부하고, 예제를 풀고, 이를 서로 공부하는 자리를 마련했는데, 사용하는 언어들이 다양하다 보니 같이 공부할 때는 Python을 사용하기로 결정했다. 한 녀석은 대학원생으로 Python을 이미 사용하고 있고, 한 녀석은 웹 개발자로의 취직..