https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 버블, 단순 선택, 단순 삽입, 셸, 퀵, 병합, 힙 중에 병합 정렬이나 힙 정렬로만 풀리는 시간 복잡도를 갖는 문제다. 퀵 정렬의 경우 꽤 빠른 정렬이기는 하지만, 배열의 종류에 따라서 그 기능이 천차만별이기 때문에 사용에 주의를 해야 한다고 한다. 병합 정렬은 재귀적인 부분에서 이해가 잘 가지 않아서 잠깐 막혔지만, 몇 가지 케이스를 따라가다 보면 이해가 될 수밖에 없는 재귀 알고리..
https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 재귀 알고리즘은 내가 배운 알고리즘들 중에서 가장 추상적인 알고리즘이다. 틀이 명확한 다른 알고리즘에 비해서 재귀는 깊이 들어갈수록 늪에 빠지는 느낌이 강하게 든다. 일일이 케이스를 분류하고 100프로 이해하려는 것보다 어느 정도 선에서 특수한 규칙까지만 확인하고 느낌대로 수정해나가는 게 더 효율적인 접근방식인 듯하다. 프로그래머스의 기초 강의와 알고리즘 도서로 간단히 복습은 했는데,..
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 알고리즘 공부는 프로그래머스의 '어서 와 알고리즘은 처음이지?' 강좌와 'DOIT 자료구조와 함께 배우는 알고리즘 입문' 책 두 가지로 기초를 다졌는데, 큐에 대해 소개된 내용은 스택과 크게 다르지 않다. 더욱이 collections의 deque모듈을 이용하면 스택과 큐 두 가지 동시에 사용할 수 있기 때문에 그 경계가 또한 모호해진다. 'DOIT 자료구조와 함께 배우는 알고리즘 입문' 책에 소개된 큐의 개념 중에 링 버퍼라는 알고리즘이 있는데, 우선 그것부터 소개해보려 한다. 1158번..
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 단순해 보이는데, 생각할수록 뭔가 복잡해보였다. 역시 예시를 따라가며 구조를 파악하는 건 중요한듯 싶다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys n, k = map(int, sys.stdin.readline().split()) s1 = list(sys.stdin.readline().rstrip()) stk1 = [] cnt = 0 for i in range(n): while cnt
https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 지난번에 풀이한 히스토그램 문항이랑 같다. 근데 지난번 풀이때 놓친 부분이 있어서 간단히 소개하려한다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 n = int(input()) s1 = [int(input()) for _ in range(n)] s2 = [0] answer = 0 s1.insert(0, 0) s1.append(0..
https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 문제는 굉장히 어렵게 써있지만, 기본 스택 문항. 지금 휴가중이라 슬쩍슬쩍 공부중인데, 복귀해서는 큐부터 시작해서 다른 알고리즘 문항들에 손대기 시작할 것 같다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys n = int(sys.stdin.readline()) answer = 0 for _ in range(n): s ..
https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 앞서 풀어본 후위 표기식의 발전된 버전이다. 후위 표기식을 해결하지 못한 채 마주쳤으면 조금은 까다로웠을 수도 있는데, 결론적으로 꽤나 쉬운 문항이었다. 가장 어려웠던 부분이 첫 부분 알파벳에 숫자를 대입하는 부분일 정도. 아스키코드로 알파벳 값들을 계산하는 풀이들이 주를 이루던데, 아스키코드를 공부해본 적이 없어 그냥 뚝심으로 밀고 갔다. 간단하게 알파벳 리스트를 불러오는 string..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 목적지까지 걸어가는 길은 굉장히 다양하다. 이 문제의 경우 도처에 힌트들과 도구들을 직접 작성해놓고, 빙글빙글 돌아가다가 실패를 잔뜩 맛봤다. 사무실 pc에 첫 시도의 노력이 묻어있는데 호환의 문제로 개인 노트북으로 따로 글을 쓰는 중이라 완성된 코드만 올릴 수 있을 것 같다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 imp..
