본문 바로가기

파이썬26

[백준] 32930번 슈팅 연습 - Python(1편) 문제 링크: https://www.acmicpc.net/problem/32930아래는 문제 사진입니다.더보기   이 문제는 처음에 N개의 과녁이 주어지고, 그 중 원점에서 가장 멀리 있는 과녁을 선택하여 커서가 해당 과녁으로 이동합니다. 이동한 후에는 그 과녁을 삭제하고, 남은 M개의 과녁에서 인덱스가 앞인 순서대로 새로운 과녁을 추가하여 다시 N개의 과녁을 구성합니다. 이후 현재 커서에서 가장 멀리 있는 과녁을 찾아 이동하는 과정을 M번 반복하며, 이때 얻는 점수는 이동한 거리의 제곱입니다. 이를 바탕으로 문제 해결 과정을 다음과 같이 정리할 수 있습니다.입력을 받습니다.원점에서 가장 멀리 떨어져 있는 과녁을 찾아 이동합니다.점수를 기록하고 해당 좌표를 삭제합니다.M개의 과녁에서 가장 앞에 있는 요소를.. 2024. 12. 20.
[백준] 7795번 먹을 것인가 먹힐 것인가 - Python(1편) 아래는 문제와 링크입니다.더보기문제 링크: https://www.acmicpc.net/problem/7795 코드를 먼저 보고 이 문제에서 얻어갈 점을 확인해 보겠습니다.from bisect import bisect_leftT = int(input())for _ in range(T): N, M = map(int, input().split()) A = sorted(map(int, input().split())) B = sorted(map(int, input().split())) count = sum(bisect_left(B, a) for a in A) print(count) 1. **이진 탐색의 활용**: 정렬된 배열에서 특정 값보다 작은 원소의 개수를 세는 데 이.. 2024. 12. 16.
[백준] 20920번 영단어 암기는 외로워 - Python(1편) 아래는 문제와 링크입니다.더보기 코드를 먼저 보고 살펴보겠습니다.import sysfrom collections import Counterinput = sys.stdin.readlineN, M = map(int, input().split())words = [word.strip() for _ in range(N) if len(word := input().strip()) >= M]word_counts = Counter(words)result = sorted(word_counts, key=lambda x: (-word_counts[x], -len(x), x))print(*result, sep="\n") 일단 이 코드에서 얻을 부분은 아래와 같습니다. 1. 바다코끼리 연산자(할당 표현식 연산자) 사용   - '.. 2024. 12. 15.
[백준] 1449번 수리공 항승 - Python(1편) 처음에는 틀린 코드를 확인하고, 후에 수정하는 방법으로 살펴보겠습니다. 아래는 문제입니다.더보기 일단 처음 제출했던 틀린 코드를 확인해 보겠습니다.N, L = map(int, input().split())data = list(map(int, input().split()))data.sort()stack = 0left, right = 0, 0while left구멍의 위치를 처리하기 위해 투 포인터 알고리즘을 사용하려 했었습니다만, 위 코드에는 몇 가지 논리적 오류가 있었습니다.일단 코드 의도를 확인해 보겠습니다.입력 및 정렬:N과 L을 입력받고, 구멍의 위치를 담을 리스트를 생성 및 정렬하려 했습니다.변수 초기화stack은 필요한 테이프의 개수를 세기 위한 변수입니다.left와 right는 두 포인터로, 투.. 2024. 12. 14.
[백준] 1940번 주몽 - Python(1편) 이번 글에서 알고리즘 설계 방법 중 하나인 투 포인터 기법을 활용하여 문제를 해결했습니다. 이 알고리즘은 이중 반복문을 피하고 시간 복잡도를 O(N)으로 줄여 효율성을 크게 높이는 방식으로, 불필요한 연산을 제거하고 주어진 조건을 효과적으로 활용했습니다. 아래는 백준 문제입니다. 사진을 클릭하면 해당 문제 페이지로 넘어갑니다.더보기 이 문제의 전체 코드를 확인해 보고, 자세히 분석해 보도록 하겠습니다.import sysinput = sys.stdin.readlineN = int(input())M = int(input())data = list(map(int, input().split()))data.sort()def partial_sum(data, M): left, right = 0, len(data).. 2024. 12. 12.
병합 정렬 쉽게 배우기: 재귀 호출과 병합 과정을 시각적으로 따라가기 병합 정렬(Marge Sort)은 분할 정복 알고리즘에 기반한 정렬 알고리즘 중 하나로, 안정적이고 효율적인 정렬 방식입니다.이번 포스트에서는 앞에서 병합 정렬 코드에 대해 알아보고 뒤에서는 병합 정렬을 시각화한 글을 보고 병합 과정을 따라가 볼 것입니다. 일단 병합 정렬의 핵심 3가지를 알아보겠습니다.분할(Divide)배열(또는 리스트)을 절반씩 나눕니다.나누는 과정을 재귀적으로 반복하여, 크기가 1인 배열로 쪼갭니다.크기가 1인 배열은 이미 정렬된 상태라고 가정합니다.정복(Conquer)작은 두 배열을 비교하면서 정렬하여 병합(Marge)합니다.병합 과정에서 두 배열을 한 번에 순회하며, 각 리스트의 첫 번째 요소를 비교하여 더 작은 값을 새로운 리스트에 추가하는 방식으로 진행합니다.병합(Merge).. 2024. 12. 12.
[백준] 10825번 국영수 - Python(1편) 아래는 백준 10825번 문제입니다. 클릭하면 문제풀이 링크로 넘어갑니다.더보기이 문제는 학생들의 이름과 국어, 영어, 수학, 점수를 입력받아 조건에 따라 정렬한 뒤 이름만 출력하는 문제입니다.국어 점수가 높은 순서로 정렬합니다.국어 점수가 같다면 영어 점수가 낮은 순서로 정렬합니다.영어 점수도 같다면 수학 점수가 높은 순서로 정렬합니다.수학 점수까지 같다면 이름을 사전순으로 정렬합니다.이 문제를 해결하기 위해, Python의 기본 정렬 함수인 sorted()를 사용했습니다. sort()와 sorted()는 Timsort 알고리즘을 기반으로 하여 선형 로그 시간인 O(n log n)의 시간 복잡도를 갖습니다. 파이썬 코딩 테스트를 위한 시간 복잡도 이해하기코딩 테스트를 공부하다 보면 시간 복잡도라는 말이.. 2024. 12. 12.
[백준] 11656 접미사 배열 - Python(1편) 더보기더 보기를 누르면 백준 11656번 문제가 나옵니다. 제가 사용한 문제 해결을 위한 코드의 핵심 로직은 아래와 같습니다.deque를 이용한 접미사 생성입력 문자열을 deque로 변환합니다.deque의 특성을 통해 왼쪽 요소를 하나씩 제거하면서 각 단계의 deque 내용을 문자열로 변환하여 저장합니다.이 과정을 통해 모든 가능한 접미사를 생성합니다.생성된 접미사 정렬생성된 접미사들을 사전 순으로 정렬합니다.전체 코드를 살펴보고 단계별로 분석해 보겠습니다.from collections import dequeS = input()dq = deque(S)data = []for _ in range(len(S)): data.append("".join(dq)) dq.popleft()result = so.. 2024. 12. 11.
Counter 클래스: 코딩 테스트를 위한 효율적인 요소 빈도 계산 도구 코딩 테스트 문제를 풀다 보면 문자열이나 배열의 요소 빈도 계산에 Counter라는 collections 모듈의 클래스를 사용하는 경우를 종종 확인할 수 있습니다. Counter 클래스의 주요 특징과 사용법에 대해 알아보도록 하겠습니다. 생성 예시 및 설명from collections import Counter# 문자열로부터 생성c1 = Counter('gallahad')print(c1) # Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})# 리스트로부터 생성c2 = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])print(c2) # Counter({'blue': 3, 'red': 2, 'green': 1}).. 2024. 12. 11.
[백준] 2108번 통계학 - Python(1편) 문제 링크: https://www.acmicpc.net/problem/2108 이 문제를 풀기 위해 우선 문제를 분석해 보겠습니다. 문제 개요N개의 수가 주어졌을 때, 다음 네 가지 통계값을 구하는 프로그램을 작성해야 합니다.산술평균중앙값최빈값범위입력첫째 줄에 수의 개수 N (1 ≤ N ≤ 500,000)이 주어집니다. 수가 큰 만큼 input() 함수를 재정의 하도록 하겠습니다. N은 홀수입니다.중앙값을 계산하기 편리하게 하기 위해 N의 값을 홀수로 지정한 것 같습니다.출력네 가지 통계값을 각각 한 줄에 하나씩 출력해야 합니다.그냥 print() 함수를 여러 번 사용하기보다 sep="\n"을 사용해서 한 번에 작성하겠습니다.세부 요구사항산술평균: N개의 수들의 합을 N으로 나눈 값을 첫째 자리에서 반올.. 2024. 12. 11.

티스토리툴바