![]()
괄호 검사란? 괄호의 종류로는 대중소([,]), ({,}), ((,))가 있는데 3가지 조건이 성립해야 한다. 조건 1 : 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 조건 2 : 동일 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 조건 3 : 서로 다른 타입의 괄호 쌍이 서로를 교차하면 안 된다. 괄호 검사 예시 괄호 검사 알고리즘 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 push() 오른쪽 괄호를 만나면 pop() 연산으로 스택의 top에 있는 괄호를 꺼냄 - 꺼낼 수 있는 요소가 없으면 즉, 스택이 비어 있으면 조건 2에 위배 - pop 한 왼쪽 괄호와 짝이 맞지 않으면 조건 3에 위배 마지막 괄호까지를 조사한 후에도 스택에 괄호가 남아 있으면..
![]()
스택(Stack) 이란? 스택이란 말 그대로 쌓아놓은 더미로 기본적으로 후입선출 방식으로 가장 최근에 들어온 데이터가 가장 먼저 나가는 형식의 자료구조입니다. 스택(Stack)의 연산 - 삽입(push) , 삭제(pop) - is_empty() : 스택이 공백상태인지 검사 - is_full() : 스택이 포화상태인지 검사 - peek(s) : 요소를 스택에서 삭제하지 않고 보기만 하는 연산 스택(stack)의 활용 분야 - 자료의 출력이 입력 순서와 역순으로 이루어져야 하는 경우 유용하며, 문서나 그림, 수식 등의 편집기에서 되돌리기(undo) 기능 --- 수행된 명령어들 중에서 가장 최근에 수행된 것부터 순서적으로 취소할 경우 - 함수 호출에서 복귀 순서를 기록하는 데 사용 - 문서나 소스코드에서 괄호..
![]()
오늘은 합병 정렬에 대해서 공부해보았습니다~ 합병 정렬(merge sort) 이란? 분할 정복을 사용해서 정렬하는 알고리즘인데, 분할 정복은 하나의 문제를 두 개로 나누어서 두 개의 문제를 각각 해결하여 원래의 문제를 해결하는 것인데, 간단한 예로 들자면 정렬되지 않은 한 개의 배열을 순환적으로 두 개의 배열로 나누어서 배열의 크기가 1이 될 때 각각 나누었던 배열을 다시 합치면서 정렬시키는 것이에요~ 합병 정렬(merge sort) 알고리즘에서는 분할(Divide), 정복(Conquer), 결합(Combine) 단계들로 이루어지는데, 분할(Divide)은 배열을 같은 크기의 2개의 부분 배열로 분할하고, 정복(Conquer)은 나누어진 배열을 정렬을 시킵니다. 마지막으로 정복(Conquer)은 정렬된 ..
![]()
삽입 정렬(Insertion sort) 이란? -삽입을 사용하면서 정렬하는 알고리즘으로 삽입할 값(key)과 값(key)들이 정렬된 리스트가 있을 경우, 정렬된 리스트에 값을 삽입할 때 정렬된 순서를 보존하면서 삽입을 하는 것이 삽입 정렬이다.자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 삽입 정렬(Insertion sort) 알고리즘 예제 배열에 5,2,4,6,1,3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보았다. key 2 와 첫 번째 자료인 5를 비교한다. 5가 2보다 더 크므로 5를 2자리에 넣고 2를 5의 자리인 첫 번째에 기억시킨다. key 값 4랑 두 번째 자료인 5랑 비교한다. 5가 ..
