공부하는 블로그 ✍️

기출문제 (3) 문자열 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하시오..

💬 문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다. 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는..

💬 문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 💡제한사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의..

1406. 에디터 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. 초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. ..

import from queue import PriorityQueue 생성 que1 = PriorityQueue() # que1.qsize() = 무한대 que2 = PriorityQueue(maxsize=10) # que2.qsize() = 10 우선순위 큐의 기본 사이즈는 무한대로, 만약 최대 크기를 지정하고자 한다면 maxsize 속성을 사용해 지정한다 데이터 삽입 que.put(7) que.put(3) que.put(5) 데이터 삭제 print(que.get()) # 3 print(que.get()) # 5 print(que.get()) # 7 get() 메서드를 사용해 오름차순으로 데이터를 삭제하고, 삭제한 값은 반환한다 우선순위 지정 que.put((5, 'FIVE')) que.put((1, ..

힙(Heap)의 삭제 연산 과정 루트 노드의 값이 가장 먼저 삭제된다. 최대 힙의 경우 최대값부터, 최소 힙의 경우 최솟값부터 삭제된다 최대 힙을 예로 들어 힙의 삭제 연산에 대해 알아보자 루트 노드를 삭제하고, 마지막 노드를 루트 노드의 자리로 이동한다 최대 힙은 루트 노드에 최대값이 와야 한다. 삭제 연산 후 루트 노드의 값은 전체 노드 중 최댓값이 아니므로 재구조화 과정이 필요하다. 루트 노드의 자식 노드 중, 더 큰 값(6)과 루트 노드의 값(2)을 비교하고 swap한다 부모 노드의 값(2)이 자식 노드의 값(5) 보다 작으므로 swap을 진행해주어 최대 힙의 구조를 완성시킨다

힙의 삽입 연산 2 → 5 → 3 → 4 → 6 → 1 → 7의 순서로 최대 힙에 값을 삽입하는 과정을 살펴보자 비어있는 노드에 값을 넣고, 부모 노드와의 대소 관계를 비교하며 swap과 insert를 반복한다 루트 노드에 2를 삽입한다 5을 삽입한다. 부모 노드(2) 보다 자식 노드(5)가 크기 때문에, swap을 진행한다 더 이상 대소 관계를 비교할 부모 노드가 없으므로 swap을 멈춘다 3을 삽입한다. 부모 노드(5)와 자식 노드(3)의 대소 관계가 성립한다 4을 삽입한다. 부모 노드(2) 보다 자식 노드(4)가 크기 때문에, swap을 진행한다 swap을 진행한 후 부모 노드(5) 와 자식 노드 (4)의 대소 관계가 성립하므로 swap을 멈춘다 6을 삽입한다. 부모 노드(4) 보다 자식 노드(6)..

힙(Heap) - 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조 - 키 값의 대소 관계는 오로지 부모노드와 자식 노드 간에만 성립하며, 형제 사이에는 대소 관계가 정해지지 않는다 - 각 노드의 자식 노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 자식 노드의 개수가 최대 2개인 이진 힙을 사용한다 - 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트노드에 오게 되는 특징을 갖는다 - 루트 노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있다 - 따라서 힙 구조에서의 최댓값(혹은 최솟값)을 찾을 때의 시간복잡도는 O(1)이다 - 데이터의 삽입과 삭제는 모두 O(logN)이 소요된다 - 이를 응용하면 우..

큐(Queue) - 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아두기 위한 자료구조이다 - 스택과 달리 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(First In First Out / FIFO) 구조를 갖는다 - 큐에 데이터를 넣는 작업은 인큐(enQueue), 꺼내는 작업은 디큐(deQueue)라고 한다 - 그리고 데이터를 꺼내는 쪽을 Front, 넣는 쪽은 Rear라 부른다 선형 큐 - 기본적인 큐의 형태로 선형으로 구현된 큐를 말한다 - 선형 큐는 인덱스의 감소 없이 증가만이 이루어지는 방식이기 때문에, 큐의 앞부분에는 데이터가 없는 경우가 발생한다 - 이러한 방식은 front의 앞부분을 다시 활용 못하기 때문에 메모리를 낭비한다는 단점이 있다 - 메모리 낭비를 하지않고, 앞의 빈 공간을..

스택 (Stack) - 스택은 박스 쌓기처럼 먼저 쌓은 박스를 마지막에 꺼낼 수 있다 - 이러한 구조를 선입 후출(First In Last Out / FILO) 혹은 후입 선출(Last In First Out) 구조라고 말한다 - 스택은 데이터를 일시적으로 저장하기위한 데이터 구조이다 - 스택에 데이터를 넣는 작업은 push, 스택에서 데이터를 꺼내는 작업은 pop이라고 말한다 - 박스쌓기와 같은 스택은, 데이터를 넣는 작업과 꺼내는 작업 모두 위쪽으로부터 수행된다 - 스택에서 푸시와 팝을 하는 위치를 꼭대기(top), 스택의 가장 아래부분은 바닥(Bottom)이라고 부른다 - 자바는 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다 public class Test { public stat..