[ 백준 / Python ] 18110 - solved.ac

문제출처 https://www.acmicpc.net/problem/18110문제회고절삭평균이라는 개념을 이용해 알고리즘을 구현해야하는 문제였다. 엣지 케이스에 대한 연습과 파이썬의 round 함수의 작동원리를 배울 수 있게 되었다. 게다가 시간초과를 극복하기 위해 input 대신에 sys.stdin.readline을 써야했다. round() 함수반올림이란 수가 있을 때 5보다 작으면 내리고 5와 같거나 크다면 다음 자리에 1을 더하는 개념이다. 하지만 파이썬의 round 함수는 다르게 작동한다. 수가 5보다 작으면 내리고 5보다 클 때 올리는 것은 동일하다. 하지만 수가 5일 때 처리하는 방식이 반올림 개념과 다르다. 수가 5일 때는 앞자리가 홀수일 때 내리고 짝수일 때는 올린다. 문제접근input함수와..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 9. 21.

[ BOJ / Python ] 1181 - 단어정렬

문제출처https://www.acmicpc.net/problem/1181 걸린시간: 16분 47초 문제분석문자열이 여러개 주어졌을 때 중복되는 문자열은 제거하고 길이가 짧은 순부터 단어가 정렬하되 동일한 길이의 경우, 사전 순으로 정렬해야하는 문제다.최대 2초 내에 최대 20000개의 데이터를 처리해야하므로 알고리즘의 시간복잡도는 O(N^2)을 넘어서는 안된다.  문제접근내 접근from sys import stdininput = stdin.readlinen = int(input())my_words = [input().strip() for x in range(n)]# 사전순으로 정렬하기my_words.sort() # 문자열인 경우 사전순으로 정렬하는 듯 하다.# 길이순으로 정렬하기my_words.sort(..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 12.

[백준 16165 (실버3)] 걸그룹 마스터 준석이(파이썬)

문제출처https://www.acmicpc.net/problem/16165문제분석① 걸그룹에 대한 정보를 입력 받은 후에 ② 퀴즈의 유형에 따라 출력하는 값의 형태가 결정되는 프로그램을 구현하는 문제였다. 예를 들어, '사나'와 1을 퀴즈로 입력 받으면 '사나가 속한 그룹의 이름'을 출력해야 하고 '레드벨벳'과 0을 퀴즈로 입력받으면 '레드벨벳'에 속한 멤버들의 이름을 알파벳 순으로 출력해야한다. 퀴즈의 유형은 1과 0으로 구분된다. 1이면 멤버의 이름으로 그룹명을 찾아야 하고 0이면 그룹명으로 멤버의 모든 이름을 찾아야 한다. 문제접근dict을 활용하기로 하였다. 이름을 조회해서 관련 된 이름을 검색하기에 dict이 좋기 때문이다.  dict은 키와 값으로 이뤄진다. hash table을 파이썬에 구현..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 5. 10.

백준 10989: 수 정렬하기 3

1. 문제 https://www.acmicpc.net/problem/10989 2. 문제 해석 한줄로 구분되는 숫자를 입력 받은 후에 받은 숫자들을 정렬한 후 다시 한줄씩 출력하는 문제다. 입력 데이터의 개수는 1

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 4. 21.

LCS 문제

LCS 문제 LCS란 Longest Common Subsequence 혹은 Longest Common String 의 약자다. LCS 문제는 특정 문자가 같은 지 여부에 따라 테이블에 기록하는 형식으로 길이와 부분 문자열을 구할 수 있다. 즉, 동적계획법을 활용하여 문제를 풀 수 있다. 문제접근법 LCS 문제는 동적 프로그래밍 접근법에 따라 해결한다. 1. 문재의 해를 분석한 후 부분문제로 분할한다. 2. 부분문제의 해를 보고 큰 문제와의 관계식을 세운다.(점화식 설계) 3. 적당한 순서로 dp table을 채운다. 4. table에서 해를 계산한 후에 정확성을 증명한다.동적계획법에서 중요한 부분은 큰문제와 작은문제의 관계로부터 재귀형태를 찾아 dp table을 채우는 것이다. 정확성 증명은 테이블 채우..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 4. 8.

[파이썬] 백준 4344: 평균은 넘겠지

문제 출처 https://www.acmicpc.net/problem/4344 나의 코드 import sys input = sys.stdin.readline c = int(input()) cases = [[x for x in map(int, input().strip().split())] for _ in range(c)] for case in cases: population = case[0] scores = case[1 : len(case)] score_avg = sum(scores) / population above_avg = 0 for score in scores: if score > score_avg: above_avg += 1 result = above_avg * 100 / population pri..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 4. 3.