본문 바로가기

장원익 기술블로그

💻 Computer Science191

[알고리즘 PS] 백준 10451번 순열 사이클 자바 문제풀이 문제 해당 포스팅은 백준의 10451번 순열 사이클 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 해결법 이번 문제는 지난번 풀었던 연결 요소의 개수문제와 매우 유사한 문제이다. 문제가 이야기하고 있는 것은 이렇다. 순열의 길이가 먼저 주어진다. 그리고 그 길이만큼 순열이 들어오는데, 그 순열은 1 ~ N 까지 순서대로 나열한 순열의 인덱스와 1:1 매칭되어 해당 매칭 자첵가 그래프 노드의 연결 상태라고 한다. 문제의 특성상 수열로 만든 그래프는 무조건 사이클을 갖게 된다. 그럼 지난번 풀었던 연결 요소의 개수문제와 동일한 문제가 되는 것이다. 오답 후보 이 문제.. 2021. 2. 7.

[알고리즘 PS] 백준 11724번 연결 요소의 개수 자바 문제풀이 문제 해당 포스팅은 백준의 11724번 연결 요소의 개수 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 해결법 연결 요소(Connected Component) 문제는 대표적인 DFS와 BFS 문제라고 볼 수 있다. 문제가 이야기하는 것은 바로 이것이다. 만약 7개의 그래프 노드가 존재하고, 각각의 노드가 아래와 같이 연결되어 있다면, 연결 요소의 개수는 총 3개가 된다는 것이다. 접근법 여기서 문제는 위에서 찾은 연결 요소의 개수를 찾는 것이다. 어떻게 할까? 그래프 각 노드에서 DFS를 수행하고 처음 수행할 때만 수를 Count 해주고 (방문 이력이 없는 노드일.. 2021. 2. 7.

[알고리즘 PS] 백준 1260번 DFS와 BFS 자바 문제풀이 문제 해당 포스팅은 백준의 1260번 DFS와 BFS 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 해결법 해당 문제를 해결하기 위해서 우선 그래프를 구현해야 한다. 그래프를 구현하는 방법에는 크게 2가지가 있다. 이 2가지 (인접 행렬, 인접 리스트)로 우선 그래프를 구현 한 뒤 탐색을 수행하면 될 것 같다. 만약 구현 방법에 대해서 알지 못한다면 아래 링크를 통해서 한 번 확인하는 것도 좋은 선택이다. 인접 리스트 구현 방법 인접 행렬 구현 방법 그래프의 DFS와 BFS를 구현하는 방법에는 여러 방법이 있다. 스택으로 DFS 구현하기 재귀 호출로 DFS 구현하.. 2021. 2. 7.

[알고리즘 PS] 백준 9613번 GCD 합 자바 문제풀이 문제 해당 포스팅은 백준의 9613번 GCD 합 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 해결법 이번 문제는 전형적인 GCD 문제였다. 유클리드 알고리즘을 모르는 사람에겐 어려운 문제였겠지만, 유클리드 GCD 알고리즘을 알고 있는 사람에게는 입력 처리하는게 더 어려웠을 것 같다. 만약 유클리드 알고리즘에 대해서 알지 못한다면 유클리드 알고리즘을 통한 최대 공약수와 최소 공배수에서 학습하는 것을 적극 추천한다. 접근법 배열이 주어진다면, 2중 for 문을 통해서 각각 구할 수 있는 gcd를 모두 구하면 된다. 하지만 주의해야할 것이 하나 있다. 아마 이 문제가.. 2021. 2. 4.

[알고리즘 PS] 백준 1850번 최대 공약수 자바 문제풀이 문제 해당 포스팅은 백준의 1850번 최대 공약수 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 이번 문제는 최대 공약수를 구하는 단순한 문제에서 조금 변형을 한 형태이다. 이 변형 덕분에 문제의 정답률이 30%라고 생각하는데, 잘 따라온다면 그리 어렵지 않은 변형이다. 해결법 문제에서는 다음 두 개의 입력을 준다. A : 첫 번째 수의 자리수 B : 두 번째 수의 자리수 이렇게 A와 B를 받게 된다면 우리는 1을 A번과 B번 각각 이어 붙혀 하나의 수를 만들 수가 있다. 만약 A가 3이고 B가 6이라면 A = 111 B = 111_111 이와 같이 구성된다. 여.. 2021. 2. 4.

[알고리즘 PS] 백준 2609 최소 공배수 최대 공약수 자바 문제풀이 문제 해당 포스팅은 백준의 2609 최소 공배수와 최대 공약수 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 해결법 이번 문제는 2개의 자연수를 GCD, LCM 처리하라는 문제이다. GCD, LCM을 처리하는 일반적인 방법을 통해서 구한다면 O(N^2)의 시간 복잡도가 소요된다. 하지만 문제에서는 시간 제한도 넉넉하고 n이 2로 고정되어있기 때문에 어떤 방법을 통해 해결해도 제한이 되지 않는다. 하지만 그래도 시간 복잡도가 더 적은 유클리드 알고리즘을 통해서 O(log N)으로 문제를 해결해보자. 접근법 해당 문제는 유클리드 알고리즘이 사용된다. 만약 유클리드 알.. 2021. 2. 4.

이전 1 ··· 9 10 11 12 13 14 15 ··· 32 다음

티스토리툴바