본문 바로가기

백준

 (6)
백준 2617 구슬 찾기(python) 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 그래프 탐색으로 접근할 수 있는 문제입니다. DFS, BFS 어떤 것을 사용해도 무방하지만 저는 플로이드-워샬이 먼저 떠올랐기 때문에 이 방식으로 풀어보았습니다. 출력해야 되는 값이 무게가 절대로 중간값이 될 수 없는 구슬의 개수를 세는 문제였습니다. 풀이 과정은 다음과 같습니다. 먼저 입력으로 들어오는 구슬 번호대로 무게 순서를 지켜 관계를 2차원 리스트에 1로 표시해 줍..
백준 3055 탈출(python) 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS방식으로 문제에 접근했습니다. 물과 고슴도치 둘 다 움직이는데, 고슴도치는 물이 있는 곳으로 갈 수 없으니, 물을 먼저 움직여서 이차원 리스트에 표시해 두고, 그다음 고슴도치를 움직여 주었습니다. 물과 고슴도치 두 개의 큐를 사용하였습니다. 시작할 때 물의 위치와 고슴도치의 위치를 받아서 큐에 각각 넣어줍니다. 물은 여러 곳에 존재할 수 있습니다. 물이 갈 수 있는 곳을 찾아서 각 방향으로 움직여서..
백준 13334 철로(python) 문제 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 우선순위 큐를 활용하여 스위핑 방식으로 접근하였습니다. 집과 사무실 위치를 위치에 맞게 리스트에 저장해 준 다음 오른쪽을 기준으로 오름차순 정렬해주었습니다. 그 뒤 리스트에 주어진 값들을 차례로 순회하면서 주어진 철로 길이 안에 해당되면 큐에 넣어 주었습니다. 큐 최소 힙을 만들며 왼쪽 좌표만을 넣어 주었습니다. 큐에 있는 값들과 순회하면서..
백준 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 주제 중에 재귀가 있었는데, 재귀 복습도 하고 파이썬에 익숙해지기 위해서 따로 풀어 봤다. 기본적인 전략은 재귀이긴 한데, 주어진 조건에 맞게 파일 구조를 어떻게 구현해 내냐가 중요한 것 같다. 나는 폴더와 파일을 같이 한 폴더에 집어넣어 주는..

티스토리툴바