Study 200

[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘? 최적해를 구하는 데 사용되는 알고리즘의 한 유형으로 문제를 해결하는 과정에서 현재 상황에서 가장 좋다고 생각되는 선택을 반복적으로 하는 방식이다.즉 전체적인 최적해를 고려하지 않고 현재 단계에서 가장 좋은 선택을 하는 것을 반복하여 최종적인 해결책을 찾는 알고리즘이다.이 알고리즘은 각 단계에서의 최적 선택이 결국 전체 문제에 대한 최적 해결책을 보장할 수 있을 때 유효하다.  특징탐욕적 선택 속성 (Greedy Choice Property): 각 단계에서 현 시점에서 가장 최적인 선택을 한다.최적 부분 구조 (Optimal Substructure): 문제의 최적 해결 방법이 부분 문제들의 최적 해결 방법으로 구성될 수 있다.장점간단하고 직관적: 구현이 간단하고 이해하기 쉬운 편빠른 수행..

알고리즘 2024.07.17

[Python] 16435번 스네이크버드

✏️ 문제 문제 파악배열을 정렬하면 쉽게 풀 수 있는 문제이다. 과일의 높이를 넣은 배열을 정렬한 후에 과일의 높이와 스네이크버드의 길이가 같으면 먹을 수 있기 때문에 길이 += 1 하고 아니면 break 해서 스네이크버드의 길이를 출력하는 방향으로 코드를 짰다. 알고리즘그리디 알고리즘정렬  코드n, l = map(int, input().split())apple = list(map(int, input().split()))apple.sort()for i in range(len(apple)): if apple[i] > l: break else: l += 1print(l)

PS/백준 2024.07.17

[Python] 1417번 국회의원 선거

✏️ 문제 문제 파악득표수 배열을 A로 가정하자. 처음엔 if max(A) > A[0] 이라는 조건문이 true면 최댓값을 가지고 있는 후보의 득표수를 -1 하고 A[0]에 득표수 +1, 매수해야 하는 사람수 +1 하는 방향으로 코드를 짰다.이렇게 짜니 무한루프를 돌고 있었고 생각해보니 다솜이가 원하는 A[0]이 배열의 최댓값이 되면 A[0]의 값이 계속 -1, +1, -1, +1 을 반복하게 되기 때문이었다. 그래서 max(A) == A[0] 라는 조건문을 사용하여 코드를 새로 짜니 해결되었다.또한 최대 득표수를 가지고 있는 후보에 A[0]가 있으면서 (and) 여러 후보라면 1명만 매수하면 되므로 매수해야 하는 사람을 +1 해주었다. 알고리즘그리디 알고리즘구현자료 구조시뮬레이션우선순위 큐  코드n =..

PS/백준 2024.07.17

[Python] List Comprehension (리스트 컴프리헨션) 에 대해

List Comprehension (리스트 컴프리헨션) 이란?파이썬에서 리스트를 간결하게 생성하는 방법 중 하나이다. 리스트 컴프리헨션을 사용하면 기존 리스트를 기반으로 새로운 리스트를 만들거나 특정 조건에 맞는 요소들로 리스트를 생성할 수 있다. 리스트 컴프리헨션은 코드의 가독성을 높이고 작성하는 코드를 줄이는 데 매우 유용하다.기본 구조[표현식 for 항목 in 반복가능한객체 if 조건문] 예제기본 리스트 컴프리헨션numbers = [1, 2, 3, 4, 5]# 기존 리스트의 각 요소에 2를 곱한 새로운 리스트를 만듦squared_numbers = [x * 2 for x in numbers]print(squared_numbers) # [2, 4, 6, 8, 10] 조건을 포함한 리스트 컴프리헨션# ..

Python 2024.07.16

[Python] String (문자열) 다루기 (1)

String (문자열) 이란?문자의 연속으로 텍스트 데이터를 저장하는 데 사용된다.파이썬에서는 작은 따옴표(') 또는 큰따옴표(")로 문자열을 정의할 수 있다. 특징불변성: 문자열은 생성된 후 수정할 수 없습니다. 예를 들어, 문자열의 일부 문자를 변경할 수 없다.인덱싱과 슬라이싱: 문자열의 각 문자는 인덱스로 접근할 수 있습니다. 인덱스는 0부터 시작한다.text = "Hello"first_char = text[0] # 'H'substring = text[1:4] # 'ell' 메소드1. 문자열 변형 및 조작 함수replace(): 문자열 내에서 특정 문자열을 다른 문자열로 교체text = "Hello, World!"new_text = text.replace("World", "Python") #..

Python 2024.07.16

[Python] List (리스트) 다루기 (1)

List (리스트) 란?원소들이 연속적으로 저장되는 형태의 자료형을 뜻한다. 대괄호([ ])로 감싸서 나타내며 안에는 0개 이상의 원소가 저장할 수 있다. 또한 리스트도 저장할 수 있다.파이썬에서는 저장되는 요소들이 모두 같은 자료형일 필요는 없다. 특징가변성: 리스트는 생성된 후 요소를 추가, 수정, 삭제할 수 있다.인덱싱과 슬라이싱: 리스트의 각 요소는 인덱스로 접근할 수 있습니다. 인덱스는 0부터 시작한다.numbers = [1, 2, 3, 4, 5]first_element = numbers[0] # 1sublist = numbers[1:4] # [2, 3, 4] 메소드1. 리스트 생성 및 초기화 함수생성: list(), [ ]empty_list1 = []empty_list2 = list..

Python 2024.07.16

[Python] 2847번 게임을 만든 동준이

✏️ 문제 문제 파악마지막에 오는 점수가 제일 큰 점수가 되어야 하므로 배열을 끝에서부터 훑으며 마지막 점수를 기준으로 앞에 있는 점수들을 바로 뒤에 있는 점수보다 1점 더 작은 점수로 감소하는 방향으로 코드를 짰다. 알고리즘그리디 알고리즘  코드n = int(input())de = 0score = []for i in range(n): score.append(int(input()))for i in range(n-1, 0, -1): # 뒤에서부터 읽어오기 if score[i-1] - score[i] > 0: # 크면 바로 뒤에 있는 점수보다 1점 작은 점수가 되도록 조정 de += (score[i-1] - score[i] + 1) score[i-1] = score[i] - 1 elif..

PS/백준 2024.07.16

[Python] 1213번 팰린드롬 만들기

✏️ 문제 문제 파악일단 팰린드롬이 되려면 모든 알파벳이 짝수 개일 때하나의 알파벳만 홀수 개고 나머지는 짝수 개일 때위의 조건이 성립하지 않으면 "sorry ~" 출력   알고리즘그리디 알고리즘구현문자열  코드name = input() count = {}keys = sorted(list(set(name)))odd = []result = ''for key in keys: cnt = name.count(key) count[key] = cnt if cnt % 2 != 0: odd.append(key)if len(odd) > 1: print("I'm Sorry Hansoo")else: for key in keys: result += key * (count[key] // 2) if odd ..

PS/백준 2024.07.16

[Python] 14916번 거스름돈

✏️ 문제 문제 파악이거 설탕 배달이랑 똑같은 알고리즘이다. 보자마자 설탕 배달 생각남..최소 개수를 출력해야 되므로 큰 단위인 5원부터 비교하지만 5원보다 크다고 무조건 5원으로 나누도록 코드를 짜지 않는 게 포인트이다.  예제1의 경우 5원으로 나누게 되면 5원 2개가 나오고 나머지가 3이므로 거슬러 줄 수 없다고 나올 수 있기 때문이다. 이 점을 잘 생각하여 코드를 작성해야 한다. 알고리즘그리디 알고리즘다이나믹 프로그래밍수학  코드n = int(input())count = 0while n >= 0: if n % 5 == 0: # 5원으로 나눴을 때 나머지가 없는 경우에만 5원으로 나눔! count += int(n // 5) print(count) break n -= 2 ..

PS/백준 2024.07.16

[Python] 1049번 기타줄

✏️ 문제 문제 파악min(6개입 가격)과 min(낱개 가격) 비교if min(6개입 가격) > min(낱개 가격) * 6 : 낱개로 전부 사는 게 이득if min(6개입 가격)  min(낱개 가격) * 6 : 6개 단위는 6개입으로 사는 게 이득if min(6개입 가격) 6개입을 하나 더 사는 게 이득if min(6개입 가격) > min(낱개 가격) * 남은 개수(6개 이하) : 낱개로 사는 게 이득 알고리즘그리디 알고리즘수학  코드n, m = map(int, input().split())brand = []money = 0for i in range(m): brand.append(list(map(int, input().split()))) brand.sort()min_value = min(min(s..

PS/백준 2024.07.15