본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준10792 - 다음 순열 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제는 어떤 수열이 주어졌을 때, 그 바로 다음 순열을 구하는 문제이다. 그냥 next_permutation()을 사용해서 풀긴 했는데, 애초에 입력으로 숫자의 범위가 10000이다. 이는 곧, 10000!를 의미하는데 제출한 코드가 운이 좋아서 통과했지만 사실 이렇게 풀면안된다. 찾아보니깐 이미 공식(?)이 있었다. 14세기에 인도의 수학자 나라야나 판디타가 고안했다는데 참 대단하다... arr[5] = [4,2,1,3,5]의 다음 순열을 구해보자. 다음.. 2020. 3. 4.
[알고리즘 문제] algospot - PICNIC https://algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요 algospot.com 입력으로 문자열의 길이가 1,000 원본 그림의 크기는 2^20 x 2^20이기 때문에 압축된 문자열을 .. 2020. 2. 26.
[알고리즘문제] 프로그래머스 - 최고의 집합 문제는 비교적 간단합니다. 다음 두 조건을 만족하는 집합을 return하면 됩니다. 입력으로 자연수의 개수 n, 합 s가 주어지고 문제의 조건은 다음과 같습니다. 1. 각 원소의 합이 S가 되는 집합 2. 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합 처음에 살짝 당황했던 부분은 s의 크기가 1억이고 자연수의 개수만 정해지고 그 자연수 경우의 수가 너무 많다는 것입니다. 그렇기 때문에 모든 경우를 검사해볼 수 없습니다. 일단 문제를 풀어보기 전에 제가 문제를 풀 수 있었던 핵심개념을 먼저 설명해 드리겠습니다. n=2, s=10일 때 나올 수 있는 모든 경우의 수와 원소의 곱을 한번 보겠습니다. 1 9 -> 9 2 8 -> 16 3 7 -> 21 4 6 ->24 5 5 ->25 -> 최대인 부분 .. 2020. 2. 13.
[알고리즘문제] 프로그래머스 -줄 서는 방법 n개의 숫자를 줄을 세울때(순열) k번째 수를 구하는 문제 입니다. 처음에 지원해주는 api로 먼저 한번 해봤는데 역시나 시간초과가 나왔습니다. 먼저 문제에서 규칙을 한번 찾아봅시다. 3개의 숫자로 만들 수 있는 조합은 아래와 같습니다. 총 만들 수 있는 경우의 수는 6가지, 즉 n!으로 표현할 수 있습니다. 같은 예로 n개의 숫자인 경우 4! = 24개가 될 수 있습니다. [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 예시에서 1이 제일 앞에 있는 경우, 2가 제일 앞에 있는 경우, 3이 제일 앞에 있는 경우는 각각 2개씩 존재합니다. 이 부분을 수학적으로 접근해보면 n! / n, (n-1)!로 표현할 수 있습니다. 이를 생각해보면 총 경우의.. 2020. 2. 13.

티스토리툴바