본문 바로가기

TIL

 (53)
백준 3055 탈출(python) 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS방식으로 문제에 접근했습니다. 물과 고슴도치 둘 다 움직이는데, 고슴도치는 물이 있는 곳으로 갈 수 없으니, 물을 먼저 움직여서 이차원 리스트에 표시해 두고, 그다음 고슴도치를 움직여 주었습니다. 물과 고슴도치 두 개의 큐를 사용하였습니다. 시작할 때 물의 위치와 고슴도치의 위치를 받아서 큐에 각각 넣어줍니다. 물은 여러 곳에 존재할 수 있습니다. 물이 갈 수 있는 곳을 찾아서 각 방향으로 움직여서..
백준 1918 후위 표기식(python) 문제 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 스택에 좀 더 익숙해지기 위해 푼 문제, 생각보다 구현이 까다로워서 좀 걸린 것 같다. 조건에 맞게 경우를 좀 나눠 주어야 한다. 먼저 알파벳이나 여는 괄호 라면 그대로 스택에 넣어준다. 닫는 괄호일 때는 스택에서 여는 괄호가 나오기 전까지 pop 시켜주며 출력해준다. 연산자는 우선 순위에 따라 나눠 주는데, 우선순위가 높은 '*'와 '/'가 스택의 top 값에 있을 때 들어오는 값..
백준 2812 크게 만들기(python) 문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 스택을 사용하여 푸는 문제였습니다. 접근 방식이 히스토그램에서 가장 큰 사각형 만들기 문제를 스택으로 풀 때 와 비슷해서 정리해 보았습니다. 이 문제도 모노톤 스택 형태 내림차순으로 만들어 줍니다. 절차는 다음과 같습니다. 주어진 숫자를 문자열로 형태로 처음 부터 순회하면서 스택에 넣어줍니다 스택에서 pop 하는 조건은 스택의 top 값 보다 현재 순회하는 위치의 값이 더 크다면 st을 pop 해주고 현재 값을 넣어 줍니다. pop 할때 문제의 조건으로 주어진 지울 수..
백준 6549 히스토그램에서 가장 큰 사각형(python) 문제 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 정글에서 Week2 주제 중 분할정복에 해당하는 문제 였다. 분할 정복 접근법 말고도 여러 방법으로 풀어 봤는데, 그 중 스택을 사용한 방식이 인상적이였다. 그래서 스택으로 푼 풀이를 소개하려 한다. 먼저 효율성을 따지지 않고 완전 탐색 형식으로 원소 마다 앞뒤로 확장 하면서 값을 갱신해 나갈 수 있는데, 이렇게 하면 O(n^2) 의 ..
백준 22860 폴더 정리(python) 문제 https://www.acmicpc.net/problem/22860 22860번: 폴더 정리 (small) main 폴더 하위에는 FolderA 폴더 하위에 있는 File1, File2, FolderB 폴더 하위에 있는 File1, File3이 있다. 파일의 종류는 File1, File2, File3 총 3가지이고, 파일의 총 개수는 File1, File2, File1, File3 총 4개이다. mai www.acmicpc.net 정글에서 알고리즘 Week1 주제 중에 재귀가 있었는데, 재귀 복습도 하고 파이썬에 익숙해지기 위해서 따로 풀어 봤다. 기본적인 전략은 재귀이긴 한데, 주어진 조건에 맞게 파일 구조를 어떻게 구현해 내냐가 중요한 것 같다. 나는 폴더와 파일을 같이 한 폴더에 집어넣어 주는..

티스토리툴바