zzugest1

중위 표기법은 연산자가 두개의 피연산자 사이에 있는 표기법이고, 후위 표기법은 연산자가 두개의 피연산자 뒤에 있는 표기법이다. 후위 표기법으로 되어있는 식을 스택을 이용해 계산하는 방법은 다음과 같다. ex) AB+CD+* 1. 식을 왼쪽부터 한글자씩 읽어나가는 방식으로 우선 피연산자는 스택에 push한다. 2. 연산자 +를 만나면 스택에 있는 두 피연산자를 pop한 후 계산을 한다. 그 뒤 계산된 값을 다시 스택에 push한다. 3. CD+부분도 위와 마찬가지 방식이고 A+B위에 push될 것이다. 마지막 연산자 *를 만났는데 마찬가지 방식으로 C+D와 A+B를 pop한 후 계산한 뒤 스택에 푸쉬 한다. 4. 수식을 다 읽고 난 후 스택에 남아있는 값을 pop한 후 출력하면 원하는 계산값이 나온다. 위..

중위 표기법은 우리가 일상에 쓰는 수식 표기법으로 연산자의 두개의 피연산자 사이에 있는 표기법을 말한다. ex) A*B+C 후위 표기법은 연산자를 두개의 피연산자 뒤에 표기하는 기법이다. ex) A*B+C -> A B * C + 위 중위 표기법이 어떤 과정을 통해 후위 표기법으로 바뀌는 지 그림으로 표현하면 A*B+C 1. 후위 표기식을 담을 빈 리스트가 있고, 연산자를 넣을 스택이 있다고 가정하자. 중위 표기식의 왼쪽부터 차례대로 읽어나가는데 피연산자인 경우 후위 표기식 리스트에 넣는다. 그 다음 연산자 *는 빈 스택에 push한다. 2. B는 피연산자이기 때문에 후위 표기식 리스트에 넣고, +를 스택에 push하기전 연산자의 우선순위를 비교한다. *는 +보다 연산의 우선순위이기 때문에 우선 *를 스택..

스택이란 자료를 보관할 수 있는 어떤 구조를 의미하는 데 데이터를 넣을 땐 한쪽 끝에서 밀어 넣어야 하고 꺼낼 때에도 넣은 방향에서 빼야하는 조건이 있다. 이러한 특성을 후입선출(Last-In First-Out)이라 한다. 그림으로 표현하자면 위와 같은 스택이 있고 A가 맨 처음 삽입된 원소라 가정하자. 그 다음 삽입연산 push(B)를 실행하면 원소 B가 A위에 삽입이 된다. 그 다음 제거(또는 반환) 연산 pop()을 실행하면 가장 최근에 삽입된, 맨 위에 있는 원소 B가 제거된다. pop()연산은 특정 원소를 지정하지 않는 것을 볼 수 있는데 스택의 특성상 무조건 맨 위 원소를 제거하기 때문이다. 스택의 추상적 자료구조를 배열로 표현한 코드는 다음과 같다. from doublylinkedlist i..

양방향 연결 리스트란 아래와 같이 앞뒤의 노드가 서로 연결되어있는 리스트를 말한다. 양방향 연결 리스트의 단점은 메모리 사용량이 커진다. 장점으로는 데이터를 앞뒤방향으로 읽을 수 있다는 점이 있다. 그래서 코드 작성이 단방향 연결 리스트보다 쉬워진다. 양방향 연결 리스트의 노드 클래스 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None 양방향이기 때문에 prev,next를 None으로 지정해 노드의 방향을 양쪽으로 구현한다. 단방향 연결 리스트의 연산과 바슷하게 적용하기 위해 양방향에서도 더미 노드를 만들어야 한다. 이 때 head의 이전과 tail 다음에 두개의 더미 노드를 만들어 양방향을 구현해..

이전 시간에는 연결리스트의 특정 원소를 지정해 연산을 하는 방법을 구현했었다. 이번엔 특정 원소의 바로 다음 원소를 지정해 연산을 하는 법을 알아보겠다. 우선 연결 리스트가 주어졌을 때 insertAfter등으로 새로운 메소드를 지정할 수 있다. 하지만 특정 원소의 바로 다음 원소를 지정할 경우, 맨 앞 원소의 삽입, 삭제 등의 연산은 이전 원소가 없기 때문에 어려움이 있다. 따라서 기존의 연결 리스트를 변형할 필요가 있다. 위 연결 리스트는 head부분의 원소가 비어있는 노드이다. 이를 dummy node라고 한다. 이 경우 위 조건의 연산을 수행할 수 있게 된다. 이를 구현하기 위한 코드는 다음과 같다. class LinkedList: def __init__(self): self.nodeCount =..

