Algorithm

427. Construct Quad Tree 이 문제는 보자마자 전형적인 분할 정복 문제라는 것이 보였고, 4개 분면으로 나눠가며 grid의 특정 범위 내의 모든 수가 같은 케이스에는 isLeaf 값을 참으로 갖는 node를 반환하는 식으로 한다면, size가 1x1인 grid 범위가 될 때 같은 베이스 케이스도 필요 없이 통과할 수 있다 생각해 아래 코드와 같이 작성했습니다.class Solution { public Node construct(int[][] grid) { return construct(grid, 0, 0, grid.length, grid[grid.length-1].length); } public Node construct(int[][] grid, int to..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제를 처음 접근할때 시간 제한이 0.1초인걸 보지 않고 당연히 1초라고 생각하여 N은 100,000이니 시간 복잡도는 O(N logN)이면 풀 수 있겠다는 생각으로 이분탐색의 형식으로 O(logN)으로 Insert함수를 만들고 N회 입력, Insert, 출력을 반복하는 main 함수로 작성하면 되겠다는 안일한 생각으로 접근을 했다. 그러나 vector.insert가 갖는 시간..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 내가 적록색약이라 적록색약자의 불편함을 알기에 공감하면서 푼 문제였다. BFS로 구현 했다. 입력받을때부터 일반인의 그림과 적록 색약의 그림을 나누어 저장했으며 저장한 그림을 매개변수로 받는 solve 함수를 작성했다. solve 함수는 전체 그림을 선회하며 방문하지 않은 칸을 방문하는데 한번 방문하면 같은 색인 영역을 다 확인하여 방문처리를 하고 cnt를 1 증가시키는 방식으로 코드를 작..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 전형적인 BFS를 사용하는 문제이다. 기본적인 BFS에서 추가되는 것은 "토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다."라는 문제조건인다. 이 조건은 토마토가 들어있지 않은 칸들로 인하여 익은 토마토와 접촉 할 수 없는 토마토가 생긴다. 때문에 모든 토마토가 익었는지 판단해야한다. #include "iostream" #include "algorithm" #inclu..