Python/백준 알고리즘 (파이썬)

[프로그래머스] 달리기 경주

문제 설명 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다. 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요. 제한사항 5 ≤..

재귀 함수 practice01_하노이탑

- 엘리스 자료구조의 정석) 문제 하노이의 탑 재귀알고리즘을 이용해 풀 수 있는 문제로는 하노이의 탑 이라는 퍼즐이 있습니다. 3개의 막대가 있고 가장 왼쪽 막대에는 탑의 높이만큼의 원반이 가장 큰 것부터 차례로 쌓여 있습니다. 이 하노이의 탑의 목표는 다음과 같은 조건을 지키면서 가장 왼쪽막대의 원반을 모두 가장 오른쪽으로 이동하는 것입니다. 한번에는 하나의 원반만 이동할 수 있습니다. 가장 위에 있는 원반만 이동할 수 있으며 가장 위에만 내려놓을 수 있고 중간에 끼워 넣을 수 없습니다. 큰 원반은 작은 원반 위로 갈 수 없습니다. 함수 hanoi에 탑의 높이가 입력으로 들어오면 3번으로 모든 원반을 옮기기 위해 몇 번째 기둥의 원반을 몇 번째 기둥으로 옮겨야 하는지에 대한 리스트를 반환하는 코드를 작..

동적 계획법 practice_02 가장 큰 부분 합 찾기

- 엘리스 자료구조의 정석) 문제 가장 큰 부분합 찾기 정수들의 리스트가 입력으로 들어옵니다. 이 정수들의 리스트를 일부분만 잘라내어 모두 더했을 때의 값을 부분합이라 부릅니다. 이때 가장 큰 부분합을 구해봅시다. 예를 들어, [-10, -7, 5, -7, 10, 5, -2, 17, -25, 1]이 입력으로 들어왔다면 [10, 5, -2, 17]을 모두 더한 30이 정답이 됩니다. ※입력에는 최소 하나 이상의 양수가 존재합니다. ※이 문제에는 여러 종류의 풀이법이 존재합니다. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어 봅시다. - 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def maxSubArray(nums): s=0 result=0 ..

동적 계획법 practice01_1로 만들기

백준 1436번 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 2. 내가 작성한 알고리즘 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 inp=int(input()) x=[0]*(inp+1) for i in range(2,inp+1): ..

브루트 포스 practice 03_ 덩치

백준 7568번 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 1. 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들..