본문 바로가기

Algorithm

백준 6603 로또 Java 2019. 6. 7. ->2019. 6. 18 수정 여러 가지의 방법으로 풀 수 있는 문제인 로또 문제이다. 우선 순열을 사용한 완전 탐색으로 푸는 방법을 정리하고 백트래킹을 사용한 완전 탐색으로 푸는 방법을 정리한다. 먼저 순열은 중복된 수가 있어도 정상적으로 작동한다. https://dundung.tistory.com/58 백준 10972 이전 순열 & 10973 다음 순열 Java 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. N=3 인경우에 사전순으로 나열하면 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 이 된다. 크기가 N인 순열의 개수는 총 N!이다. (N팩토리얼) 1 2 3의.. dundung.tistory.com 이 글에서 알아본 nextPermutation(다음 순열)을..
백준 10971 외판원 순회 2 Java 2019. 5. 31. 여러가지 방법으로 풀 수 있는 외판원 순회 2 문제를 순열을 사용한 완전 탐색으로 푸는 방법을 정리하려고 한다 문제는 n을 입력받고 n개 만큼의 도시를 전부 순서대로 이동할 때 드는 비용의 최소값을 출력하는 문제이다. 배열에 0부터 저장한다 생각하고 문제를 풀어볼 것 이다. 예제로 주어진 4 0 10 15 20 --> 0번 5 0 9 10 --> 1번 6 13 0 12 --> 2번 8 8 9 0 --> 3번 에서는 각각의 행에서 열은 j번째 행으로 이동할때 드는 비용을 말하는 것이다. 예를들어 0번에서 1번으로 갈땐 비용 w[0][1] -> 10이 들고 1번에서 2번으로 갈땐 비용 w[1][2] -> 9가 들고 2번에서 3번으로 갈땐 비용 w[2][3] -> 12이들고 3번에서 다시 0번으로 가는 비용은..
백준 1722 순열의 순서 Java 2019. 5. 29. 순열의 크기 N이 주어지고 순열이 사전순으로 정렬되어 있을 때 1번과 2번으로 나눈 문제가 주어진다. 1번의 경우에는 순열의 순서 k를 주고 k번째 순열 N개를 출력하면 된다. 2번의 경우에는 순열 N개가 주어지고 순서 k를 출력하면 된다. N의 최댓값인 20으로 20!까지 순열을 나타낼수 있으므로 순열의 순서를 미리 다 구해놓고 문제를 푸는 방식은 시간초과이다. 2번 문제는 N개의 순열의 개수가 N!개 인 점을 생각해서 문제를 풀면 된다. N = 7 {5 2 4 7 6 3 1}이 있을 때 첫자리인 5를 보면 5 전에 1로 시작하는 순열 6!개 2로 시작하는 순열 6!개 3으로 시작하는 순열 6!개 4로 시작하는 순열 6!개가 있었을 것이다. 첫자리가 5로 고정일 때 두 번째 자리인 2 전에 5 1로 시..
백준 10974 모든 순열 Java 2019. 5. 28. --> 2019. 6. 12 수정 n이 입력으로 주어지면 모든 순열을 출력하면 되는 문제이다. 다음 순열을 계속해서 구하는 방법과 백트래킹을 사용해서 구하는 방법 두 가지 방법을 알아보자. 먼저 순열을 사용한 방법이다. 크기가 n인 배열의 순열의 개수는 n!이다. n! 만큼 다음 순열을 구한 다음 계속 출력해주면 되는 문제이다. 다음 순열을 구하는 방법을 까먹었다면 https://dundung.tistory.com/58 백준 10972 이전 수열 & 10973 다음 수열 Java 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. N=3 인경우에 사전순으로 나열하면 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 이 된다. 크기가 N인 순열의 개수는 총 N!이다. (N팩토리..
백준 10972 이전 순열 & 10973 다음 순열 Java 2019. 5. 28. 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. N=3 인경우에 사전순으로 나열하면 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 이 된다. 크기가 N인 순열의 개수는 총 N!이다. (N팩토리얼) 1 2 3의 다음 순열은 1 3 2 가 되고 1 3 2의 이전 순열은 1 2 3 이 된다. 다음 순열은 찾는 방법은 int i = 배열의 크기 -1, int j = 배열의 크기 -1 일때 1. i > 0 이면서 A[i] > A[i-1]를 만족하는 카장 큰 i를 찾는다. 2. A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다. 3. A[i-1]과 A[j]를 swap한다. 4. A[i]부터 순열을 뒤집는다. 1번과 2번 모두 i와 j가 A.length-1로 초기화 되고 A..
비트마스크 2019. 5. 27. 비트마스크란 정수로 집합을 나타내는 방법이다. 포함이 되어있을 땐 1로 포함 되어있지 않을 땐 0으로 나타낸다. 570 같은 경우엔 2진수로 표현하면 1000111010(2)이다. 인덱스로 나타내면 9 8 7 6 5 4 3 2 1 0 1 0 0 0 1 1 1 0 1 0 570 = {9, 5, 4, 3, 1}을 포함하고 있는 집합이라고 할 수 있다. 길이가 N인 이진수는 0~N-1까지의 부분집합을 나타낼 수 있다. 1부터 ~ N까지의 부분집합을 나타내고 싶다면 add, remove, check, toggle을 할때 어떤 수 X를 -1 해주도록 하자. * 어떤 수X가 집합에 포함되어 있는지를 검사할 때(check) N & (1
백준 1561 놀이공원 Java 2019. 5. 27. 이분 탐색 문제인 놀이공원이다. 아무정보없이 이 문제를 만났다면 이분탐색으로 풀릴 거라는 생각도 못했을 것이다. 여태까지 풀어본 다른 이분 탐색 문제들과는 조금 다르다. 수를 딱 정해서 이분탐색으로 그 범위를 줄여나가는 것이 아닌 N번째 학생이 탈 놀이기구의 번호, N번째 학생이 정해져있다. 놀이기구의 번호로 범위를 줄여나갈 순 없을 것이다. 이 문제는 시간으로 범위를 설정해야 한다. 놀이기구의 개수 m이 주어지고 각각의 놀이기구 운영 시간이 주어지기 때문이다. x분까지 놀이기구를 탄 학생의 수를 구해서 end에 넣고 x분에 놀이기구를 탄 학생의 수를 구해서 end에서 뺀다음 begin에 넣고 그 사이에(begin 17에 0분에 탄 m명의 학생수를 더하면 된다. -> 17+5 -> 22명 x분에 탄 학생..
백준 1939 중량제한 Java 2019. 5. 24. 이분탐색 문제인 중량제한이다. 이분탐색 문제는 대체로 쉽다고 생각했는데 이분탐색에 DFS/BFS 가 섞이니까 생각보다 많이 헷갈렸다... 내가 정답률을 떨어뜨리는데 한 몫 했다. 문제는 마지막 줄에 주어지는 섬 두 개 사이에 물품을 옮길 때 중량의 최댓값을 출력하면 된다. 예제 입력에서 가중치를 제외하면 1 2 3 1 2 3 인데 마지막에 주어진 섬이 1 3 이므로 1 -> 3으로 바로 갈 수도 있고 1 ->2 ->3으로 갈 수 도 있는 것이다. 그렇기 때문에 그래프 자료구조에서 DFS / BFS를 통해 탐색해야 한다. 입력에 가중치가 주어지기 때문에 클래스를 하나 더 만들어서 그래프를 만들어 줘야했다. 양방향 그래프로 입력 받는다. 그 다음 가중치의 최솟값 -> start, 최댓값 ->end로 범위를 ..

티스토리툴바