본문 바로가기

BOJ67

[BOJ] 4358. 생태학(Python) 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 사용 자료구조 : 해시(Hash) 파이썬 코드는 다음과 같다. from sys import stdin input = stdin.readline nameInfo = dict() # 나무 이름 등장 횟수 nameSet = set() # 중복 없앤 이름 리스트 cnt = 0 while.. 2021. 4. 29.
[BOJ] 9935. 문자열 폭발(Python) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 처음 풀었을 때 시간초과 나서, 다른 분 풀이 보고 스택을 써야한다는 아이디어를 얻어 다시 코딩해서 pass했다. 사용 자료구조 : 문자열 + 스택 코드 설명 아래 주석에 달아놓았다. 핵심 아이디어는 폭발 문자열의 마지막 글자가 현재 탐색하는 문자와 같고, 폭발 문자열과 스택에 폭발 문자열의 길이만큼의 문자열이 같다면, 스택에서 폭발 문자열의 길이만큼 pop() 해준다. 마지막 문자까지 모든 탐색이 끝났을 때, 스택에 남아있는 문자가 있다면 스택을.. 2021. 4. 27.
[BOJ] 1316. 그룹 단어 체커(Python) 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 사용 알고리즘 : 문자열 + 구현 코드 설.. 2021. 4. 27.
[BOJ] 13335. 트럭(Python) / Simulation 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 설명다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라. # 21분 소요 사용 알고리즘 : 문제에서 주어진 그대로 구현하는 Simulation 문제 전체적인 흐름은 아래 코드에 주석으로 달아놓았고, solve() 함수에서 중요! 표시한 부분을 보면, trucks에서 맨 앞의 트럭이 다리로 이동할 수 있는 .. 2021. 4. 21.
[BOJ] 3980. 선발 명단(Python) / DFS, Backtracking 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 11개의 포지션에 11명의 선수를 채웠을 때, 능력치의 합의 최댓값을 구하는 문제. # 42분 소요. (한 번에 통과, PyPy3 제출 기준 시간 1위 달성했다!) 사용 알고리즘 : Backtracking, DFS 순열 구하기 무난하게 순열 구하는 dfs 재귀로 접근해 가지치기하여 가짓 수를 쳐냈다. 원래 dfs 순열로는 11개 자리에 11명을 각각 다른 자리에 배치하는 경우의 수가 39,916,800개가 나오는데, Backtracking으로 가지치기하면 경우의 수가 1824개로 확연히 준다. perm 함.. 2021. 4. 15.
[BOJ] 1941. 소문난 칠공주(Python) / DFS, Backtracking 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 전형적인 Backtracking 문제이다. 내가 매우 취약한 알고리즘.. 이번 주는 백트래킹/DFS 문제를 파보자 사용 알고리즘 : Backtracking / DFS 재귀로 조합 구현 조합으로 접근해야한다는 것을 생각도 하지 못했다. 가짓 수가 너무 많을 것이라 생각했는데, 백트래킹으로 Y를 4번 이상 만났다면 return하여 가지치기로 어느정도 거를 수 있다. dfs 함수로 25개 칸에서 7개 칸을 선택하는 조합을 구현한다. 이 때, 7개 숫자를 리스트로 담는데,.. 2021. 4. 13.

티스토리툴바