후회가 없도록

문제 출처: https://www.acmicpc.net/problem/1260 1. 결과 메모리 33100KB, 시간 144ms 2. 풀이 DFS와 BFS 모두 가능한 각 경로를 탐색하는 방법이지만, DFS는 루트 노드에서 시작하여 일단 하나의 분기를 끝까지 탐색해본 후, 다시 직전에서 다른 것을 탐색하는 방식이고, BFS는 루트 노드에 연결된 모든 자식 노드를 탐색, 이후 그 자식 노드의 자식 노드들을 탐색하는 방식으로 루트로부터 떨어진 높이마다 해당 높이에서 가능한 경우를 모두 탐색한다. 이런 특징 때문에 DFS는 특정 경로를 찾아내는 문제, 순열이나 조합 등을 찾을 때 주로 사용하고, BFS는 최단 거리를 찾을 때 주로 사용한다고 한다. 일단 이 문제는 간단한 DFS, BFS 구현이 요점이기 때문에..

문제 출처: https://www.acmicpc.net/problem/10942 1. 결과 메모리 60000KB, 시간 1816ms 2. 풀이 동적 계획법을 다루는 문제에서 팰린드롬(Palindrome)은 대표적인 예제 중 하나이다. ABA, ABCBA와 같이 앞에서 한 글자씩 읽어도, 뒤에서 한 글자씩 읽어도 같은 문자열이 되는 경우를 팰린드롬이라고 한다. 주어진 문자열에서 가능한, 가장 긴, 연속된 팰린드롬 문자열의 길이를 구하는 문제가 팰린드롬 관련 문제 중 가장 기초가 되는 문제이고, 그 외에 가장 긴 팰린드롬 자체를 구하는 문제나 이 문제처럼 팰린드롬의 여부를 묻는 문제도 있다. 여기서 말한 다른 팰린드롬 문제는 블로그에 알고리즘 풀이를 기록하기 이전에 풀어봤기 때문에 아직 없지만, 추후에 특정..

문제 출처: https://www.acmicpc.net/problem/11444 1. 결과 메모리 29200KB, 시간 88ms 2. 풀이 이 문제는 평범한 재귀 호출이나 동적 계획법과 같은 연산을 통해 구하기가 쉽지 않다. 문제 조건에서 볼 수 있듯이 Fn을 구하는데, 해당 n이 최대 10^17(10의 17제곱)까지 가능하기 때문이다. 또한 피보나치 수열은 궁극적으로 앞의 연속된 두 숫자를 알아야만 그 다음 숫자를 구할 수 있고, 앞의 연속된 두 숫자는 또 해당 숫자의 앞의 연속된 두 숫자를 알아야만 연산이 가능하다. 즉, 기존의 피보나치 수열 개념( Fn = Fn-1 + Fn-2 (n ≥ 2) )은 연쇄적으로 연산이 되기 때문에, 각각의 독립된 소문제 해결을 통해 큰 문제를 해결하는 일반적인 분할 정..

문제 출처: https://www.acmicpc.net/problem/11401 1. 결과 메모리 188804KB, 시간 1144ms 2. 풀이 이 문제를 처음에 풀이할 때는 혼란스러웠다. 분할 정복과 재귀 호출 등을 사용해서 팩토리얼 연산 횟수를 최대한 줄이는 것이 문제의 요점이라고 생각했다. 하지만 그렇게 풀이한 코드는 채점 결과 런타임 에러를 발생했고, 생각해보면 최대 400만 번의 재귀 호출이 발생할 수 있기 때문에 납득할 수 있는 결과였다. 하지만 그렇다면?? 어떤 풀이로 접근을 해야 할지 고민을 하며 다른 블로그와 풀이 아이디어만을 참고하려고 검색하던 중 '페르마의 소정리'를 이용하는 문제라는 것을 알았다. 페르마의 소정리란 코드의 주석 부분에 작성한 것처럼 소수인 p와 그 p의 배수가 아닌 ..

문제 출처: https://www.acmicpc.net/problem/1780 1. 결과 메모리 67648KB, 시간 3592ms 2. 풀이 분할 정복을 최근에 제대로 배워보면서 분할 정복과 재귀 호출을 연습하게 되는 계기가 되었다. 또한, 나로서는 이 문제에서 하나의 함수만으로 재귀 호출 후 답을 반환하는 아이디어가 쉽게 떠오르지 않았기 때문에 전역 변수를 사용했다. 각 함수 내에서 global을 통해 counts가 전역 변수임을 알렸는데, 이런 전역 변수 선언은 가장 함수의 맨 위에서 이루어져야 한다. 파이썬은 위에서부터 순서대로 읽어나가는 경향이 있기 때문에, 함수의 중후반에서 전역 변수 선언을 했을 때는 그 이전 줄에서 이 counts라는 변수를 읽지 못하고 오류가 발생했다. 오히려 전역 변수를 ..

