백준

[BOJ] 2580번 : 스도쿠 (JAVA/자바)

문제 알고리즘 고민 빈 공간인 0에 1부터 9까지 차례대로 넣으면서 스도쿠의 기본 원리인 3x3 칸 + 가로 9칸 + 세로 9칸 검사를 진행하고 가능하면 넣은 후 dfs로 탐색을 진행하는 방법으로 작성하였다. 1. 입력 값인 스도쿠를 for문을 이용해서 값이 0 인곳(빈칸)을 탐색해서 blankIdx 라는 ArrayList 배열에 빈 공간의 point를 전부 담아 놓는다. (탐색하는 시간을 조금이라도 줄이려고 한 과정이지만 사실 차이는 없을 것 같아 어차피 탐색은 n개를 O(n)으로 탐색하기 때문에... 2. dfs 방식으로 탐색을 하면서 숫자를 넣었는데, 만약 모든 빈칸이 꽉 찼다면(blankIdx.size() == cnt(채운 숫자 개수)) 현재의 스도쿠 상태를 출력하고 프로그램을 종료한다. 3. 숫..

[BOJ] 9663번 : N-Queen (JAVA/자바)

문제 알고리즘 고민 퀸은 가로, 세로, 4방향의 대각선으로 공격이 가능하다. 따라서 퀸을 놓을 수 있는지 확인하려면 놓는 위치에서 위에 해당하는 범위에 다른 퀸이 있는지 확인을 해야한다. 없다면, 놓는 퀸이 다른 퀸을 공격할수도, 다른 퀸이 놓는 퀸을 공격할수도 없을것이다. 처음에는 dfs 통해 N x N 배열을 돌면서 퀸을 한쪽에 놓고 그 위치에서부터 배치가 가능한지 위의 공격범위로 총 8방향을 검사하면서 진행했다. 하지만, N이 8만 되도 시간이 엄청나게 드는것을 확인할 수 있었다. 이후 다른 방법에 대해 생각을 했다. 퀸을 배치할때, 가로나 세로 부분에 한부분은 무조건 차지하기 때문에 사실 배열이 2차원이 아닌 1차원 배열로도 표현을 압축해서 하는 것이 가능하다는 것을 확인했다. 세로 1 2 3 4..

[BOJ] 15649번 : N과 M (1) (JAVA/자바)

문제 알고리즘 고민 1부터 N 까지의 수를 M 개를 나열한 조합을 출력하는 문제이다. 처음에 바로 든 생각은 DFS 였다. 재귀형식의 DFS 를 사용하였는데 visited를 만들어 방문지를 숫자로 하여 중복되지 않도록 하였고, 합계 대신 String 으로 숫자를 만들며 다음 dfs에게 넘겨주었다. String에 넣어준 숫자의 개수가 M이 될때 최종적으로 출력할 정답 StringBuffer에 넣어주면서 return 하였다. 문자열은 만들어서 넘겨주게 되면 새로운 객체가 생성되기 때문에 Call by Reference 의 문제가 생기지 않을거라고 생각했다. JAVA Code import java.io.BufferedReader; import java.io.IOException; import java.io.I..

[BOJ] 10757번 : 큰 수 A+B (JAVA/자바)

문제 알고리즘 고민 이 문제는 큰 고민을 하지 않았다. 이전에 자바를 공부할 때 BigInteger 라는 큰 수를 처리하는 좋은 기능이 있기 때문에 그 기능을 사용해서 바로 문제를 해결하였다. Python 이나 C/C++ 같은 경우에는 고민이 필요할 것으로 예상된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedRead..