Social Developer

어제보다 한 걸음 더

Algorithms

문제는 간단하지만 해결은 좀처럼 쉽지 않다. 다만 DFS 응용으로 다소 중요하게 다뤄지는 개념이다. 단절점이나 단절선 문제 유형에 대해서 잘 익히고 가야겠다. 문제 해결에 있어 중점적인 부분은 최소 방문 순서를 기록하고 비교하는 것이다. 노드를 방문할 때마다 방문 순서를 매기고, 연결된 노드들의 방문 순서를 비교해가며 연결된 노드들의 최소 방문 순서를 구하고, 현재 노드의 최소 방문 순서를 비교해 현재 노드의 최소 방문 순서보다 연결된 노드과 재귀적으로 연결된 노드들의 최소 방문 순서가 같거나 크면, 현재 노드를 단절점으로 구별하는 것이다. 예를 들어, 예제 그래프는 아니지만 위와 같은 그래프가 있다고 하면, 1번 노드에서 부터 깊이 우선 탐색 방법으로 탐색을 시작하면서, 방문 순서를 기록해보면 [1, ..

2021. 3. 4.

Algorithms

그래프 이론 중 Union & Find 개념을 알고 있다면 쉽게 접근할 수 있는 문제다. 합집합 연산에서는 Union, 같은 집합에 포함되어 있는지 확인 연산은 Find로 확인할 수 있다. 기본적으로 단일 Union&Find 연산에서 시간 복잡도는 O(N)인데, 그런 연산이 이 문제에서는 M번 주어지므로, 단순하게 Union & Find를 구현하게 되면 시간초과를 볼 수 있는데, 경로압축기법을 사용해 시간복잡도를 대폭 단축시키면 대략 O(M)번의 연산으로 이 문제를 해결할 수 있다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static..

2021. 2. 26.

Algorithms

두 배열이 주어지고, 각각의 부 배열의 합으로 T를 만드는 문제이다. 이전에 연습했던 배열 원소들의 합을 가지고 투 포인터로 탐색해주는 방법과 크게 다르지 않다. 각 배열의 연속 부분 합 케이스들을 만들어 리스트에 담아준 뒤, 리스트를 오름차순 정렬해주고 투 포인터를 사용하면 된다. 유의할 점은 변수 타입 정의이다. 각 원소의 최대 절댓값이 백만이고, 주어지는 배열의 최대 길이가 1,000이므로 부 배열의 합 케이스를 계산할 때 약 100억으로 int 범위를 넘어간다. 따라서 답으로 출력할 변수 ans와 List를 정의할 때 Long형 변수로 답을 담아주면 된다. package exhaustiveSearch; import java.io.BufferedReader; import java.io.InputSt..

2021. 2. 12.

Algorithms

문제의 첫 인상이 범상치 않다. 그림이 등장하는데, 원이 나올 때부터 긴장된다. 하지만, 읽어보면 문제 지문 자체는 크게 복잡할 게 없다. 이전에 연습해오던 부분합, 투 포인터 문제와 유사한 것 같은데 먼저 원형으로 구성되어 있다는 점이 낯설다. 어떻게 구현해야하는지 끙끙대다가, 결국은 다른 분의 풀이를 참고해 해결했다. 참고: https://kohen.tistory.com/20 순환 큐라는 개념이 있다고 한다. 아직 본격적으로 찾아 공부해보지 않았으나, 이번 문제에서 이 유형에 익숙해지고자 했다. // in main function for(int i = 0; i < M; i++) { // check배열 초기화 check = new boolean[M]; // 첫 번째 조각 담기 check[i] = tru..

2021. 2. 12.

Algorithms

약간 독특한 문제다. 시간 제한도 12초로 비교적 길고, 입력도 다소 독특하게 주어진다. 문제는 간단한데, 단순하게 A, B, C, D 배열의 모든 조합을 차례대로 4중 반복문을 쓰게되면 시간복잡도는 4000^4(256조)로 눈 앞이 아득해진다. 다른 방법을 찾아야 하는데, 단순히 정렬을 통해 다중 포인터를 쓰는 방법은 배열이 4개나 있기 때문에 쓰기 어렵다. 때문에 배열을 2개씩 묶어 각 합을 통해 새로운 리스트 2개를 만들어 주고, 정렬한 뒤 투 포인터를 사용해준다. 배열을 2개씩 묶으면 4000^2(1,600만)를 2번 수행하기 때문에 크지만, 나름 합리적으로 새로운 리스트를 만들어 줄 수 있겠다. 또, 새로 생성된 리스트는 길이가 최대 1,600만이 되고 정렬시 시간 복잡도는 O(N log N) ..

2021. 2. 12.

Algorithms

이전에 풀었던 1182번 부분수열의 합 문제와 유사한데, 이번엔 수열 길이의 범위가 40으로 늘어났다. 이전처럼 백트래킹으로 구현하면 주어진 시간 내에 해결할 수가 없다.(2^40 = 약 1조) * 1182번 부분수열의 합: sdesigner.tistory.com/57 결국 다른 방법을 모색해야 하는데, 나는 여기서 해결방법이 떠오르지 않아 결국 다른 분들의 해결방안을 참고했다. * 참고: https://kohen.tistory.com/19 이 문제 풀이의 핵심은 전체 수열을 절반으로 쪼개보는 것이다. 1) 길이가 40으로 수열이 주어지면 길이가 각 20인 수열로 쪼개고, 자른 두 수열을 가지고 부분수열의 합 케이스들을 각각 구한다. // in main function // 입력받은 배열을 두 부분으로 ..

2021. 2. 12.

Algorithms

이 문제는 2가지 방식으로 시도했다. 먼저 첫 번째 풀이는 백트래킹 DFS 와 DP를 활용해서 한 번 시도했는데, DP를 활용하지 않았을 때는 시간초과가 나다가 DP를 도입하고 나니 틀렸다는 결과를 받게 됐다. 이 풀이에 대해서는 게시판에 BFS를 활용해 풀이한 사람도 있는 것으로 봐서 DFS 접근이 무조건 안되는 것 같지는 않은데 ... 이유를 찾지 못해 게시판에 도움을 요청하고 기다리고 있는 상태이다. (답변이 달리면 여기에 추가할 예정!) 혹시 여기서라도 이유를 아시는 분은 댓글 답변 부탁드립니다!(코드 하단 첨부) 두 번째 풀이는 다익스트라 알고리즘을 활용하는 것이다. 사실 문제를 보고 다익스트라로 풀 수 있겠다는 생각을 떠올리지 못했다. 개념은 대략 알았어도 활용하는 데 익숙치 않은 것이 이유일..

2021. 2. 11.

Algorithms

소수에 대한 개념과 투 포인터에 대해 익숙하다면 크게 어렵지 않게 해결할 수 있는 문제다. 소수의 특성 중 '양의 정수'라는 점과 문제에서 주어진 '연속된 소수'라는 점을 활용해 투 포인터를 사용하면 된다. 풀이는 에라토스테네스의 체를 이용해 주어진 범위(N N) { break; } } System.out.println(cnt); } }

2021. 2. 11.

Algorithms

어렸을 때 한 번씩 해봤을 법한 게임이다. 간단한 프로그래밍으로 답을 찾아낼 수 있을 거란 생각은 못해봤는데 신기하다. 여하튼 문제를 보면 몇 군데에 구멍이 뚫려있고, 그 안에 조건을 만족시키는 수를 넣어야 하는데 조건을 모두 만족시키려니 조금 머리가 아프다. 1) 가로줄에 유일한 숫자여야하고, 2) 세로줄에 유일한 숫자여야 하고, 3) 작은 사각형 안에서 유일한 숫자여야 하는 조건을 만족시켜야 하는데 구멍에 값을 하나 채워놓았는데 가로줄, 세로줄, 작은 사각형 안에 다른 구멍이 있다면 어떻게 해야할까 조금 막막하다. 다만 최근 백트래킹 문제를 집중적으로 몇 개 접했다보니, 순간 DFS와 백트래킹은 뇌리에 스쳤다. 결국 자리에 1~9를 모두 넣어보는데, 넣을 때마다 조건에 부합하는지를 체크하고 넣어주면 ..

2021. 2. 5.