본문 바로가기

장원익 기술블로그

💻 Computer Science191

[알고리즘 PS] 백준 10971번 외판원 순회 2 자바 문제풀이 문제 해당 포스팅은 백준의 10971번 외판원 순회 2 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 CS 분야에서 유명한 문제라고 한다. 이 문제의 핵심은 다음과 같다. n by n 행렬에서 (n, m)은 혹은 arr[n][m]은 n에서 m으로 가는 비용.. 2021. 2. 20.

[알고리즘 PS] 백준 10819번 차이를 최대로 자바 문제풀이 문제 해당 포스팅은 백준의 10819번 차이를 최대로 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 로그인 www.acmicpc.net 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 문제에서 주어진 풀이 조건은 그닥 어렵지 않다. 단지 각각 원소의 다음 원소와 차이가 최대가 되는 식에 만족하는 값을 찾으면 된다. 어떻게 하면 차이가 최대가 될까? 아직 나의 능력으로는 쉽게.. 2021. 2. 20.

[알고리즘 PS] 백준 10974번 모든 순열 자바 문제풀이 문제 해당 포스팅은 백준의 10974번 모든 순열 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 지난 문제를 통해서 우리는 nextPermutation() 메서드를 구현하면서 다음 순열을 구하는 방법을 배웠다. 이번에는 다음 순열을 구할 수 있는 최대까지 구하는 모든 수열문제를 풀어볼 것이다. 이번 문제도 순열에 대한 핵심 컨셉에 대해 알고 있는지를 물어보는 것이기 때문에 nextPermutation() 만 구현할 수 있으면 쉽게 해결할 수 있는 그런 간단한 문제이다. 해결법 다음 순열을 구하기 위한 방법에는 다음 4가지 순서를 따라야 한다. A[i-1.. 2021. 2. 20.

[알고리즘 PS] 백준 10973번 이전 순열 자바 문제풀이 문제 해당 포스팅은 백준의 10973번 이전 순열 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 순열을 구하기 위한 Prev Permutation을 구현하는 문제이다. 지난 10972번 다음 순열 문제와 같은 취지의 문제라고 할 수 있다. STL 에서는 next_permutation과 prev_permutation 이 기본적으로 제공되어 그대로 사용하면 되지만, 자바에서는 이를 직접 구현해줘야 한다. 다음 순열을 구하기 위해서는 4가지 순서를 따라야 한다고 했는데, 이전 순열을 구하려면 다음 순열을 구하는 부등호의 반대만 해주면 된다. A[.. 2021. 2. 20.

[알고리즘 PS] 백준 10972번 다음 순열 자바 문제풀이 문제 해당 포스팅은 백준의 10972번 다음 순열 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 순열을 구하기 위한 Next Permutation을 구현하는 문제이다. STL 에서는 next_permutation이 기본적으로 제공되어 그대로 사용하면 되지만, 자바에서는 이를 직접 구현해줘야 한다. 다음 순열을 구하기 위한 방법에는 다음 4가지 순서를 따라야 한다. A[i-1] = 1 이면서 A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다. A[i-1] 과 A[j]를 Swap 한다.. 2021. 2. 20.

[알고리즘 PS] 백준 15650번 N과 M (2) 자바 문제풀이 문제 해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 지난 N과 M (1) 풀이와 마찬가지로 백트래킹 문제의 대표적인 문제라고 할 수 있다. 이전 시간까지 우리는 브루트 포스 알고리즘 문제들을 풀었는데, 브루트 포스 알고리즘은 가능한 모든 경우를 대입해 정답을 찾는 방.. 2021. 2. 18.

이전 1 ··· 6 7 8 9 10 11 12 ··· 32 다음

티스토리툴바