빵똥

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 접근 N과 K모두 최대 10만에 있을 수 있고 방문횟수 또한 끝에서 끝 지점으로 -1로만 이동했을 경우 10만번 방문한다. 즉 시간복잡도 및 최대값은 10만으로 BFS로 접근 가능하다. BFS 문제이지만 노골적으로 격자판이나 그래프가 주어지지 않기 때문에 수빈이의 위치와 동생의 위치까지를 각 정점으로 볼 수 있고 이동 가능한 경로는 그림과 같이 x - 1, x + ..

https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 1. 접근 나이트가 갈 수 있는 곳을 확인하는 게 500²에 M의 위치를 확인하여 출력하는 게 1000으로 BFS를 이용하여 시간 내에 충분히 풀 수 있는 문제이다. 먼저 나이트의 이동경로를 사용하기 편하게 배열로 저장하고 static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1..

BFS 기초 문제 중 하나이다. 1. 접근 정점의 최대 갯수는개수는 100개이며 완전 그래프라 가정해도 간선의 개수는 n * (n - 1) / 2 = 100 * (100 - 1) / 2 = 4,950개, 그에 따른 무방향 그래프의 차수의 개수는 4,950 * 2 = 9,900개로 시간제한에 여유 있게 풀 수 있다. 2. 풀이 두 번째 입력값인 두 사람의 촌수, 즉 예제로 보자면 다음 그림과 같다. 다른 기초 BFS 문제와 같이 이동할 때 마다 배열에 1씩 누적하며 최종 목적지의 값을 출력하면 끝이다. 전역 변수 및 input static int V, E, start, end; static ArrayList[] graph; static int[] dist; public static void main(Str..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 2178번과 같이 너비 탐색 기초 문제다. 1. 접근 테스트 케이스의 최대치가 나와있지는 않으나 체스판의 최대 크기인 300² 를 모두 밟아도 90,000으로 시간제한 걱정 없이 풀이에 접근하면 된다. 그림 예제에 나와있듯 나이트의 이동 경로를 미리 배열로 짜둔다면 다음과 같다. (시계방향) static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, ..

1. 자료구조란? 자료(데이터)의 효율적인 처리를 위해 자료들 간의 논리적 관계를 추상화를 통해 구조화한 것을 자료 구조라 부른다. 여기서 말하는 추상화란 시내버스, 고속버스, 공항버스 등을 묶어 버스라 부르고 버스, 지하철, 택시를 묶어 대중교통이라고 부르는 것처럼 자료들이 가지는 공통의 특징만을 뽑아 정의한 것이다. 개발자가 사용하는 프로그래밍 언어에서의 자료구조의 형태는 '미리 정의된 자료구조'와 개발자가 정의하여 사용하는 '사용자 정의 자료구조'로 구분된다. 미리 정의된 자료구조는 해당 언어가 설계단계나 컴파일러 단계에서 개발자에게 제공하는 자료구조이며 사용자 정의 자료구조는 개발 중 개발자에 의해 만들어진 리스트, 스택, 큐, 트리와 같은 자료구조이다. 부적절한 자료구조의 사용은 개발의 복잡도를..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 가중치 없는 그래프에서 최단 거리를 구하는 가장 기초적인 BFS 문제다. 1. 접근 미로의 모든 칸을 다 밟는다고 가정해도 최대 N * M, 즉 100²인 10,000으로 시간제한 1초 내에 풀 수 있다. 이동할 때의 조건으로는 다음과 같으며 배열로 미리 저장해두면 다음과 같으며 static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; 좌표상 (n - 1)(m - 1)에 도착했을 때 ..

DFS와 BFS를 동시에 활용해야 하는 문제인 백준 14502-연구소 문제를 풀어보자. (solved.ac 티어 = 골드 5) https://www.acmicpc.net/problem/14502 1. 접근 문제에서 확인할 수 있듯 그래프의 크기는 8 * 8 = 64가지이며 바이러스의 확산을 막는 벽을 반드시 3개를 설치해야 한다. 즉 우리가 해야 할 일은 벽을 3개 세워본다 -> 바이러스를 퍼트린다(0인 곳) -> 남아있는 안전지역을 확인한다 -> 최 갯값을 갱신한다. 이렇게 네 가지로 정리할 수 있으며 최댓값인 64개의 공간에 중복되지 않게 벽을 3개 세워본다 = n! / ((n - m)! * m!) = 41664 벽을 세운 후 하나하나 탐색하며 안전지대인지 확인한다 = N² = 64 시간 복잡도 = ..

10월 1일 퇴사 후 인프런 알고리즘 강의를 거쳐 백준에서 한 달 만에 겨우 골드 5단계 달성했다...! 다양한 유형을 접하고 있는 단계이며 취준 기간이 길어지더라도 조급해하지 하지 말고 천천히 가보려고 한다 백준, 인프런, 프로그래머스 등 한 문제씩 풀어갈 때마다 복습의 개념으로 블로그에 정리하고자 한다!