Social Developer

어제보다 한 걸음 더

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.