본문 바로가기

Computer Science/알고리즘

(17)
[백준 알고리즘] 9095번 1,2,3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 3 4 7 10 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 7 44 274 풀이 이 문제는 1부터 입력한 n값까지 1, 2, 3만을 사용하여 구하는 입력한 n값을 구하는 방법의 개수를 구해야 한다. 처음 문제를 보고 ..
[백준 알고리즘] 1932번 정수 삼각형 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 30 ..
[Programmers] Level3 - 최고의 집합 (연습문제) Python 풀이 문제 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다. 집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요. 제한사항 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) ..
[Programmers] Level3 - 하노이의 탑 (연습문제) Python 풀이 문제 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다. 한 번에 하나의 원판만 옮길 수 있습니다. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다. 1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소..
[Programmers] Level1 - 2016년(연습문제) Python 풀이 문제 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN, MON, TUE, WED, THU, FRI, SAT입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 TUE를 반환하세요. 제한사항 2016년은 윤년입니다. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다) 입출력 예 a b result 5 24 TUE 풀이 이 문제는 2016년 1월 1일 시작요일과 1년이 366일인 윤년을 사용하여 문제를 풀이하면 쉽게 해결할 수 있다. 가장 먼저..
[Programmers] Level1 - 완주하지 못한 선수(해시) Python 풀이 문제 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion return [leo, kiki, ede..
[Programmers] Level1 - 수박수박수박수박수박수?(연습문제) Python 풀이 문제 길이가 n이고, 수박수박수박수....와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 수박수박을 리턴하고 3이라면 수박수를 리턴하면 됩니다. 입출력 예 n return 3 수박수 4 수박수박 풀이 이 문제는 예시로 알려준 입출력을 보게 되면 힌트를 쉽게 얻을 수 있다. n은 자연수이며, 반환되는 값은 n의 값에 따라 '수' / '박'으로 끝이 나게 된다. 즉 n이 홀수인 경우 '수'로 끝이 나고 n이 짝수인 경우 '박'으로 끝이 나게 됨을 쉽게 알 수 있다. 따라서 n번 반복하여 홀수/짝수를 구분하여 값을 반환하면 해결이 된다. 코드 def solution(n): answer = '' for i in range(n): if i % 2 == 0: a..
[백준 알고리즘] 1929번 소수 구하기 오늘은 백준 알고리즘 사이트에 올라와 있는 1929번 문제를 해결하고 글을 작성하고자 한다. 본 문제는 Python3로 풀이를 진행 하였다. 문제 문제을 보면 M~N까지의 숫자 중 소수를 구하는 문제임을 충분히 알 수 있다. 풀이 우선 문제에서 보면 알 수 있듯이 소수를 구하는 코드를 작성하면 된다. 소수를 Python코드로 구현 시 다양하게 구현할 수 있지만, 이 문제의 경우 백준 알고리즘에 나와 있는 분류 중 하나인 방법을 사용해보려고 한다. 백준 알고리즘 홈페이지에서는 이 문제에 대한 분류를 다음과 같이 하고 있다. 따라서 이 문제는 '에라토스테네스의 체'공식을 이용하면 쉽게 풀이할 수 있다. 에라토스테네스란? - 수학에서 소수를 찾는 방법 중 하나이다. 자세한 설명은 위키백과에 자세히 나와 있기 ..