알고리즘
(Python) 백준 1436번 - 영화감독 숌
문제 링크 : https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 풀이 브루트포스 문제이다보니 실버 문제치고 풀이가 어렵지 않았다. i = int(input()) fin = 0 # 종말의 숫자 flag = 0 # 몇 번째 종말의 숫자인지 while i != flag: # 원하는 순서의 종말의 숫자에 도달할때까지 반복 fin += 1 # 0부터 하나씩 증가 시키기 if "666" in str(fin): # "666"과 비교를 위해 fin을 문자열로..
(Python) 백준 1181번 - 단어 정렬
문제 링크 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 arr = [] for _ in range(int(input())): m = input() if m in arr: continue if len(arr) == 0: arr.append(m) for i in range(len(arr)): if len(arr[i]) > len(m): arr.insert(i, m) break elif len(arr[i]) == len(m):..
계수 정렬
계수 정렬이란? 카운팅 정렬 (Counting Sort)이라고 부르기도 하는 계수정렬은 O(n)의 시간복잡도를 가지는 정렬이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다. 계수 정렬의 특징 주어진 데이터의 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 0과 양수 범위의 데이터들만 정렬할 수 있다. 데이터의 범위가 커지게 되면 소요되는 시간이 커지게 되고, 메모리가 낭비되는 문제가 발생한다. 또한 음수 범위의 데이터들은 정렬할 수 없다는 단점을 가진다. 계수 정렬의 과정 정렬되지 않은 수들을 count 배열에 몇 번씩 등장하는지 적어둔다. count 배열을 앞에서부터 순회하며 등장 횟수를 누적합으로 변경한다. 기존의 배열의 뒤에서부터 누적합 결과를 인덱스로 사..
(Python) 백준 10989번 - 수 정렬하기 3
문제 링크 : https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 원래 브론즈 문제는 포스팅하지 않으려 했으나 문제와 관련하여 정리할 개념들이 많이 있어서 풀이를 적어보려고 한다. 메모리 제한과 시간 제한이 있어 단순하게 python의 sort함수로는 이 문제를 풀 수 없어서 계수정렬을 이용하여 풀었다. count = [0] * 10001 for _ in range(int(input())): count[int(input())] += 1 for i in range..
(Python) 백준 1259번 - 팰린드롬수
문제 링크 : https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 풀이 원래 브론즈 문제는 포스팅 하지 않으려 했으나 더 좋은 코드를 만드려고 노력하였던 기록을 남기고 싶어서 순서대로 풀이를 올려보겠다. def cal(l): if len(l) == 1: return "yes" if len(l) == 2: if l[0] == l[1]: return "yes" return "no" if len(l) == 3: if l[0] == l[2]: return "yes" re..