병아리의 코딩 일기

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 해결 프로세스 및 꿀팁 대각선도 이동이 가능하므로 길이가 8인 델타 배열을 만듭니다. (팔방탐색) 원래 DFS는 visited 배열을 만들어 검사해줍니다. 하지만 이런 문제같은 경우에는 1을 지날 때 0으로 바꾸어주면 됩니다. map의 좌표 중 1인 곳만 탐색하기 때문에, 0으로 바꾸어준 곳은 더이상 다른 곳에서 탐색하지 않기 때문입니다. 한 가지 꿀팁을 드리자면!! map의 좌표를 w..

https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 문제 해결 프로세스 이 문제는 이전 깊이 우선 탐색 1 문제와 완전히 동일하지만, 정점을 내림차순으로 방문합니다. Collections.reverseOrder() 을 이용하여 리스트만 내림차순으로 정렬해주면 해결되지만, DFS 알고리즘에 익숙해지기 위해 다시 한 번 풀어보는 것을 추천해드립니다! 정답 코드 package DF..

문제 요약 격자 내에서 모든 값이 양수로만 이루어진 직사각형 중 최대 크기를 구하는 문제입니다. 그런 직사각형이 없다면 -1 을 출력합니다. 문제 해결 프로세스 이 문제는 완전 탐색으로 풀어야 합니다. 어느 칸에 어떤 숫자가 들어있을 지 모르기 때문이죠. 그렇다면 어떻게 완전탐색을 할 수 있을까요? 저는 직사각형의 시작점 (i, j)을 정하고, 끝점(k, l)을 정해서 풀었습니다. 직사각형 꼭짓점의 행, 열의 좌표가 될 수 있는 범위를 나타내면 다음과 같습니다. (0 ~ n-1 으로 놓고 풀었지만 편의상 아래와 같이 표시할게요.) 시작점 i : 1 ~ n j : 1 ~ m 끝점 k : i ~ n (끝점의 행이 시작점의 행보다는 크거나 같아야 합니다.) l : j ~ m (끝점의 열이 시작점의 열보다는 크..

안녕하세요~! 오늘은 SW Expert Academy의 Ladder1 문제를 풀이해보려 합니다. 난이도는 D4 이구요, 구현만 잘하면 어렵지 않게 풀 수 있는 문제입니다. (는 저는 처음에 못풀었음,, ) 그동안은 문제를 보자마자 달려들려고 했는데, 문제의 요구 사항 및 해결 전략을 간단히 세우고 나서 풀면 도움이 된다고 하시더라구요. 그래서 저도 앞으로는 정리를 간단히 해보고, 문제를 적어도 3번은 읽어보고 정확하게 접근하려고 합니다. 문제를 어렵게 풀었는데 정작 문제를 정확히 읽지 않아서 다 지우고 시작했던 적이 종종 있거든요. 문제는 아래 링크에서 확인해주세요! 😀 🍎 문제 링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?cont..

본 글은 Do IT 알고리즘 코딩 테스트 자바 편을 정리한 글입니다! 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 코딩 테스트에서 사용 빈도가 높으니 꼭 알아두시기 바랍니다. 구간 합의 핵심 이론 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 합니다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의합니다. 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열이라 생각하면 됩니다. 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다. A[i]부터 A[..