전체 글

슬라이딩 윈도우(Sliding Window) 기법이란?1. 개념슬라이딩 윈도우(Sliding Window) 기법은 배열이나 문자열 같은 연속된 데이터를 일정한 범위(윈도우)로 탐색할 때, 불필요한 중복 연산을 줄이는 알고리즘 기법입니다.2. 핵심 원리윈도우 크기를 일정하게 유지하면서 한 칸씩 이동하며 값을 업데이트합니다.새롭게 추가되는 값만 반영하고, 필요 없는 이전 값은 제거하여 중복 계산을 최소화합니다.보통 O(N)에 처리 가능하므로 브루트포스(완전 탐색) O(N^2)보다 훨씬 빠름.🔹 슬라이딩 윈도우의 동작 방식예를 들어, 길이가 N인 배열에서 크기 k의 윈도우를 사용하여 연속된 부분 합을 구하는 문제를 생각해보겠습니다.🔸 브루트포스(완전 탐색) 방식 (O(N*k))모든 부분 배열을 하나씩 탐색..

[Silver II] 헌내기는 친구가 필요해 - 21736문제 링크성능 요약메모리: 135696 KB, 시간: 240 ms분류너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 20일 16:35:31문제 설명2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.도연이가 다니는 대학의 캠퍼스는 N×M$N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x$x$, y$y$)에 있다면 이동할 수 있는 곳은 (x+1$x+1$, y$y$), (x$x$, y+1$y+1$),..

[Silver III] 구간 합 구하기 4 - 11659문제 링크성능 요약메모리: 127164 KB, 시간: 168 ms분류누적 합제출 일자2025년 1월 23일 11:02:04문제 설명수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.첫 시도는 당연히 쉽게 하려고 했다. 이게 왜 class3 이지? 라고 오만하게 생각했다.import sysN, M = map(int, sy..

[Silver IV] 체스판 다시 칠하기 - 1018문제 링크성능 요약메모리: 32412 KB, 시간: 64 ms분류브루트포스 알고리즘제출 일자2025년 1월 23일 10:24:00문제 설명지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우..

[Silver III] 1, 2, 3 더하기 - 9095문제 링크성능 요약메모리: 32412 KB, 시간: 36 ms분류다이나믹 프로그래밍제출 일자2025년 1월 22일 13:10:31문제 설명정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.나의 코드..

[Silver III] 바이러스 - 2606문제 링크성능 요약메모리: 108384 KB, 시간: 88 ms분류그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색제출 일자2025년 1월 21일 14:03:48문제 설명신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결..