빵똥

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1. 접근 문제를 풀기 전 시간 복잡도를 구하자! V + E를 T만큼 반복하는데 T는 제시되어 있지 않다! n과 m이 그리 크지 않으니 T도 상식적인 선 안에서 제시되니 일반적인 DFS로 접근해보자! 문제의 조건을 살펴보면 트리의 조건을 제시해주고 해당 조건을 만족하는 개수를 이 형식에 맞춰서 출력해주면 된다. 조건에서 제시된 트리의 기준은 정점이 n이라고 가정했을 때 간선이 n..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 접근 문제를 풀기 전 항상 시간 복잡도를 생각하자! 그래프 탐색에서의 시간 복잡도는 인접 행렬 = V², 인접 리스트 = V + E 이며 이번 문제 포함해 대부분의 문제는 인접 리스트로 접근하니 100,000 + 99,999 = 199,999로 시간 여유는 충분하다! 문제의 조건은 루트를 제외한 각 노드의 부모를 출력하는 것이다. 문제의 예제를 그림으로 그려서 접근해보자. 글로만은 이해가 어려우니 그림을 보며 이해해보자! 탐색을 진행하며 각 정점의 부모가..

1. 정렬 알고리즘 컴퓨터 과학에서 가장 많이 사용되는 연산 중 하나일 만큼 데이터를 활용함에 있어 정렬은 매우 중요하다. 예를 들자면, 당장 이 글을 쓰고 있는 티스토리에서도 글이 수백 개가 넘어간다면 카테고리별 혹은 날짜별 같은 특정한 정렬 기준에 따라 나열되어 있지 않다면 사람이 찾을 때도, 컴퓨터가 찾을 때도 많은 시간을 요구한다. 정렬 방법은 정렬이 수행될 때 데이터가 저장되어 있는 위치에 따라 내부 정렬, 외부 정렬로 구분한다. 내부 정렬은 데이터의 용량이 주기억장치(RAM) 저장 공간보다 작을 때 수행하는 정렬 방법이며 다양한 알고리즘에서 흔하게 사용되고 있는 정렬 방법이다. 외부 정렬은 내부 정렬의 반대의 케이스로 데이터를 보조 기억장치(HDD, SSD)에 저장하고 일부 데이터만 주기억장치..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 접근 최대 입력값에 따른 시간 복잡도는 다음과 같다. 칸의 갯수 = H * N * M = 1,000,000로 시간제한안에 여유있게 풀 수있다! 문제의 조건을 살펴보자 익은 토마토 기준으로 상,하,위,아래,좌,우 총 여섯 방향으로 토마토는 익어가며 토마토가 비어있는 칸도 있다. 첫 번째 입력 예제를 그림으로 보면 토마토가 잘 익어가다가 비어있는 칸으로 인해 모두 익지 못..

1. 알고리즘이란? 이론적으로 컴퓨터를 사용한 문제 해결의 가능성이라는 측면에서 0개 이상의 입력과 1개 이상의 출력이 있어야 한다, 각 명령은 단순 명확해야 한다, 한정된 수의 단계를 거친 후 종료되어야만 한다, 모든 명령은 컴퓨터에서 실행 가능해야 한다.로 총 네 가지의 조건을 만족해야 한다. 하나의 문장으로 종합하자면 주어진 문제의 대한 해답으로 모호함 없이 간단하며 컴퓨터가 수행 가능한 유한개의 명령을 순서에 따라 구성한 것이다. 다만 컴퓨터로 해결할 수 있어도 처리 과정이 너무 오래 걸려 현실적으로 해결할 수 없는 문제도 있기에 효율성 또한 충분히 고려되어야 할 조건이다. 2. 자료구조와의 연관성 효율적인 프로그램을 위해서는 효율적인 알고리즘이 필요하며 효율적인 알고리즘을 위해 적합한 자료구조를..

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 1. 접근 배열의 최대 크기는 50으로 50 * 50칸을 두 번만 방문하면 되니 약 2,500번만에 풀 수 있는 문제다! 문제의 조건을 살펴보자면 땅은 . * X D S로 총 다섯개로 나눌 수 있으며 물과 고슴도치는 매번 위, 오른쪽, 아래, 왼쪽 총 네 방향으로 이동이 가능하며 물은 벽과 비버굴을 통과할 수 없고 비버는 벽과 물 웅덩이를 통과할 수 없다. 다음과 같은 배치가 있다고 가정했을 때 최단 거리는 ..

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 1. 접근 상근이의 위치, 즉 1번 정점에서의 거리가 2 이하인 정점의 수만 카운트하면 끝이다! 즉, BFS의 시간복잡도인 O(V + E) = 500 + 10000 이면 풀 수 있다! 자신의 친구, 친구의 친구를 정점과 간선에 비유하면 1과 인접한 정점, 1과 인접한 정점과 인접한 정점(??)까지의 수 이며 2번, 3번, 4번 친구가 초대 대상이 된다. 2. 풀이 변수 세팅 stat..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 1. 접근 먼저 최대값과 시간 복잡도를 구해보자면 모든 관계를 다 둘러보아도 5,000번이면 되니 최대값은 넉넉하고 시간 복잡도로는 유저(간선)마다 각각의 케빈 베이컨 수를 구해야 하니 (유저 수 + 관계) * 유저수 = 100,000로 시간 또한 넉넉하다. 문제의 설명을 그래프와 표로 정리하자면 다음과 같다. 표와 같이 각 유저의 케빈 베이컨의 수..

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..