본문 바로가기

Algorithm/BOJ47

BOJ 11559 - Puyo Puyo(DFS, BFS, 배열 조작, 구현) C++, Java 풀이 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net - 전형적인 구현 문제이지만 생각보다 정확하고 빠르게 풀기 힘들었던 문제이다. 한 턴에 연쇄가 여러 번 일어나도 1연쇄로 카운트 되므로 한 턴에 모든 연쇄에 대해서 처리한 다음 블럭을 아래로 내리면 된다. C++은 dfs, Java는 bfs로 풀이하였다. #include #include #include #include #include using namespace std; .. 2022. 3. 23.
BOJ 17825 - 주사위 윷놀이(구현, 브루트포스, 백트래킹) https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net - 주사위를 10번 던지면서 4개의 말 중 하나를 선택해서 움직인다. O(4^10) = 100만이므로 브루트포스 방식으로도 충분히 풀 수 있다 - 4^10 = 2^20 이므로 말을 선택하는 방식의 종류(seq) = 0~(1 sync_with_stdio(false) typedef pair pii; vector v = { {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0}, {10, 13, 16, 19, 25, 30, 35, 40,.. 2022. 3. 11.
BOJ 16973 - 직사각형 탈출(BFS, 부분합) https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net - 이문제에서 부분합을 쓰지 않고 직사각형 내부에 벽이 있는지 검사하는 로직을 쓰면 복잡도가 O(WH)인 연산을 맵의 모든 칸에서 한번씩 돌게 되므로 O(NMWH) = 1000^4 연산을 하게 되서 시간 초과가 난다. - 1차원 부분합 개념을 통해서 i~j까지의 합을 s[j] - s[i] 로 표현할 수 있는데 2차원 부분합도 이와 유사하게 구현할 수 있다. - 1. (1,.. 2022. 2. 13.
BOJ 1948 - 임계영역(그래프, 위상정렬) https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net - 문제에서 2가지를 요구하는데 하나는 DAG가 주어지고 시작노드부터 끝노드까지 가야하는데 여기서 가장 긴 경로를 찾는 것, 다른 하나는 그 경로에 포함된 엣지의 갯수를 찾는 것이다. * 위상정렬 구현 방식(bfs로 구현할 때) - dfs나 스택도 가능함 1. 각 노드들의 진입 차수 계산 2. 진입 차수가 0인 노드들을 큐에 삽입 3. 큐에서 노드를 꺼내 연결된 간선을 .. 2021. 8. 20.

티스토리툴바