글 (452) 썸네일형 리스트형 [Python] 1799번 비숍 (추후 보강 예정) https://www.acmicpc.net/problem/1799 25/08/07 일단 이 문제는 여러 가지 풀이 방법이 있는데, 내가 푼 방법만 소개하도록 하겠다. 문제 접근 방식: 먼저 체스를 생각해보면, 흰색 칸의 비숍은 검은 색 칸의 비숍에 전혀 영향을 미치지 못한다. 반대도 마찬가지다. 따라서, 보드 판을 흰색 칸과 검은색 칸으로 분리할 수 있다. 이후에, 비숍은 항상 "대각선"으로 움직이므로, 보드를 45도로 돌려서 모서리 부분을 패딩한다면 비숍 문제를 룩 문제로 바꿔서 생각할 수 있다. 그리고 룩 문제에서 서로가 공격할 수 없도록 최대한의 룩을 놓으려면 각 열과 각 행에 하나씩의 룩만 놓을 수 있다. N-Queen문제를 풀어봤다면 알 수 있듯, 각 열과 각 행에 하나씩의 기물을 놓는 .. 히스토그램에서 가장 큰 직사각형(Largest Rectangle in Histogram) 최근 히스토그램에서 가장 큰 직사각형 문제에 대해 배우게 되어 다양한 풀이 방법을 작성해보고자 한다. 히스토그램에서 가장 큰 직사각형 문제란? 단위 길이의 폭을 가지는 막대들이 일렬로 나열된 히스토그램이 주어짐.해당 히스토그램 내부에 포함되면서 가장 넓이가 넓은 직사각형을 구하는 문제이다.막대들은 모두 단위 길이를 가지고 있기 때문에, 편의 상 막대의 높이들은 $A[i]$와 같은 형태의 배열로 주어진다고 하자. 즉, $A[i]$는 $i$번째 막대의 높이가 되는 것이다.이 문제에서 가장 쉽게 생각할 수 있는 솔루션은 $\mathcal{O}(N^3)$짜리의 솔루션이다. 히스토그램에 포함되는 모든 직사각형을 조사하는 방법으로, 두 인덱스 $i, j$를 선택하고, 그 사이에 있는 모든 막대를 조사함으로써 막대 .. [Python] 2567번 색종이 - 2 https://www.acmicpc.net/problem/2567 25/07/30 도형의 둘레를 구해보자. 문제 접근 방식: 여러 방법이 있지만, 결국 스위핑 아이디어로 통일된다. 문제에서 요구하는 대로 직사각형의 합집합을 2차원 배열 상에서 표현하는 것은 그리 어렵지 않다. 이제 스위핑을 하면 된다. 갑자기 엥 스위핑이 뭐지 싶지만, 그냥 배열 순회하며 쓱 쓸어버리는거라고 생각하면 된다. 귀찮아서 다 표시는 못했지만, 2차원 배열을 색칠한 후에 행 별로 순회하며 세로 길이를 모두 잴 수 있다. 이때 0과 1이 바뀌는 지점, 혹은, 현재 지점과 이전 지점의 값이 서로 다른 경우 경계이므로 이때 세어주면 된다. 이렇게 세로 경계를 다 세어주면 가로 경계를 똑같이 세어주면 된다. 혹은 다음과 같이 생각.. [Python] 3158번 Sierpinski 삼각형 https://www.acmicpc.net/problem/3158 25/07/30 약간의 아이디어를 필요로 하는 문제이다. 문제 접근 방식: 문제에서 요구하는 것은 T123232232와 같은 형식으로 부분 시어핀스키 삼각형이 문자열로 주어질 때, 해당 부분 시어핀스키 삼각형과 변을 공유하는 모든 부분 시어핀스키 삼각형을 T12323...과 같은 형식으로 출력하는 것이다. 먼저 예제 입력에 나와있는 T312를 분석해보자.그림과 같이 놓여있는 형태이다. T312는 T31이라는 부분 시어핀스키 삼각형에서 2자리에 위치해있다. 따라서, T314와 인접하다는 사실을 알 수 있다. 이를 확장시켜보면, 주어지는 문자열이 1, 2, 3으로 끝난다면 해당 문자열의 마지막 글자를 제외한 부분 시어핀스키 삼각형의 4번째.. [Python] 31541번 1차원 돌 게임 1 (추후 보강 예정) https://www.acmicpc.net/problem/31541 25/07/03 플레티넘 200문제를 채우기 위해 풀었던 문제 중 하나이다. 규칙을 찾아서 해결했다. 문제 접근 방식: 일단 $T$의 제한이 $10^6$으로 수상하게 크고, $n$의 제한 또한 $10^{18}$으로 크므로, $\mathcal{O}(1)$에 준하는 시간으로 답이 나와야 함을 추측할 수 있다. 게임 이론 문제이고, 서브태스크가 각 제한 별로 나와있어서, 주어진 작은 제한 $n = 1000$까지에서 DP를 돌려 규칙을 찾아보기로 했다. 상태 식은 다음과 같이 정의된다. $$DP[N][K] = N개의 돌이 있고, 현재 K개의 돌을 가져가야 할 경우의 승패 여부$$ 당연히 $N $N == K$라면 선공이 딱 맞춰서 다 가져.. [Python] 1220번 [S/W 문제해결 기본] 5일차 - Magnetic https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14hwZqABsCFAYD 25/07/28 아이디어를 떠올리면 쉽게 구현할 수 있는 문제이다. 문제 접근 방식: 일단 문제를 보면 열 별로 독립이기 때문에, 하나의 열에 대해서만 어떻게 움직일지를 생각해보자. 구현의 편의 상 열 별로 구현하기가 힘드므로, list(map(list, zip(*M)))을 통해 전치 행렬을 취해줌으로써 행 별로 순회하도록 고쳐보자. 교착상태가 되려면 빨간 색이 나온 후에 파란 색이 나와야 한다. 따라서, 빨간색이 나올 때 flag를 세워주고, 교착상태가 있다면 답에 더해준다. 빨간색이 나온 뒤에 파란색이 나온 다면, 즉, flag와 .. [Python] 1767번 [SW Test 샘플문제] 프로세서 연결하기 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf 25/07/29 구현에서 실수가 날 수도 있는 약간 까다로운 백트래킹 문제이다. 문제 접근 방식: 문제에서 요구하는 상황은 다음과 같다. 현재 코어가 놓여있고, MAP의 가장자리에는 전기가 흐른다. 가장자리에 놓여있는 코어는 전기가 이미 흐른다고 간주한다. 우리가 구하고자 하는 것은, 코어에 전선을 연결하여 최대한 많은 코어에 전기를 흘리고자 할 때 그때 전선 길이의 합의 최솟값을 구하는 것이다. 이때 코어에서 가장자리로 연결하는 전선은 서로 교차할 수 없고, 일직선의 형태이다. 일단 문제를 보면, 맵의 크기가 상당히 작고, $7 \.. [Python] 7824번 Playing With Stones https://www.acmicpc.net/problem/7824 25/06/26 전형적인 스프라그-그런디 정리 문제이다. 플레티넘 200문제를 달성하기 위해 풀었던 문제들 중 하나이다. 문제 접근 방식: 문제가 영어로 되어 있기 때문에, 해석을 하자면 다음과 같다. 두 사람이 돌을 제거하는 게임을 함.$N$개의 돌 무더기가 주어져 있으며, 각각의 무더기에는 $a_1, a_2, \dots, a_n$개의 돌이 있음.자기 차례에 플레이어는 하나의 무더기에서 최소한 $1$개 이상의 돌을 제거해야하며, 해당 무더기의 돌 개수의 절반 이하만 제거할 수 있음.이때 돌을 제거할 수 있는 선택이 더 이상 없는 플레이어가 짐.두 사람이 최적으로 플레이 할 때, 선공이 이긴다면 "YES", 그렇지 않다면 "NO"를 출.. 이전 1 2 3 4 ··· 57 다음
