본문 바로가기
반응형

분류 전체보기701

백준 5427 불 c++ (bf) 문제 출처 : https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 .. 2021. 7. 27.
백준 5547 일루미네이션 c++ (bfs) 2022-07-06 Kotlin 추가 문제 출처 : https://www.acmicpc.net/problem/5547 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 문제 부유한 집안의 상속자 상근이네 집은 그림과 같이 1미터의 정육각형이 붙어있는 상태이다. 크리스마스가 다가오기 때문에, 여자친구에게 잘 보이기 위해 상근이는 건물의 벽면을 조명으로 장식하려고 한다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에, 밖에서 보이는 부분만 장식하려고 한다. 위의 그림은 상공에서 본 상근이네 집의.. 2021. 7. 27.
백준 4179 불! c++(bfs) 문제 출처 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는.. 2021. 7. 26.
[알고리즘] Graph-위상 정렬(Topological Sort) 참고 자료 : https://www.youtube.com/watch?v=qzfeVeajuyc Topological Sort Result : 1 : 위상 정렬 가능(사이클이 존재하지 않는다.) 2 : 1, 2, 3, 5, 4, 6, 7 or 1, 2, 3, 4, 5, 6, 7 위상 정렬(Topological Sort)이란? 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용하는 알고리즘으로, 방향 그래프에 존재하는 각 정점들의 선행 순서를 지키며 모든 정점을 나열하는 것이다. 위상 정렬(Topologicla Sort)의 특징 여러 개의 답이 존재할 수 있다. 그래프의 흐름은 '조건'이다. 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. 즉, DAG(Directed Acyclic Graph : 사.. 2021. 7. 24.
백준 2583 영역 구하기 c++ (bfs,dfs) 문제 출처 : https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된.. 2021. 7. 24.
[알고리즘] 분할 정복(Divide and Conquer) 분할 정복(Divide and Conquer)이란? 주어진 문제의 입력을 나눌 수 없을 때까지 분할(Divide)하여 문제를 해결(Conquer : 정복)한 뒤, 다시 병합(Combine)하는 방식의 알고리즘으로, 이진 탐색(Binary Search) 알고리즘, 병합 정렬(Merge Sort) 알고리즘, 퀵 정렬(Quick Sort) 알고리즘 등에 사용된다. Divide : 문제가 분할이 불가능할 때까지, 2개 이상의 문제로 나눈다. Conquer : 문제를 해결한다.(정렬, 탐색 등) Combine : Conquer한 문제들을 병합하여 원래 문제의 답을 얻는다. 분할 정복(Divide and Conquer)의 특징 1. 분할된 문제들은 크기만 작아질 뿐, 원래 문제와 성격이 동일하다. 2. 대개 재귀적.. 2021. 7. 21.
백준 1068 트리 c++, Kotlin, Java (dfs,bfs) 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는.. 2021. 7. 21.
백준 1052 물병 c++ (탐욕법) 문제 출처 : https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 문제 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않.. 2021. 7. 21.
[알고리즘] 병합/합병 정렬(Merge Sort) 병합 정렬(Merge Sort)이란? 리스트를 반으로 더 이상 나눌 수 없을 때까지 반으로 나누고(Divide : 분할), 나누어진 부분 리스트들을 두 개씩 짝지어 정렬(Conquer : 정복)하며 합치는(Combine : 결합) 과정을 반복하는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 병합 정렬(Merge Sort)의 특징 1. 주어진 배열(입력 배열) 이외에 다른 추가 메모리를 요구한다. //추가적인 리스트가 필요하다. 2. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다. // merge할 때 같은 값이 나온다면 앞의 그룹의 숫자를 먼저 써야 함 3. 데이터들 간의 상대적 크기 관계만을 이용해서 정렬하는 비교 정렬이다 4. 시간 복.. 2021. 7. 21.
반응형

티스토리툴바