본문 바로가기

전체 글

 (229)
트리 (Tree) 하나의 정점을 Node 라고 하고 Node 와 Node를 이어 주는 선을 간선(Edge) 이라고 한다. 1은 부모노드이고 1의 자식노드는 2와 3이다 Node 4 하나도 트리라고 한다. 자식노드가 2개 이하인 트리를 이진트리(Binary Tree)라고 한다. 트리 순회는 재귀적으로 구현한다.출처 : AlgorithmLABS
전염병 문제철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다. 철수네 마을은 1번부터 N번까지 번호가 매겨져 있다. 철수네 마을의 구조는 꽤나 복잡한데, i번 마을에서 출발하면 i * 2 번 마을에 갈 수 있고, 또한 i / 3(i를 3으로 나눈 몫) 번째 마을에도 갈 수 있다. 전염병은 사람에 의하여 옮는 것으로 알려져 있다. 따라서 i번 마을에 전염병이 돌게 되면, i * 2 번 마을과 i / 3(i를 3으로 나눈 몫) 번 마을 역시 전염병이 돌게 된다. K번 마을이 가장 처음으로 전염병이 돌기 시작했을 때, 전염병이 돌지 않는 마을의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 전체 마을의 개수 N과, 처음으로 전염..
원형 큐 구현하기 문제이 문제에서는 원형 큐를 구현한다. 선형 큐는 “큐가 실제로는 비어있어도 Push와 Pop을 할 수 없는" 문제가 발생할 수 있다. 원형 큐는 이 문제를 해결한다. 원형 큐 역시 큐와 마찬가지로 다음 세 개의 연산을 지원한다.Push X : 큐에 정수 X를 push한다. 만약 rear 포인터가 더 이상 뒤로 갈 수 없다면, “Overflow”를 출력한다.Pop : 큐에서 정수 하나를 pop한다. 만약 front 포인터가 더 이상 뒤로 갈 수 없다면, “Underflow”를 출력한다.Front : 큐의 front에 있는 정수를 출력한다. 만약 큐가 비어있다면 “NULL”을 출력한다.크기가 n인 원형 큐에 m개의 연산을 하는 프로그램을 작성하시오. 입력의 편의를 위해서 Push는 “1”, Pop은 “2”..
원형 큐 (Circular Queue) 큐 구현의 문제점은 계속 rear에 원소를 추가하게 되면 위의 사진처럼 길이 10짜리 배열을 선언하고 큐의 크기를 4짜리를 사용하다 보면 배열의 크기를 벗어나게 되면 앞의 공간이 비게 되어 공간의 효율성이 매우 떨어진다. 공간의 효율성이 떨어지는 큐를 개선한 원형 큐 (Circular Queue)는 front와 rear을 연결하여 그림과 같이 공간을 효율적으로 사용할 수 있다. data 배열의 길이를 8로 선언하고, 길이가 4인 원형 큐를 구현하는 방법을 보자.rear 에 원소를 계속 추가하다 보면 data 가 꽉차게 되는데 이때 rear을 다시 0으로 바꾸는 것이다. 그러면 비어있는 앞의 공간을 활용할 수 있다. front 역시 배열의 끝까지 도달하게 되면 다시 0으로 front를 옮겨주어 공간 활용을..
큐 구현하기 문제이 문제에서는 큐를 구현한다. 큐는 다음 세 개의 연산을 지원한다.Push X : 큐에 정수 X를 push한다. 만약 rear 포인터가 더 이상 뒤로 갈 수 없다면, “Overflow”를 출력한다.Pop : 큐에서 정수 하나를 pop한다. 만약 front 포인터가 더 이상 뒤로 갈 수 없다면, “Underflow”를 출력한다.Front : 큐의 front에 있는 정수를 출력한다. 만약 큐가 비어있다면 “NULL”을 출력한다.크기가 n인 큐에 m개의 연산을 하는 프로그램을 작성하시오. 입력의 편의를 위해서 Push는 “1”, Pop은 “2”, Top은 “3”으로 표현한다. 입력첫째 줄에 큐의 크기 n, 연산의 개수 m이 주어진다. ( 1 ≤ n ≤ 100, 1 ≤ m ≤ 1,000 ) 두 번째 줄부터 ..
큐 ( Queue ) 큐 (queue) 는 한쪽 끝에서는 원소가 추가되고, 나머지 한쪽 끝에서는 원소가 삭제되는 선형 리스트이다. push 연산을 수행하게 되면 rear 에 원소가 한개씩 쌓인다. pop 연산을 수행하게 되면 front 에서 원소가 한개씩 삭제 된다. 먼저 들어간 원소가 먼저 나오기 때문에 FIFO 라고 한다. 큐의 size 만큼 원소가 꽉찼는데 push연산을 하면 Queue Overflow 가 발생한다. 큐가 비어있는데 pop 연산을 하게 되면 Queue Underflow가 발생한다. 출처 : AlgorithmLABS
탑 문제KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가..
중복없는구간 문제n개의 숫자가 주어지고, 이 중에서 r개의 연속된 숫자를 선택했을 때, 이 연속 부분 내에는 숫자가 중복되지 않기를 원한다. 예를 들어, 다음과 같이 10개의 숫자에서 3개의 연속된 숫자를 선택할 수 있다.이렇게 선택을 하면, 선택된 숫자들 사이에서는 중복이 존재하지 않는다. r의 최댓값을 구하는 프로그램을 작성하시오. 위의 경우, (4, 2, 1, 3)을 선택하면 되므로 r의 최댓값은 4이다. r이 5 이상이 될 경우, 중복 없이 연속 부분을 선택하는 것이 불가능하다. 입력첫째 줄에는 숫자의 개수 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 둘째 줄에 n개의 숫자가 주어진다. 각 숫자는 항상 1보다 크거나 같고, n보다 작거나 같다. 출력r의 최댓값을 출력한다. 예제 입력10 1 3 1 2 ..

티스토리툴바