본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[알고리즘 PS] 백준 2606번 바이러스 자바 문제풀이 문제 해당 포스팅은 백준의 2606번 바이러스 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이번 문제는 대표적인 그래프 탐색 문제라고 할 수 있다. 그 중에서 연결 요소 찾기의 범주에 해당되는데, 어떻게 구현하는지 알아보자. 연결 요소를 찾는 대표적인 방법에는 크게 2가지가 있다. DFS BFS 이번 문제에서는 D.. 2021. 2. 24.

[알고리즘 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.

이전 1 ··· 4 5 6 7 8 9 10 ··· 25 다음

티스토리툴바