알고리즘/백준 BAEK JOON
-
14503.로봇청소기알고리즘/백준 BAEK JOON 2020. 6. 1. 00:51
이번에 풀어볼 문제는 백준 14503 로봇청소기이다. 시뮬레이션 분류의 문제이며 문제 이해만 잘하면 풀 수 있는 문제이다. 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 하지만 제대로 이해못하거나 설계를 잘못하면 미궁속에 빠져서 푼거 또 풀고 푼거 또 풀게된다... 나 역시 1주일전에 풀다가 틀린 부분을 못찾아서 1주일 후에 다시 푸는데 성공했다(그사이에 늘긴 늘었다보다..) 내가 실수했던 부분은 후진에 대한 내용이다. 4방향모두 갈곳이 없을 때 청소한 곳을 지나갈 수 있는 방법은 후진뿐인데 잘못이해해서 후..
-
16236.아기상어알고리즘/백준 BAEK JOON 2020. 5. 31. 15:06
이번에 풀어볼 문제는 백준 16236의 아기상어이다. 시뮬레이션 + 탐색의 문제이며 요즘 점점 설계의 중요성을 깨닫는다. 이 문제를 잘 풀기 위해서는 자신이 구하고자하는 내용들의 순서로직의 설계를 잘해주어야 한다. 아직 설계능력이 많이 미숙한 것 같다. 하다보면 늘겠지.. 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..
-
14890.경사로알고리즘/백준 BAEK JOON 2020. 5. 28. 03:04
이번에 푼 문제는 백준 14890 경사로이다. 난이도는 쉬우나 문제를 보자마자 괜히 쫄았다.. => 고쳐야할점 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 그리고 분석시간을 충분히 가졌으나 실수를 하나 하는바람에 분명히 맞게구현했는데 시간을 낭비했다. 찾아보니 나처럼 헤맨사람이 많았다. 이 문제에서 대부분 실수하는 부분은 경사로를 놓는 것에 있다. 나는 경사로를 한 번 놓으면 치우지 않은 상태에서 다른 경로를 찾는건가 했는데... 아니였다.. 가로일 때 경사로 놔서 가능한 길 찾아보고 세로일 때 다시 경사로가 모두 없는 상태에서 ..
-
1697.숨바꼭질알고리즘/백준 BAEK JOON 2020. 5. 27. 03:21
1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 이번에 풀어볼 문제는 백준의 1697 숨바꼭질이다. 어떻게 접근을 시작하는지, 설계를 시작하는지에 따라 체감하는 난이도는 크게 차이가 날 것 같다. 나같은 경우에는 금방 풀이법을 찾아냈다. 대부분이 금방 찾아내는 경우라면 쉬운편에 속하는 것이고 아닌 사람들 굉장히 헤맬 것이다. 결론을 말하자면 이번문제는 BFS로 간단하게 풀어낼 수 있는 문제이다. 주의할 점이 있다면 같은 연산을 줄이는 것이다. 이것만 주의하면 충분히 풀 수 있는 문제..
-
2468.안전영역알고리즘/백준 BAEK JOON 2020. 5. 26. 23:01
이번에 풀어볼 문제는 백준의 2468 안전영역이다. BFS, DFS(재귀,스택,큐)로 풀이가 가능하다. 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 나는 BFS를 이용해서 풀이를 진행하였고 난이도는 역시 그렇게 어려운 편은 아니다!! 모든 문제가 그렇지만 설계단계를 잘생각해서 진입해야 헤매지 않고 풀이에 성공할 수 있다. 이 문제는 직전에 포스팅 한 문제들과 다를 바없이 탐색이 문제를 푸는관건이 아니라 탐색 이전까지의 로직을 구현해내는 것이 관건인 문제이다. 이 문제에서는 물에 잠기는 최소높이와 최고높이를 저..
-
1012.유기농 배추알고리즘/백준 BAEK JOON 2020. 5. 26. 00:33
이번에 풀어볼 문제는 백준의 1012 유기농 배추이다! 이 문제는 BFS나 DFS를 이용해서 풀면 되는데 역시나 난이도는 높지않다. 여기서 배울 점은 나눠진 영역의 탐색(BFS, DFS)을 진행하는 방법이다. BFS를 기준으로 설명을 적어놓았다 -> DFS든 BFS든 탐색방법만 다를 뿐 구현 로직은 같다. 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 이 문제에서 Key Point는 1. 맵에 배추를 잘 넣어주는 로직과 2. 영역별로 나눠져 있는 배추를 탐색하는 것이다. 1번은 간단하기 때문에 조금만 생각하면 가능니..
-
7576.토마토알고리즘/백준 BAEK JOON 2020. 5. 25. 21:18
이번 문제는 토마토이다! 비교적 쉬운 문제에 속한다. BFS를 이용하면 간단히 풀 수 있는데 BFS로 퍼지면서(토마토가 익으면서) 내부의 값(걸리는 시간값)을 잘 지정해주어야한다! 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net #pragma warning(disable:4996) #include #include #define MAX 1001 using namespace std; int n, m; int map[MAX][MAX]; int dx[4] = { -1, 1, 0..
-
14502.연구소알고리즘/백준 BAEK JOON 2020. 5. 25. 07:09
이번 문제는 연구소이다. 꽤 많이 중요한 내용을 배우고 상기할 수 있는 문제였다. 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 이 문제를 푸는데 핵심은 맵을 복사해서 사용한다는 것과 나머지는 탐색이다. 난이도는 어려운 수준이 아닌 거 같지만 초보자에게 연습하기는 좋은 문제인 것 같다( 난 초보자 ㅠㅠ.. 너무좋네...) 재귀함수 관련된 문제를 조금 더 풀어봐야할 것 같다. * 문제풀면서 중요한점 1. 문자, 특수기호 실수 => 실수로 자꾸 if문 다음에 변수에 값을 대입할 때 "=" 대신 "=="를 사용하여 틀림 주의..