문제 27277번: 장기자랑실력이 $4, 2, 3, 5, 1, 6$인 순서로 공연하면, 각 병사가 발휘할 수 있는 실력은 순서대로 $4, 0, 1, 2, 0, 5$이므로 실력의 합이 $12$인 채로 공연을 끝마칠 수 있다.www.acmicpc.net 문제 풀이max(0, 현재값-이전값)에서 최대의 효과를 발휘하려면 (현재값-이전값) > 0이고, 그것이 최대로 클 때 최대 효율을 발휘할 수 있다. 예를 들면 [1,2,3,4]가 있다면 [4,1], [3,2]을 짝지어야 최종합 4로 최댓값을 만들 수 있다. 만약 배열이 홀수일 경우 큰 수와 작은 수를 짝지은 후 남은 값을 맨 마지막에 추가해 주면 된다.import Foundation var n = Int(readLine()!)! var skills = rea..
→ Problems
문제 소개 (분할 가능한 배낭 문제) 담을 수 있는 최대 무게가 15kg 인 배낭과 함께 가치가 있는 아이템이 주어졌을 때, 배낭에 어떻게 하면 가장 비싸게 담을 수 있을까? 그리디 알고리즘 (Greedy Algorithm)을 통한 풀이 말이 거창하지 우리는 본능적으로 당연한 정답을 알고 있다. 바로 비싼 것부터 담으면 된다는 것. 이것을 그리디 알고리즘이라고 표현하기도 한다. 지금 이 순간 제일 최적인 답을 선택하는 것이다. 이런 배낭 문제처럼 단순한 문제들은 그렇다. 위의 문제를 그대로 대입하면 변수가 어떻게 주어질 줄 모르겠지만 [12, 1, 4, 1, 2]와 [4, 2, 10, 2, 1]이 주어진다면 10달러짜리 4kg, 4달러짜리 11Kg를 담아주면 된다는 결과가 나온다. 핵심 포인트는 정렬이다..
문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 간단히 설명하면 S 에서 A, B로가는 최단 거리를 구하는데 A, B가 같이 갈 수 있는 거리를 최대한 같이 간다음 따로따로 가게 되는 경우가 있다면 그 최단거리를 구하는 무제이다. 이를 문제에서는 길간의 거리를 요금, 같이 가는 것을 동승으로 표현했다. 위의 경우는 S에서 5까지 같이 이동한뒤 (34) 5에서 B까지 (46) 5에서 A까지 (2) 가는 경우가 최단거리라고 한다. 위의 길을 준다면 총 82의 최소 거리를 출력해야 하는 문제이다. 문제 풀이 두가지 방법으로 문제를 풀 수 있다...
문제 소개 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단하게 문제를 소개하면[[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]] 라는 입력값이 나온다면 이 입력값을 모두 포함하는 최소의 실수가 몇개인지 출력하는 문제이다. 아래에서는 3이라는 출력값이 나온다. 문제 풀이 아주 간단하게 접근을 했다. 우선 이런 문제들은 하나를 기준으로 정렬해주는 것이 핵심 포인트 인듯 싶다. 그 후 미사일 문제라 aim 이라는 변수를 두었고, 이 aim이라는 구간에 target이 포함된다면 상관 없고, 만약 target의 범위가 좁다면..
문제 소개 프로그래머스 - 길 찾기 게임 (이진 트리 순회 문제) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 이진 트리 순회 문제였다. 아래와 같은 트리 순회방법이 네가지가 있는데, 여기서는 전위 순회, 후위 순회를 물어보는 문제였다. 예를 들면 [5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2] 같은 노드가 주어진다면 아래와 같은 이진 트리가 만들어지고, 전위 순회, 후위 순회가 [[7, 4, 6, 9, 1, 8, 5, 2, 3], [9, 6, 5, 8, 1, 4, 3, 2, 7]] 형태로..
아래와 같은 백준 문제를 풀다가 파라메트릭 서치라는 알고리즘을 알게 되었다. 이에 관해서 정리하려고 한다. 문제 요약 1654번: 랜선 자르기첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제를 간단히 요약하자면 주어진 K개의 랜선으로 N개를 만들 수 있는 랜선의 최대 길이를 구하는 문제이다. 예시를 들면 [802, 743, 457, 539] 로 4개의 랜선의 길이가 주어지고 이 랜선들로 11개의 랜선을 만들 수 있는 랜선의 최대 길이를 구하는 문제인 것이다. 처음 문제 풀이아래처럼 아주 간단하게 랜선의..
