본문 바로가기

전체 글

 (39)
[방학의 PS] DFS와 BFS - BOJ_2606 어제 살짝 예고 드렸듯이 오늘은 DFS와 BFS의 구현에 대해 심층적으로 분석해보고자 합니다. 이 글은 자료구조와 알고리즘을 개략적으로나마 훑어보신 분들을 대상으로 한 글이기 때문에 DFS가 뭐고 BFS가 무엇인지에 대한 설명은 생략하도록 하겠습니다. 그럼 이제부터 본격적으로 다음과 같은 단계에 따라 DFS와 BFS를 구현해보도록 하겠습니다. 1단계 그래프 생성 2단계 DFS와 BFS의 공통점에 대해서 생각 3단계 DFS와 BFS를 각각 구현 1. 그래프 생성 당연하지만 그래프부터 생성해야 합니다. 당연하지만 그래프는 문제에서 주어지는 방식, 프로그램이 요구하는 방식에 따라 생성하는 방법이 천차만별이긴 합니다. 저는 아래와 같은 방식으로 구현했습니다만 사실 별로 중요한 코드는 아니라고 봅니다. # n은 .. 2022. 6. 15. 06:51
[방학의 PS] set, deque, 리스트의 참조 복사 오늘은 원래 DFS와 BFS를 공부하고자 하였으나, 몇 가지 추가적인 공부가 필요하여 이를 보충하도록 하겠습니다. 1. set set은 파이썬의 데이터 타입입니다. 딕셔너리나 리스트와 같이 말입니다. 이는 수학에서 집합과 매우 유사한 특징을 지니는데, 우선 다음과 같이 선언 및 정의하게 됩니다. s1 = set([1, 2, 3, 3]) # [1, 2, 3, 3]이라는 리스트를 set 자료형으로 바꿔 s1에 저장한다는 의미입니다. s1 >> {1, 2, 3} set의 중요한 특징은 다음과 같습니다. 중복을 허용하지 않는다. 순서가 존재하지 않는다. 위의 코드에서 보신 것처럼 set은 중복을 허용하지 않습니다. 또한 순서가 존재하지 않는데, 이는 인덱스로 접근할 수 없다는 것을 의미합니다. 예를 들면 s1 .. 2022. 6. 15. 06:35
[방학의 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

티스토리툴바