에르미타쥬 에르미타쥬

https://www.acmicpc.net/problem/1463 언뜻 보면 단순한 문제로 보인다. 그냥 1, 2, 3번을 구현해서 적용하면 되는 것처럼 보인다. 그러나 그렇지 않다. 연산을 사용하는 횟수의 최솟값을 출력하라는 뜻은 연산을 최고의 효율로 진행하라는 뜻. 1로 만들기위해 쓸데없는 연산을 진행해선 안된다. 경우의 수를 담을 리스트를 만들었다. 그다음 정수 X에 대한 세 가지 연산에 따른 경우의 수를 리스트에 저장했다. 그리고 경우의 수에 따른 값들에 다시 세 가지 연산을 적용하면 경우의 수 아홉 가지가 나올 것이다. 이를 리스트에 저장한다. 그리고 이를 반복하다가 1로 만드는 순간 연산의 최솟값을 출력하면 된다. 123456789101112131415161718192021222324X = i..

https://www.acmicpc.net/problem/1978 주어진 수에서 소수를 찾는 문제이다. 소수란 1과 자기 자신으로 만 나누어지는 수이다. 1은 제외되고 2, 3, 5 , 7, 11 .. 그 외에 수로 나누어지는 수는 소수가 아니다. 이에 착안하여 수가 주어졌을 때 1과 자기 자신을 제외한 다른 수로 나누었을 때 값이 정수라면(나누어졌다는 뜻이니까..) 제외하는 방식으로 코드를 작성하였다. 12345678910111213141516num = input()count = int(num)nums = list(map(int,input().split(' ')))if len(nums) == int(num): for i in nums: if i != 1: for j in range(2,i): if (i..

https://www.acmicpc.net/problem/1110 깊이 생각할 것 없이 문제 내용을 충실히 반영하면 되는 문제였다. 다만, '먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자릿수로 만들고, 각 자리의 숫자를 더한다.'라고 나와있는데 코드 작성 시 반영할 필요가 없다. 예를 들어서 주어진 수가 10보다 작은 3이라고 가정하자. 10을 곱하지 않고 3을 그대로 사용했을 시 어차피 1의 자릿수이기에 더할 필요 없이 3을 그대로 사용한다. 10을 곱해서 30으로 만들어 사용했을 시 각 자리의 수를 더하게 된다. 그래봐야 3+0 = 3 이므로 10을 곱하지 않은 이전 값과 동일하게 된다. 그러니 무시해주면 된다. 이 문제는 // 연산자와 % 연산자를 잘 사용해야 하는 문제이다. a//b은 ..

https://www.acmicpc.net/problem/11718https://www.acmicpc.net/problem/11719 파이썬의 특성을 이용하면 쉽다. 파이썬은 입력을 그대로 출력을 받아주는 함수 print()를 제공하기 때문이다.while 반복문 아래 try , except 예외 처리 구문으로일단 입력을 받아 출력해보고(try) 예외가 발생(EOFError)하면 프로그램이 멈추는 구조로 작성한다. *EOFrror : 읽어들일 데이터가 더 이상 없을 때 발생하는 에러11718번, 11719번 문제는 다음과 같은 코드로 둘 다 해결 가능하다. 123456while True: try: print('''%s''' % input()) except EOFError: break Colored by C..

지금까지 배워온 정렬은 두 수의 대소를 '비교'하는 과정을 거쳐 정렬하는 comparison sort였습니다. 두 수를 반복적으로 비교해 정렬하는 comparison sort는 아무리 알고리즘을 잘 짜도 계산 복잡성이 O(nlogn)보다 큽니다. 예를 들어서 퀵 정렬(quick sort)의 계산 복잡성이 O(n^2)이고, 힙 정렬(heap sort)이 O(nlogn)이라는 점을 감안하면 이 같은 내용이 들어맞음을 확인할 수 있습니다. 하지만 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산 복잡성을 O(n) 선까지 낮추려는 알고리즘입니다. - counting sort 예를 들어, 다음과 같은 input array에 대해 counting sort를 수행한다면, inp..

힙이라는 자료구조는 무엇일까. 한 노드(node)가 최대 2개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 트리구조를 말한다.모든 노드의 값이 각자의 자식 노드의 값보다 크거나 같은 것을 최대 힙(Max heap)이라한다.모든 노드의 값이 각자의 자식 노드의 값보다 작거나 같은 것을 최소 힙(Min heap)이라한다.힙은 최대 힙이거나 최소 힙이어야 한다.또한, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 완전이진트리(complete binary tree)이다. 이러한 힙 속성(최대 힙, 완전이진트리)를 만족하면 다음 그림처럼 트리구조가 완성된다.힙은 완전이진트리 성질을 만족하기 때문에 1차원 배열로도 표현이 가능하다. [100, 19, 36, 17, 3, 25, 1, 2, 7]..

이진 탐색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는값보다 크면 그 값은 새로운 최댓값이 되며, 작은 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두배가 되므로 속도가 빠르다는 장점이 있다. 123456789101112131415def binary_search(target, data): data.sort() start = 0 end = len(data) - 1 while start

우선순위 큐의 각 원소들은 우선순위를 갖고 있다. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다. 즉, 우선순위가 다르다면 우선순위에 따라 원소들이 처리되지만 우선순위가 같은 경우 큐의 본래 특성인 선입 선출에 따라 큐가 처리된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#노드 클래스 생성class Node: def __init__(self, data, pri): self.data = data self.next = None self.pri = pri #우선순위 큐class Priority_Queue:..