https://www.acmicpc.net/problem/1927문제널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 분류자료 구조우선순위 큐 접근 방식문제 자체는 heap 자료구조에 대해 이해하고 있으면 되고 파이썬의 내장 라이브러리 heapq를 사용하면 되므로 어렵지 않다. (이후에 heap 내용을 정리해서 글을 써보는 걸로...)하지만 계속 시간초과가 떴고, 원인은 입출력 속도가 느려서였다.import sysinput = sys.stdin.readline sys.stdin.readline(..

https://www.acmicpc.net/problem/2910문제위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다. 창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다. 만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다. 이렇게 정렬하는 방법을 빈도 정렬이라고 한다. 수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오. 분류자료 구조정렬해시를 사용한..

https://www.acmicpc.net/problem/9012   문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’와 ‘)’ 만으로 구성되어 있는 문자열이다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS..

Recursion : when a method call itself 자기자신을 불러 반복하여 결과 값을 업데이트하는 것 loop문 없이 본인을 호출하여 반복문이 된다. 끝에 도달하면 return하는 값이 정해져있다. 표현법이 단순하고, 복잡한 문제를 간단하게 해결할 수 있다. but, 이해하는게 어려울 수 있다. 재귀로 간단하게 해결할 순 있지만 쉬운건 아님!!!! Base case : Values of the input variables for which we perform no recursion calls are called base cases (there should be at least one base case). : Every possible chain of recursive calls must..

문제 N개의 노드로 구성된 트리가 입력으로 주어진다. 이때, 각 노드는 1번부터 N번까지 서로 다른 번호로 구분되며, 트리의 루트는 1이다. 노드 v의 조상(ancestor)은 노드 v부터 루트까지의 경로 상에 있는 노 드이다. 노드의 번호를 입력으로 받아, 해당 노드의 모든 조상들을 공백으로 구분하여 출력하는 프로그램을 작성하시오. 예제 입출력 예제 입력 예제 출력 10 4 1 2 1 3 1 4 2 5 3 6 3 7 6 8 6 9 6 10 4 8 5 9 1 6 3 1 2 1 6 3 1 가장 처음으로 트리를 구현해봤던 건데 이제서야 올린다. 딱히 어떤 순회나 탐색을 써야겠다고 생각하고 구현한건 아니고 그냥 순서대로 찾기... row index가 부모이고 column index가 자식이다. 트리 벡터의 r..

구현한 내용은 아래와 같다. 정수를 저장하는 트리를 구현한 뒤, 입력으로 주어지는 명령어를 처리하는 프로그램을 작성하시오. 트리의 루트는 항상 1이며, 초기 상태의 트리에 1이 삽입되어 있다. 명령어는 다음과 같이 총 5가지 이다. insert x y: 노드 y를 노드 x(1 ≤ x ≠ y ≤ 10,000)의 자식으로 트리에 삽입한다. 만약 y가 이미 트리에 존재하거나, x가 트리에 존재하지 않을 경우, -1을 출력한다. delete x: 트리에서 노드 x(2 ≤ x ≤ 10,000)를 삭제한다. x의 자식 노드는 모두 x의 부모 노드의 자식으로 차례로 연결한다. 만약 노드 x가 트리에 존재하지 않을 경우, -1을 출력한다. parent x: 노드 x(2 ≤ x ≤ 10,000)의 부모 노드를 출력한다...