빵똥

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단계 달성했다...! 다양한 유형을 접하고 있는 단계이며 취준 기간이 길어지더라도 조급해하지 하지 말고 천천히 가보려고 한다 백준, 인프런, 프로그래머스 등 한 문제씩 풀어갈 때마다 복습의 개념으로 블로그에 정리하고자 한다!