프로그래밍 (25) 썸네일형 리스트형 [방학의 PS] 다이나믹 프로그래밍(DP) - BOJ_1463 오늘은 새로운 알고리즘에 대해서 이야기해 보겠습니다. 바로 다이나믹 프로그래밍이라고 불리는 알고리즘입니다. 혹시 처음 들어 보신 분이 계시다면, 이름이 생소하고 고급져서 왠지 어렵게 느껴지실 수도 있을 것 같습니다. 그러나 걱정할 것 없습니다. 사실 다이나믹 프로그래밍(이하 dp)이라는 이름은 알고리즘의 개발자가 펀딩을 따내기 위해 일부러 있어 보이게 작명한 네이밍이거든요ㅎㅎ. 실상은 아주 단순한 알고리즘을 의미합니다. dp의 핵심은 문제를 반복되는 단계로 쪼개어 앞선 단계의 값을 뒤의 단계에서 활용한다는 것입니다. 이 말의 의미를 피보나치 수열을 예로 들어 자세히 알아보겠습니다. 우리가 코딩을 통해 피보나치 수열의 n번째 수를 구하는 경우, 다음과 같이 재귀를 주로 활용합니다. def fib(n): i.. 2022. 6. 15. 06:17 [방학의 PS] 균형잡힌 세상 - BOJ_4949 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 오늘의 문제는 자료구조 알고리즘 시간에도 한 번 다루었던 스택에 관한 문제입니다. 대표 유형인 괄호 문제이죠. 스택의 핵심은 모두 아시다시피 FILO(First In, Last Out)입니다. 그 부분을 집중해서 읽어보시면 여태까지 제가 올린 문제 중에서는 가장 수월하게 해결하실 수 있으실 것 같습니다. 정답 코드는 다음과 같습니다. brackets = ['(', ')', '.. 2022. 6. 15. 06:08 [방학의 PS] 프린터 큐 - BOJ_1966 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 큐 문제인 듯 큐 문제 같지 않은 문제입니다. 저는 처음에 우선순위 큐 문제로 내용을 착각하고 이를 통해 구현해보려다 삽을 좀 푼 뒤, 근본적인 구현으로 다시 돌아갔습니다. 덕분에 시간을 너무 많이 허비했네요ㅠㅠ 큐의 핵심은 FIFO(First In, First Out)입니다만, 이것만으로는 풀기 어려운 문제였습니다. 문제에서 주어지는 논리를 만족하는 자료구조를 생각한 뒤, 어떻게 하면 중복되는 요소.. 2022. 6. 15. 06:04 [방학의 PS] 이분 탐색과 매개 변수 탐색 - BOJ_2805, BOJ_1654 자료구조 및 알고리즘을 간략하게나마 공부했던 학생들을 대상으로 한 review 및 관련 문제 풀이 형식의 글입니다.😊 1. Binary Search 이분 탐색 또는 이진 탐색은 이미 정렬된 배열에서만 사용할 수 있는 탐색 알고리즘입니다. 우리가 찾으려는 원소를 target이라고 합시다. 그리고 탐색 대상이 되는 배열의 시작을 start, 끝을 end, 가운데에 위치한 원소를 mid라고 합시다. target mid 일 경우, 탐색 대상이 되는 배열을 mid부터 end까지 축소합니다. 즉 start = mid가 됩니다. 이렇게 절반씩 뚝뚝 끊어서 탐색하기 때문에 시간 복잡도는 .. 2022. 6. 15. 05:52 Javafx를 활용한 육목(Connect6) 만들기 1. UML diagram 2학년 자바 수업 마무리 프로젝트로 간단한 육목 게임을 만들어 보았습니다. 육목의 규칙은 다음과 같습니다. 1) 흑이 먼저 돌 한 개를 착수한다. 2) 백과 흑이 번갈아 가면서 차례로 돌을 두 개씩 착수한다. 3) 같은 색의 돌 6개를 먼저 연속하게 착수하는 쪽이 승리한다. 상기된 룰로만 진행되며 오목에 존재하는 3·3 착수 금지 등 복잡한 룰 없습니다. 그럼에도 양 진영 간에 균형 잡힌 승률을 달성하기 때문에 공개된 정보의 공정한 게임을 대표합니다. 2. Connect6 Class Connect6 클래스를 메인 클래스로 합니다. 중심이 되는 변수는 3개입니다. 어떤 플레이어의 차례인지를 나타내는 char 변수인 whoseTurn가 있습니다. 흑돌의 순번일 때는 ‘B’이고, 백.. 2022. 6. 6. 22:37 Circular Queue in Python global SIZE class Q: def __init__(self, front, rear): self.queue = [None] * SIZE self.front = front self.rear = rear def isQueueFull(self): if self.queue[self.circulate(self.rear)] != None: return True else: return False def enQueue(self, data): if self.isQueueFull(): print("Queue is Full ...") else: self.rear = self.circulate(self.rear) self.queue[self.rear] = data def isQueueEmpty(self): if se.. 2022. 3. 29. 00:00 Example using Stack in Python 1. Stack 클래스 정의 from queue import Empty class ArrayStack: def __init__(self): self._data = [] def __len__(self): return len(self._data) def is_empty(self): return len(self._data) == 0 def push(self, e): self._data.append(e) def pop(self): if self.is_empty(): raise Empty('Stack is empty') return self._data.pop() def top(self): if self.is_empty(): raise Empty('Stack is empty') return self._data[-1.. 2022. 3. 19. 10:37 에라토스테네스의 체 import sys ipt = sys.stdin.readline n = int(ipt()) sieve = [False, False] + [True] * (n-1) for i in range(2, int(n**0.5)+1): if sieve[i]: for j in range(i+i, n+1, i): sieve[j] = False for i in range(n*1): if sieve[i]: print(i, end=' '); 1. 모든 수를 소수라 가정함. 2. 소수가 아닌 수를 지움. * square에 대하여 예민해야 함. * dictionary를 사용하여 푸는 방법도 있음. 2022. 3. 16. 05:50 이전 1 2 3 4 다음
