공부하는 과자

https://velog.io/@cheesesand cheesesand (치즈샌드) / 작성글 - velog velog.io블로그를 velog로 이전했습니다~

알고리즘을 풀다 보면이 문제와 같이 "출력값의 절대오차 또는 상대오차가 10^-9 이하이면 정답"라는 조건이 달린 문제를 많이 볼 수 있다. 이번 글에서는 오차, 절대 오차, 상대 오차에 대해 알아본 후해당 문제를 풀이할 것이다. 오차(Error)오차란 참값(또는 이론값)과 실제 측정값(또는 근삿값) 사이의 차이를 의미한다.굳이 식으로 본다면 다음과 같이 볼 수 있다. 오차 = 측정값 또는 근삿값 − 참값 (실제 값) 절대 오차(Absolute Error)절대 오차란 참값과 근삿값의 차이를 절댓값으로 취한 것을 의미한다.식으로 예를 들면 다음과 같이 볼 수 있다. 참값 = 3.14159265근삿값 = 3.14 절대 오차 = ∣근삿값 − 참값∣= 0.00159265 이걸 또 다르게 표현하면 0.001592..

이중 연결 리스트(doublely linked list)는 두 개의 포인터를 사용하여 선행 노드와후속 노드에 모두 연결되는 양방향 구조를 가진다.  자료 삽입이중 연결 리스트에서 자료를 삽입하는 과정음 다음과 같다.먼저 새로운 노드를 생성하여 노드의 데이터 영역에 자료(B)를 저장한다.  새로운 노드(B)의 오른쪽 포인터 영역이 다음 노드(C)를 가리키게 하고,새로운 노드(B)의 왼쪽 영역이 이전 노드(A)를 가리키게 한다.  후속 노드(C)의 왼쪽 포인터 영역이 새로운 노드(B)를 가리키게 하고,선행 노드(A)의 오른쪽 포인터 영역이 새로운 노드(B)를 가리키게 한다.  자료 삽입이 완료된 상태는 다음과 같다.  자료 삭제자료가 저장된 리스트에서 가운데 위치한 노드(B)를 삭제하는 과정은 다음과 같다...

자료 삽입단순 연결 리스트에서 자료를 삽입하는 과정은 다음과 같다.먼저 새로운 노드를 생성하여 노드의 데이터 영역에 자료(B)를 저장한다.  새로 생성된 노드(B)의 포인터 영역이 후속 노드(C)를 가리키게 한다.  선생 노드(A)의 포인터 영역이 새로 생성된 노드(B)를 가리키게 한다.  이전 노드(A)와 후속 노드(C) 사이에 새로운 노드(B)가 삽입되었다.  이처럼 연결 리스트에서 자료를 삽입하고자 할 때는 포인터 값만변경시팀으로써 연산을 쉽게 수행할 수 있으며, 이웃하는 노드들을이동시키지 않아도 된다. 자료 삭제단순 연결 리스트에서 자료를 삭제하는 방법 역시 간단하다.자료가 연결된 리스트에서 가운데 위치한 노드(B)를 삭제하는과정은 다음과 같다.  먼저 삭제하고자 하는 노드(B)의 이전 노드(A)..

단순 연결 리스트는 각 노드마다 하나의 포인터 영역을 가지며,이전 노드의 포인터가 다음 노드를 가리키면서 서로 연결된 구조이다.기억 공간 내 떨어져 있는 자료들을 포인터로 연결하며, 자료가주기억 장치 내에 물리적으로 어떻게 저장되어 있는지에 관계없이포인터가 가리키는 주소를 사용하여 논리적인 순서를 가진다.  연결 리스트에서 하나의 자료를 저장하는 단위를 노드(node)라고 하며,한 개의 노드는 실제로 자료를 저장하는 데이터 영역과 다음 자료가 저장된노드를 가리키는 포인터 영역으로 구성되어 있다. 헤드 포인터(head pointer)가 첫 번째 노드와 연결되며, 포인터를 통하여연결되어 있는 각 자료에 접근할 수 있다. 또한, 마지막 노드는 더 이상연결할 후속 노드가 없기 때문에 포인터 영역을 null로 설..

