Algorithm

[BOJ] 1931번 : 회의실 배정 (JAVA/자바)

문제 알고리즘 고민 처음에는 DP 인가 그리디인가 조금 헷갈렸다. 시작하는 시간이랑 끝나는 시간 두개의 변수가 있어 단순 그리디로 풀리는건가 싶었다. 조금 더 고민을 하던 중 최대 할 수 있는 회의의 개수는 결국 끝나는 시간이 낮은 걸 우선순위로 체크하면 된다는걸 깨달았다. 시작하는 시간이야 어떻든지 끝나는 시간이 빨라야 다음 회의가 더 많이 시작할 수 있는 기회가 생기는 것이기 때문이다. 1. 회의의 시간을 끝나는 시간 기준으로 정렬했다. 다만 시간이 같다면 시간이 더 빨리 시작하는 것을 우선적으로 처리하였다. (시간이 같을때 더 빨리 시작하는 것을 우선적으로 해야하는 이유는 회의가 5시에 끝났다고 가정해보자 그 다음으로 6 to 6 과 5 to 6이 있다면 5 to 6 을 진행하고 6 to 6을 진행..

[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..