[Problem Solving] BOJ 2615: 오목
문제 출처: https://www.acmicpc.net/problem/2615 오목 게임을 진행한 바둑판이 주어졌을 때, 검은 돌이 이겼는지, 흰 돌이 이겼는지 판정하는 문제다. 이긴 돌의 연속된 다섯 개의 바둑 알 중 가작 왼쪽의 바둑알의 좌표를 출력한다. 6개 이상으로 바둑알을 연속으로 놓았을 경우는, 승리로 판정하지 않는다. 일단 오목에서 이겼을 경우, 바둑알을 연속 5개를 놓는데, 놓는 방식은 4가지 방식이 있다.1. 세로로 5개2. 가로로 5개3. 오른쪽 대각선 아래로 5개4. 오른쪽 대각선 위로 5개이를 탐지하기 위해서, dx와 dy를 다음과 같이 정의한다.dx = [0, 1, 1, -1]dy = [1, 0, 1, 1] (0, 0)부터 (18, 18)까지 돌면서 위 네 가지 케이스가 있는지 찾..
2025. 9. 29.
[Problem Solving] 프로그래머스: 2019 카카오 개발자 겨울 인턴십 - 호텔 방 배정
문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr Union Find 알고리즘을 활용하는 문제이다. 입력이 [1, 3, 4, 1, 3, 1] 로 주어진다면출력은 [1, 3, 4, 2, 5, 6]이 되는데, 배정받고자 하는 방이 예약 가능하다면, 그 방과 오른쪽 방을 Union하는 것이다. Union된 Set의 부모 노드로 갈수록 숫자가 커져야 한다.입력에서 1번, 3번, 4번 방을 배정받고자 한다면,parent[1] = 2parent[3] = 4parent[4] = 5이 된다. 또 1번 방..
2025. 9. 23.
[Problem Solving] 프로그래머스 2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물
문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=python3 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 단순하게 풀려고 하면 시간초과가 날 수 있으므로, 누적합으로 최적화 해야 한다. 4 * 5 행렬에 board가 다음과 같이 있다고 가정하자.5 5 5 5 55 5 5 5 55 5 5 5 55 5 5 5 5(0, 1)부터 (3, 3)까지 공격하여 1 만큼 건물의 내구도를 낮춘다고 하자.우선 (0, 1)에 -1을 해주고, (0, 4)와 (4, 1)에는 +1을 해주고, (4, 4)에는 -1을 해준다.0 -1 0 0 ..
2025. 9. 10.