java

[BOJ] 1541번 : 잃어버린 괄호 (JAVA/자바)

문제 알고리즘 고민 맨 처음에 문제를 잘못 이해해서 괄호를 단 한번 열고 닫을 수 있는줄 알고 DP 방식으로 풀으려고 했다... (문제를 꼼꼼히 읽는 습관을 기르자..) 괄호를 칠 수 있는 개수의 제한이 없다는 것을 확인하고 나서는 문제가 쉽게 풀렸다. 식을 진행하면서 ( - )연산자가 나온다면 그 이후부터는 모든 숫자를 음수로 생각하면 되기에 그렇게 문제를 풀었다. 입력을 받는 방식에서 람다를 이용해서 한번 받아보겠다고 이거저거 시도를 해보았다. 또한, 숫자만 뽑아내거나 연산자만 뽑아내는 방식 이것저것 해보면서 정규식에 대한 내용을 조금 공부했다. JAVA Code import java.io.BufferedReader; import java.io.IOException; import java.io.Inp..

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