본문 바로가기

파이썬62

[BOJ] 1747. 소수&팰린드롬(Python) 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. 사용 알고리즘 : 소수판별 알고리즘(제곱근까지 구함) N을 1씩 늘려가며 팰린드롬이고 소수인 조건을 만족시키는 즉시 반.. 2021. 4. 29.
[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.
[DataStructure] Python 자료구조별 시간 복잡도 정리 Python 자료구조별 시간 복잡도 정리 리스트 자료형과 메서드의 시간 복잡도 Operation Example Class Notes 1 Index l[i] O(1) 인덱스로 값 찾기 2 Store l[i] = 0 O(1) 인덱스로 데이터 저장 3 Length len(l) O(1) 리스트 길이 4 Append l.append(5) O(1) 리스드 뒤에 데이터 저장 5 Pop l.pop() O(1) 가장 뒤의 데이터 pop 6 Clear l.clear() O(1) l = [] 7 Slice l[a:b] O(b-a) 슬라이싱되는 요소들 수 만큼 비례 8 Extend l.extend(...) O(len(...)) 확장되는 길이만큼 9 Construction list(...) O(len(...)) 리스트 길이만큼.. 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] 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.

티스토리툴바