데이터 원소들을 순서를 지어 늘어놓는다는 점에서 연결 리스트 (linked list) 는 선형 배열 (linear array) 과 비슷한 면이 있지만, 선형 배열은 "번호가 붙여진 칸에 원소들을 채워넣는" 방식이라고 한다면, 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식에 차이점이 있다. 기본적 연결 리스트 위 그림과 같이 단순히 데이터가 늘어져있는 것이 아닌 앞에 있는 원소가 그 다음 원소를 가리키는 형식의 리스트를 연결 리스트라고 한다. 하나의 원소와 그 다음 원소를 가리키는 방향이 하나씩 담겨있는 것을 노드(Node)라고 한다. 위 노드에서 67은 노드의 data, 화살표는 link를 의미 한다. 노드내의 데이터는 숫자뿐만 아니라 문자열, 또 다른 연결리스트 등이 올 수 있다. 위 연결..

알고리즘의 복잡도는 문제를 푸는데 있어서 얼만큼의 자원을 요구하는지에 대한 지표이며 두가지로 나뉘는데 시간 복잡도 : 문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계 공간 복잡도 : 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계 컴퓨터의 성능이 발전되면서 공간 복잡도보단 시간 복잡도의 중요성이 높아보일 수 있지만 자료주고 특성상 고려해야하는 경우도 있다. 빅오(Big-O) 표기법이란 빅오는 점근 표기법중의 하나이며, 어떤 함수의 증가양상을 다른 함수와의 비교로 표현한다. 알고리즘의 복잡도를 표현하는 흔히 쓰이고 이름처럼 영문 대문자 O를 이용해 표기한다. ex) O(n), O(1) .. 만약 입력의 크기가 n일 때 빅오표기법을 사용한다면 O(logn) : 입력의 크기의 로그에 비례..

재귀함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 함수이다. ex) 1부터 n까지의 자연수들의 합을 구하는 함수를 재귀함수를 이용해 풀면 다음과 같이 풀 수 있다. def sum(n): print(n) if n u : return -1 mid = (l + u) // 2 if x == L[mid]: return mid elif x < L[mid]: return solution(L,x,l,mid-1) else: return solution(L,x,mid+1,u) 앞서 포스팅했던 이진 탐색 코드와 매우 유사하다. 우선 중앙값이 찾고자 하는 값 x와 같다면 중앙값을 리턴하고, x가 중앙값보다 작다면 이진 탐색에 의해 중앙값 이상 원소는 날라가게 된다. 이를 재귀적인 방법을 이용하기 위해 retur..

정렬이란 여러 원소로 주어진 데이터를 정해진 기준에 맞게 늘어놓는 작업을 말한다. 그중 대표적으로 sort가 있는데 파이썬에는 함수 sorted()와 메소드 .sort()가 있다. 이 둘의 차이점을 예시로 통해 보여주자면 a=[5,7,3,9,1] a.sort() a [1, 3, 5, 7, 9] 임의의 리스트 a를 a.sort()를 이용한 후 a를 출력하면 오름차순으로 정렬된 결과가 나온다. a=[5,7,3,9,1] sorted(a) a [5, 7, 3, 9, 1] 하지만 sorted(a)를 이용한 후 a를 출력하면 a는 그대로 출력되는 것을 볼 수 있다. 이처럼 sort는 기본적으로 오름차순으로 데이터들을 정렬하고, 그 외 정렬 기준을 여러 코드를 이용해 설정할 수 있다. 탐색이란 여러 원소로 이루어진 ..

1번 문제) 정렬된 리스트에 원소 삽입 문제 설명 리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요. 인자로 주어지는 리스트 L 은 정수 원소들로 이루어져 있으며 크기에 따라 (오름차순으로) 정렬되어 있다고 가정합니다. 예를 들어, L = [20, 37, 58, 72, 91] 이고 x = 65 인 경우, 올바른 리턴 값은 [20, 37, 58, 65, 72, 91] 입니다. 힌트: 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입하는 것이 한 가지 방법입니다. 주의: 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처..