문제 출처: https://www.acmicpc.net/problem/10773 1. 결과 메모리 29980KB, 시간 4908ms 2. 풀이 이 문제는 솔직히 전혀 어려웠거나 어떤 이슈가 있는 것이 아니고, 직접 스택이라는 추상적 자료형을 클래스로써 구현한 코드를 담고 있기 때문에 남긴다. 파이썬의 리스트를 이용해서 구현해서 충분히 쉽게 풀이가 가능한 문제이다. import sys class Stack: def __init__(self): self.stack = [] def push(self, x): self.stack.append(x) def rmpop(self): if self.stack: self.stack = self.stack[:-1] def pop(self): if self.stack: re..

우선순위 큐란, 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형을 의미한다. 비선형 구조를 갖는 자료구조인데, 배열이나 연결 리스트로도 구현할 수 있지만 출력과 원소를 찾고 삭제하는 과정 등이 비효율적이기 때문에, 보통은 힙(Heap)을 통해 구현한다. 그리고 파이썬에서는 heapq 라이브러리를 이용해서 힙의 연산을 이용할 수 있다. 1. 힙(Heap) 우선, 힙이란 완전 이진 트리(Complete Binary Tree)이고, 모든 노드에 저장된 값들은 자식 노드들의 값보다 작거나 같다. 여기서 값의 크기가 작을수록 큰 우선순위를 부여하는 것이라고 생각하면 된다. 즉, 배열을 정렬했을 때 기본적으로 오름차순 정렬되는 것처럼 일반적인 힙에서는 루트 노드(우선순위가 가장 높은 노드)가 값이 가장 작다. ..

자료구조는 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조는 자료들이 순서를 가지고 있는 연속된 자료구조를 뜻한다. 선형 구조를 갖는 대표적인 자료구조는 스택(Stack)과 큐(Queue)가 있는데, 이 글은 이 둘에 대한 개념과 구조, 구현 소스 코드 등을 정리했다. 1. 스택(Stack) 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조로써, 후입선출, LIFO(Last In First Out) 등의 성격을 갖는다. 배열, 연결 리스트 등의 자료구조로 구현할 수 있으며, 파이썬의 리스트도 거의 스택과 비슷한 방식으로 동작한다. push, pop, size, empty, top 등의 연산을 구현할 수 있으며 이를 구현한 코드와 다른 책을 참조한 소스 코드는 각각 아래 링크에 있다. 1) 간단하게 구..

우선, 자료구조란 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공하는 형태를 의미한다. 자료구조는 추상적 자료형(자료와 그 자료에 대한 연산을 개념적으로 정의만 한 것)을 구체적으로 구현한 결과라고 표현할 수도 있다. 즉, 리스트(파이썬의 자료 type 중 리스트와는 다름), 스택, 큐, 트리 등의 명칭과 그 구조의 개념은 추상적 자료형에 속하고, 이를 실제로 사용할 수 있도록 모듈, 클래스 등을 통해 구현한 것 또는 이를 구현하는 도구가 되는 것(배열, 연결 리스트 등)을 자료구조라고 생각하면 된다. 이 글에는 대표적인 자료구조(배열, 연결 리스트)의 구조 개념, 장단점과 함께 이를 구현한 코드를 정리했다. 1. 배열(Array) 배열은 절대적인 순서에서 인덱스(위치)를 통해 조회..

명시적인 것이 암시적인 것보다 낫다. - 파이썬 철학 중 일부 - 1. 기원 1) 누가 귀도 반 로섬(Guido van Rossum) 2) 언제 1989년 12월 3) 어디서 네덜란드 CWI(Centrum voor Wiskunde en Informatica, 국립 수학 및 과학 컴퓨터 과학 연구기관) 4) 어떻게 최초로 1980년대 말 고안되었고, 반 로섬이 구현하며 파이썬의 주 저자로 계속 중심적 역할을 맡아 파이썬의 방향을 결정. 5) 왜 귀도 반 로섬은 암스테르담대학교에서 컴퓨터과학과 수학을 전공하고, CWI라는 연구소에서 인터프리터 언어(interpreted language)를 개선하는 일을 맡았다. CWI에서는 개발 범용의 명령형 컴퓨터 프로그래밍 언어 ABC를 개발하는 프로젝트를 시작했지만, ..