Every step counts

10)Stack_3 계산기 문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있음 문자열 수식 계산의 일반적 방법 중위 표기법의 수식을 후위 표기법으로 변경한다.(스택 이용) 후위 표기법의 수식을 스택을 이용하여 계산한다. 중위표기법(infix notation) 연산자를 피연산자의 가운데 표기하는 방법 예) A + B 후위표기법(postfix notation) 연산자를 피연산자 뒤에 표기하는 방법 예) AB+ 중위표기식의 후위표기식 변환 방법1 수식의 각 연산자에 대해서 우선쉰위에 따라 괄호를 사용하여 다시 표현한다. 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킴 괄호 제거 Step1. 중위 표기식의 후위표기식 변환 알고리즘(스택이용) 2 입력받은 중위 표기식에서 토..

재귀호출 자기 자신을 호출하여 순환 수행되는 것 함수에서 실행해야하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성 가능 피보나치 0과 1로 시작하고 이전의 두 수의 합을 다음 항으로 하는 수열을 피보나치라고 함 피보나치 수열의 i번째 값을 계산하는 함수 F를 정의하면 다음과 같음 F0 = 0, F1= 1 Fi = Fi-1 + Fi-2 for i ≥ 2 위의 정의로부터 피보나치 수열이 i번째 항을 반환하는 함수를 재귀함수로 구현 가능 def fibo(n): if n < 2: return n else: return fibo(n-1) + fibo(n-2) 메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 ..

스택의 특성 물건을 쌓아 올리듯 자료를 쌓아올린 형태의 자료구조 스택에 저장된 자료는 선형 구조를 갖음 선형구조: 자료 간의 관계가 1대1의 관계를 가짐 비선형구조: 자료 간의 관계가 1대 N의 관계를 가짐 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다. 마지막에 삽입한 자료를 가장 먼저 꺼냄. 후입선출(Last-in, First-out) 스택을 프로그램에서 구현하기 위해 필요한 자료구조와 연산 자료구조: 자료를 선형으로 저장할 저장소 배열 사용 가능 저장소 자체를 스택이라 부르기도 함 스택에서 마지막 삽입된 원소의 위치를 top이라 부름 연산 삽입: 저장소에 자료를 저장. Push 삭제: 저장소에서 자료를 꺼냄. 삽입한 자료의 역순. Pop 스택의 공백 여부를 확인하는 연산. isEmpty 스..

문자열 비교 C에서는 strcmp() 함수를 제공 Java에서는 equals() 메소드를 제공(문자열 비교에서 ==연산은 메모리 참조가 같은지 확인하는 것) Python에서는 ==연산자와 is 연산자를 제공 == 연산자는 내부적으로 특수 메서드 eq()를 호출 문자열 정수 def atoi(data): result = 0 for i in range(len(data)): result = result * 10 + ord(data[i]) - ord('0') return result def itoa(data): result = '' while data > 0: remain = data % 10 result = chr(remain + ord('0')) + result data = data//10 retu..

컴퓨터에서의 문자표현 1967년 ASCII(American Standard Code for Information Interchange)라는 문자 인코딩 표준이 제정됨 ASCII는 7비트 인코딩으로 128문자를 표현하며 33개의 출력 불가능한 제어문자들과 공백을 비롯한 95개의 출력 가능한 문자들로 이루어져 있음 확장 ASCII는 표준문자 이외의 악센트 문자, 도형문자, 특수문자, 특수기호 등 부가적인 문자를 128개 추가할 수 있게 하는 부호. 표준 아스키는 7비트를 사용하여 문자를 표현하는데 비해 확장 아스키는 1바이트 내의 8비트를 모두 사용하여 추가적인 문자를 표현할 수 있음 컴퓨터 생산자와 소프트웨어 개발자가 여러가지 다양한 문자에 할당할 수 있도록함. 이렇게 할당된 확장 부호는 표준 아스키와 같..

검색(Search) 저장되어있는 자료 중에서 원하는 항목을 찾는 작업 목적하는 탐색 키를 가진 항목을 찾는 것 탐색 키(search key): 자료를 구별하여 인식할 수 있는 키 순차 검색(Sequential Search) 일렬로 되어있는 자료를 순서대로 검색하는 방법 가장 간단하고 직관적인 검색 방법 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격히 증가하여 비효율적 두가지 경우 정렬되어 있지 않은 경우 첫번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾음 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환 자료구조의 마지막에 이를 때 까지 검색대상을 ..

2차원 배열 1차원 List를 묶어놓은 List 2차원 이상의 다차원 List는 차원에 따라 Index를 선언 2차원 List의 선언: 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함 Python에서는 데이터 초기화를 통해 변수선언과 초기화가 가능함 예) arr = [[0, 1, 2, 3], [4, 5, 6, 7]] N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] """ 3 1 2 3 4 5 6 7 8 9 """ 배열 순회 n * m 배열의 모든 원소를 조사하는 방법 # 행 우선 순회 for i in range(n): for j in range(m): Array[i][j] # 열 우선 순회 for j in ra..

카운팅 정렬 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 제한사항 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능: 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야함 시간복잡도 O(n + k) : n은 리스트 길이, k는 정수의 최대값 list1의 요소들을 list2[0]부터 누적 카운팅완성된 list3는 list1을 정렬한 것 list1을 마지막 요소부터 하나씩 list3에 추가하고 list2에서는 1씩 감산 list2는 .. list2 = [0] * (list1의 최댓값 +1) list1은 ..

APS 과정의 목표 중 하나는 보다 좋은 알고리즘을 이해하고 활용하는 것 좋은 알고리즘은 정확성: 얼마나 정확하게 동작하는가 작업량: 얼마나 적은 연산으로 원하는 결과를 얻어내는가 메모리 사용량: 얼마나 적은 메모리를 사용하는가 단순성: 얼마나 단순한가 최적성: 더 이상 개선할 여지없이 최적화 되었는가 알고리즘의 작업량을 표현할 때 시간복잡도로 표현(Time Complexity) 실제 걸리는 시간을 측정 실행되는 명령문의 개수를 계산 def CalcSum(n): sum = 0 for i in range(1, n+1) sum += 1 return sum # 1+n*2 = 2n+1 def CalcSum(n): return n(n+1)/2 시간복잡도 = 빅-오(O) 표기법 Big-Oh Notation 시간 복..