Python

[백준 알고리즘][파이썬/Python] 4344번: 평균은 넘겠지

문제 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. 입력 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 둘째 줄부터 각 테스트 케이스마다 학생의 수 N(1 ≤ N ≤ 1000, N은 정수)이 첫 수로 주어지고, 이어서 N명의 점수가 주어진다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 출력 각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다. 입출력 예 제출 코드 import sys n = int(input()) for i in range(n): lst = list(map(int, sys.stdin.readline().strip().split())) avg = sum(lst[..

[백준 알고리즘][파이썬/Python] 1157번: 단어 공부

문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 입출력 예 제출 코드 s = input().upper() dic = {} for i in s: if i in dic: dic[i] += 1 else: dic[i] = 1 best = [-1, ''] second = [-2, ''] for k, i in dic.items(): i..

[백준 알고리즘][파이썬/Python] 1152번: 단어의 개수

문제 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. 출력 첫째 줄에 단어의 개수를 출력한다. 입출력 예 제출 코드 s = input().strip() if len(s) == 0: print(0) else: print(s.count(' ')+1) # 실패 코드 # lst = input().strip().sp..

[자료구조][파이썬/Python] 덱 (Deque)

덱(Deque, Double Ended Queue) 덱(Dequeue)은 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다. 덱은 스택(Stack)과 큐(Queue)의 연산을 모두 지원하는 자료구조로, 양 끝에서 모두 삽입과 삭제가 가능한 큐라고 생각하면 된다. 나머지 부가적인 덱의 길이를 반환하는 연산이나 덱이 비어있는지 확인하는 연산 등은 스택과 큐에 구현되어 있는 연산들과 유사하게 구현된다. Python의 모듈을 이용하기 큐를 설명할 때 언급했지만 collections라는 모듈에 deque라는 클래스로 이미 구현되어 있다. 여기서 특별한 점은 양 끝에서 삽입과 삭제를 할 수 있어야 하므로 양방향 연결리스트(Doubly Linked List)로 구성되어 있다. 단순히 값을 삽입하고 삭..

[알고리즘][파이썬/Python] 퀵 정렬 (Quick Sort)

정의 기준 값을 중심으로 작은 원소들은 왼쪽 부분집합으로, 큰 원소들은 오른쪽 부분집합으로 분할하여 정렬하는 방식의 정렬 알고리즘 * 퀵 정렬도 분할과 정복(divide and conquer) 기법을 이용하는 정렬 알고리즘이다. 하지만 병합 정렬과 차이가 있는데, 병합 정렬이 분할 후 정복하는 원리였다면, 퀵 정렬은 정복 후 분할하는 원리의 정렬 알고리즘이다. 우선 기준 값보다 작은 원소들을 왼쪽 부분집합으로, 기준 값보다 큰 원소들은 오른쪽 부분집합으로 구분하는 정복 절차를 밟고, 기준 값을 중심으로 2개의 부분 집합으로 분할한다. 동작 방식 0. 기준 값을 보통 피벗(pivot)이라고 부르며, 선택하는 기준은 다양하겠으나 일반적으로 가장 왼쪽 원소를 피벗으로 지정한다. 본 글에서도 가장 왼쪽 원소를 ..

[알고리즘][파이썬/Python] 병합 정렬 (Merge Sort)

정의 입력 자료를 부분집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 다음에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer) 기법 중 하나로, 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식의 정렬 알고리즘 동작 방식 (2-way 병합, 오름차순 정렬 기준) 0. 일반적으로 정렬한 상태의 자료를 담기 위해 입력 자료의 크기만큼의 새로운 배열(리스트)을 선언해줌. 그러나 해당 포스팅에 기재한 소스코드는 정렬한 원소를 새로운 리스트에 담지 않고 입력값인 기존의 리스트를 재사용했음. 동작 방식에 대한 설명은 새로운 리스트를 선언했다고 가정한 채 진행. 1. 입력 자료를 두 개의 부분집합으로..

[알고리즘][파이썬/Python] 쉘 정렬 (Shell Sort)

정의 - 일정 간격(interval) 떨어져 있는 원소들끼리 부분집합을 구성한 후 각 부분집합의 원소들에 대해서 삽입 정렬을 수행하되, 간격을 줄여가며 삽입 정렬을 반복하여 전체 원소들을 정렬하는 방식의 정렬 알고리즘 * 쉘 정렬은 삽입 정렬의 문제점을 극복하기 위해 개선한 정렬 알고리즘이다. 삽입 정렬의 경우, 주어진 자료의 정렬 상태에 따라 시간 복잡도가 많이 달라졌는데, 역순으로 정렬되어 있는 형태에 가까울수록 비교횟수가 아주 많이 늘어나는 치명적인 문제점이 존재했다. 그래서 Donald L. Shell 은 '간격(interval)'이라는 개념을 도입하여 위 언급한 문제점을 극복해내는 '쉘 정렬'을 고안해냈다. 동작 방식 0. 간격(interval) h = 정렬할 배열(혹은 리스트)의 길이 % 2 ..

[알고리즘][파이썬/Python] 삽입 정렬 (Insertion Sort)

정의 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식의 정렬 알고리즘 동작 방식 0. 정렬할 배열(혹은 리스트)은 두 개의 부분집합 S와 U로 구분 * S (Sorted) : 정렬된 앞부분의 원소들 * U (Unsorted) : 아직 정렬되지 않은 나머지 원소들 1. U의 가장 앞에 있는 원소를 꺼내어 S의 마지막 원소부터 첫 번째 원소까지 대소 비교하며, S 내에 적절하게 삽입될 위치를 탐색 2. 대소 비교가 끝나면, U에서 꺼낸 원소를 탐색한 위치에 삽입 3. 그 결과, S의 원소는 하나 증가하며 U의 원소는 하나 감소 4. U가 공집합이 될 때까지 위 과정을 반복하며 정렬 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Ca..