Social Developer

어제보다 한 걸음 더

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.