Algorithm4 [BOJ][Java] 2615. 오목 문제 설명 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다. 입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오.. 2023. 7. 31. [BOJ Java] 1149 : RGB 거리 ( Dynamic Programming 문제 접근 방식 ) https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 제가 문제를 풀어보다가 마주한, 처음에는 해결하지 못하여 다른 DP 문제들을 여러 개 풀고 나서야 감이 잡혀서 풀어버린 Dynamic Programming 문제입니다. Dynamic Programming 문제는, 솔직히 제가 DP 문제를 많이 풀어보지 않았어도, 직관적으로 "아 이거는 DP 문제인 것 같은데?" 라는 직감이 확 왔습니다. 이 문제도 처음 마주하자마자, Gree.. 2023. 1. 4. [알고리즘 접근] 시간 초과를 예방할 수 있는 방법 최근에 알고리즘 테스트를 준비하면서, 학교의 중앙도서관에 알고리즘 코딩테스트 관련 책이 소장되어 있다는 것을 확인하고 흥미가 생겨 그 책을 확인했다. 한 장 한 장 넘기면서 내게 모자란 부분을 채우려고 책장을 넘기는 와중, 아주 흥미로운 부분이 눈에 들어왔다. 백준을 기준으로 하면, 단순히 연산을 1억 번 이상 진행하게 되면 1초가 걸린다는 부분이었다. 그렇다면, 이것을 반대로 생각해 보면, 문제에서 주어진 가장 큰 데이터 코너 케이스를 기반으로 가장 큰 수부터 고려해 문제를 해결해 나갈 수 있을 것이다. 어차피 작은 숫자는, 아주 큰 숫자를 기준으로 생각하여 문제를 풀었을 때 무조건 시간 초과가 나지 않을 것이다. 만약에, N 이 2^15 제곱이고, 우리는 한 변이 N 인 정사각형 모양 2차원 배열에서.. 2023. 1. 3. [BOJ Java] 1012 : 유기농 배추 급한 분들을 위한 반례 제안 1 2 3 5 0 0 1 0 1 1 0 2 1 2 답 : 1, 나올 수 있는 Output : 2 요약 : 처음 문제를 볼 때는, 최대 50 × 50 밭이라서, 한칸 한칸 비교하는 식으로 체크하는 로직을 만든다면 시간 복잡도 측면에서 충분히 해결할 수 있다고 생각했다. 하지만, 기존 로직에서 계속 오답 처리가 되었다. 나 스스로의 사고력에 갇혀서 반례를 찾지 못하는 것이라고 생각하여 질문 게시판을 보니, 모두 DFS 로 해결했다는 것을 알게 되었다. 기존에는 DFS 는 Node 들을 만들어 해결하는 것이라고 생각했다. 하지만, 그렇게 하지 않더라도 큰 틀에서 DFS를 쓸 수 있다는 것을 이번에 확인한 시간이었다. 단순히 어떻게 이런 "배추밭" 에서 DFS를 "잘 활용" 할 수 .. 2023. 1. 1. 이전 1 다음
