곽로그

문제 너무나 오랜만에 푸는 알고리즘 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 시행착오1 접근 같은 것을 포함하는 수열에서 오름차순으로 n-1개를 뽑는다. 예를 들어 연산자가 + + - - * * * / 이렇게 있는 경우, 인덱스 오름차순으로 n-1개를 뽑았다. 그런 다음 n-1개의 연산자에 대해 수열과 연산을 했다. n이 5인 경우 + + - - , + + - * 이런식으로 진행했다. 문제 / * + - 의 경우를 포함하지 못한다. 시행착오2 접..

문제 www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이 switch문을 이용해서 명령문 마다 분기하는 것까지는 다 비슷할 것 같다. 여기서는 집합을 어떻게 표시할 것인지에 따라서 풀이가 달라질 것 같다. "S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다."를 보고서 HashSet으로 풀어야 겠다 생각했다. x가 이미 있는 상태에서 add를 해도 무시되기 때문이다. 나머지 명령어들도 hash에서 제공되는 메서드를 이용하면 쉽게 풀 수 있다. 이전에는..

문제 www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이1 재귀함수를 생각했다. 만약 방문한 도시의 수가 N개이면 최솟값을 구한다. 방문한 도시의 수가 N개가 아니면 다음 방문할 도시를 찾는다. 이때 다음 방문할 도시는 이전에 방문한적이 없는 도시이면서, 현재방문한 도시와 연결되어 있어야 한다. public static int getMinCost(int currentNode, int visitCount){ if(..

문제 www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 이 문제는 www.acmicpc.net/problem/15663이 문제를 푸는 것에 각 요소 사이값의 최대를 구하는 것만 추가 된 문제다. n의 최대값이 8이므로 모든 1부터 n을 나열한 모든 경우에 대해서 각 요소 사이값을 구하면 된다. 입력으로 주어지는 배열을 저장하는 int[] 배열을 numArray, numArray를 정렬할 배열을 candiArray라고 하자. 그리고 numArray의 인덱스 0~ n-1 ..

문제 www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 풀이 alwaysbemoon.tistory.com/268 의 풀이와 반대로 생각하면 된다. 어떤 수열의 이전 수열을 구하기 위해서 @$% ---의 수열에서 @$% 으로 시작하는 첫번째 순열을 구한다. 그 다음 그 이전 수열은 ---에서 %보다 큰 수들 중 최소값과 %의 위치를 바꾼다. -%-에 대해 내림차순 정렬을 하면 @$-로 시작하는 마지막 수열을 구할 수 있다. 코드 import java.io.BufferedReader; import java.io.Buff..

문제 www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 풀이 1 2 3 4 를 순서대로 나열해보자 1 2 3 4 1 2 4 3 1 3 2 4 . . . 4 3 2 1 순으로 나열한다. 이때 1 2 4 3 의 다음 순열인 1 3 2 4 를 보자. 1 2 4 3 의 다음 순열이 왜 1 3 2 4 인지를 보면, 1 2 4 3 이 1 2 - - 으로 시작하는 마지막 순열이기 때문이다. 수를 나열 할때 1 --- 를 나열하고 2---를 나열한다. 1 ---에서도 1 2 --을 나열한다음 1 3 --을 나열한다. 1 2 --로 시..

문제 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 풀이 이분그래프가 뭔지 모르겠어서 위키에 있는 설명 보고 풀었다. ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 2색변 이분 그래프의 예 그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을..

문제 www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 풀이 부등호가 N개 있으면 숫자는 N+1개를 뽑아야 한다. 이때 숫자는 중복을 허락하지 않는 수라고 했으므로 N과 M(1)과 같은 문제다. 중복되지 않는 수 N+1개를 뽑았다면, 입력받은 부등호와 비교를 한다. 비교를 하고 부등호 수열인 경우, int배열에 있는 숫자를 StringBuffer로 변환한 뒤 ArrayList validArray에 add하였다. validArray를 정렬하고 나서 맨 앞에 있는 값이 최소값이..