자료를 순서와 상관없이 무작위로 저장하는 집합과는 달리리스트(list)는 순서에 따라 차레대로 저장하는 자료 구조를 말한다.  리스트에 각 자료는 이웃하는 원소들과 한 개씩만 대응되기때문에 선형 리스트라고도 한다. 이러한 리스트는 자료를 메모리에 저장하는 방법에 따라순차 리스트와 연결 리스트로 구분한다.  순차 리스트는 배열을 이용하여 구현하기 때문에첨자를 이용한 자료 접근 속도가 빠르며, 자료들이 나열되어있는 논리적 순서와 실제 기억 고간에 저장되는물리적 순서가 같다. 그러나 자료의 삽입이나 삭제 연산 시 원소들을 일일이이동 시켜야 하는 배열의 문제점도 그대로 지니고 있다.  연결 리스트는 물리적인 저장 공간 내에 각각 흩어져 있는자료들이 링크로 서 연결되어 있는 구조를 말한다.선행 자료에는 후속 자료..

자료 삽입큐에 아무런 자료도 입력되지 않은 초기 상태일 때 front와 rear값은-1로 설정되어있다. 이후 자료가 삽입될 때마다 rear가 1씩 증가하며한 칸씩 뒤로 이동하게 된다. 추가로 front와 rear가 같다는거는 위에 경우처럼초기 상태이거나 큐에 저장된 자료가 없다는 것을 의미한다.  이런 식으로 큐에 새로운 자료를 삽입할 때에는 rear 포인터를 먼저1 증가시켜 자료를 입력 받게 된다.  큐도 스택과 마찬가지로 제한된 용량을 가지고 있기 때문에 저장 공간이가득 차 있는 상태에서 추가로 다른 자료를 입력하면 오버플로가 발생한다.다시 말해, rear와 큐의 크기가 같아지면 더 이상 삽입 연산은 불가능 하다. 자료 삭제큐에서 자료는 입력된 순서에 따라 순서대로 삭제가 이루어진다.먼저 삭제 연산을..

컴퓨터는 어떠한 작업을 수행할 때, 저장 공간 안에 먼저 입력된데이터부터 순서대로 출력되는 구조를 큐(queue)라고 한다.큐는 자료의 삽입과 삭제 모두 한쪽 방향에서만 이루어지는 스택과 달리,양쪽 방향에서 각각 삽입과 삭제가 이루어진다. 이처럼 처음에 입력된자료가 가장 먼처 출력되는 방식을 선입선출(FIFO) 구조라고 한다.  front 포인터는 삭제를, rear 포인터는 삽입할 위치를 가리킨다.  front 포인터는 큐의 앞쪽(head)에 위치하여 자료가 출력되는 지점을 가르키며,rear 포인터는 큐의 뒤쪽(tail)애서 자료를 입력하는 곳을 지정해 준다.

자료 삽입스택에서 top의 초기값은 -1이며, 자료가 삽입될 때마다 1씩 증가한다.이때 새롭게 입력할 자료를 스택의 가장 위에 추가하고, 기존에 저장된자료들은 추가한 자료의 아래에 위치하게 된다.  스택 안에 여유 공간이 있을 결우 얼마든지 자료를 추가할 수 있지만,스택의 크기보다 더 많은 자료를 입력할 수는 없다. 자료 삭제스택에서 top은 자료가 삭제될 때마다 1씩 감소한다. 즉, 삭제 연산을 수행할 경우스택의 가장 위에 입력된 자료를 먼저 제거하고 제거된 자료의 아래에 있던자료가 가장 위에 위치하게 된다.이런 식으로 자료를 삭제하게 되면 처음에 삽입된 자료가 가장 마지막에 삭제된다.  오류 발생 조건스택 구조는 제한된 저장 공간을 사용하기 때문에 연산을 수행할 때는 반드시스택의 크기와 상태를 고려해..

모든 자료의 삽입과 삭제가 한쪽 끝에사만 수행된는 제한적개념의 선형 구조를 스택(stack)이라고 한다. 스택은 가장 마지막에입력된 자료가 가장 먼처 출력뙤기 때문에 후입 선출(LIFO)구조라고 한다. (스택의 구조) 이처럼 스택의 중간에 자료를 삽입(push)하거나 삭제(pop)할 수가 없기 때문에 자료의 입출력이 비교적 제한적이며,스택의 톱(top) 위치에서만 자료의 삽입과 삭제가 이루어진다. (top 포인터의 위치) 톱(top)은 일반적으로 스택의 가장 위에 위치하는 자료를 가르키며,동시에 삭제할 지점을 가르키는 역할도 한다. 톱 포인터(top pointer)는 컴퓨터에 저장되는 데이터 기억 장치 내의연속적인 공간에 주소를 부여받아 저장된다.포인터는 이러한 자료의 위치(번지)를 가르키는 역할을 하는..