본문 바로가기

Algorithm

 (19)
[백준 5557] 1학년 python 문제 풀이 이 문제는 DP로 풀어야한다. 어떤 구조로 정보가 저장될 수 있을지 살펴보면 왜 DP로 풀어야하는지 시각적으로 알 수 있다. 0부터 20사이의 숫자만 나와야하므로 DP는 크기가 21인 배열(0포함)을 사용할 수 있다. 21개의 배열에 루프를 돌며 다음 값을 + - 해서 다음 배열에 저장해주면 된다. 이때 상근이는 20을 넘는 수는 모른다는 조건이 있으므로 배열을 넘어가는 수는 저장하지 않는다. 이를 코드로 구현하면 아래와 같다. 통과된 풀이 import sys n = int(input()) arr = list(map(int, sys.stdin.readline().split())) dp = [[0] * 21 for _ in range(n)] # 첫 번째 수는 무조건 저장해야하니까 dp[0][ar..
[Programmers] 가장 큰 수 python (정렬) 문제 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 접근 방법 빈 문자열로 수를 초기화 ..
[Programmers] 체육복 python (Greedy) 문제 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution ..
[Programmers] 완주하지 못한 선수 python (Hash) 문제 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한 사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 입출력 예 설명 예제 #1 "leo"는 참여자 명단에는 있지만, 완주..
[Algorithm] 가장 간단한 알고리즘 - 브루트 포스법 브루트 포스법 : brutu는 무식한, force는 힘이라는 뜻이다. 무식하게 힘으로 해결하는 방법. 즉, 가장 간단한 알고리즘으로 가능한 모든 경우의 수를 검사하는 알고리즘이다. 브루트 포스법은 문자열 검색 중 가장 가장 기초적이고 단순한 알고리즘이다. 문자열 검색 string searching 이란 ? : 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것. 텍스트 text : 검색되는 쪽의 문자열 패턴 pattern : 찾아내는 문자열 ex. 문자열 'yena'에서 'na'를 검색하면 성공, 'bibi'에서 'na'를 검색하면 실패. 여기서 텍스트는 'yena', 'jiyun'이 되고, 패턴은 'na'가 된다. 브루트 포스법 brute fo..
[백준 12904] A와 B python 문제 문자열 S, T가 주어질 때 2가지 규칙에 의해 S를 T로 변경할 수 있는지 출력하는 문제이다. 풀이 기본 아이디어 S의 길이 마지막 문자열이 A라면 A를 제거한다. 문자열을 뒤집고 뒤에 B를 추가한다. -> 마지막 문자열이 B라면 B를 제거하고, 문자열을 뒤집는다. 파이썬 구현 문자열을 뒤집고, 마지막 문자열을 제거하는 동작을 해야하므로 리스트 이용 통과된 풀이 s = list(input()) # 문자열 S t = list(input()) # 문자열 t success = False while len(s) != len(t): if t[-1] == 'A': # 규칙 1 t.pop() elif t[-1] == 'B': # 규칙 2 t.pop() t = t[::-1] if s == t: # 성공 여부 체..
[Algorithm] 재귀 Recursion 재귀 recursion 재귀 알고리즘의 기본 재귀란 ? 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀를 사용하면 프로그램을 간결하고 효율성 좋게 작성할 수 있음 재귀 호출 recursive call '자기 자신과 똑같은 함수'를 호출한다. ex - 팩토리얼 구하기 factorial() 함수는 n - 1의 팩토리얼 값을 구하기 위해 다시 자기 자신과 똑같은 factorial() 함수를 호출한다. def factorial(n: int) -> int: """양의 정수 n의 팩토리얼을 구하는 과정""" if n > 0: return n * factorial(n - 1) else: return 1 if __name__ == '__main__': n = int(input('출..
[백준 9020] 골드바흐의 추측 python 문제 문제 요약 : 모든 짝수를 두 소수의 합으로 나눌 수 있다는 골드바흐의 추측에 맞게 주어진 짝수 n에 대하여 골드바흐 파티션을 출력하는 문제이다. 풀이 기본 아이디어 : n을 반으로 나눈 다음 n에서 반으로 나눈 수와 가까운 소수를 뺐을 때 나머지가가 소수이면 골드바흐 파티션이 된 것 ! 소수인지 판별 에레토스테스테네스의 체 사용 ( 백준 1929 번 ) 루프 사용 반복 변수 : tmp , n//2 부터 시작 반복 변수 갱신 : 0이 되기 전 까지 -1 종료 조건 : n- tmp 했을 때 소수가 나온다. 반(n // 2) 만 체크하는 이유 가장 차이가 적은 파티션을 찾아야 하니까. 0부터 (n // 2)까지 반만 체크해도 n-tmp가 소수인지 체크하기 때문에 결국 0부터 n까지 전체가 다 체크되니까..
반응형

티스토리툴바