전공/알고리즘
-
백준 1697(숨바꼭질)전공/알고리즘 2020. 6. 17. 13:57
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 조건들을 추가해서 더 쉽게 접근할 수 있을까. 고민을 해보았지만, 반례들이 존재했다. 그래서 그냥 bfs로 완전탐색을 하였다. dfs대신 bfs를 선택한 이유는 이 문제는 전형적인 턴제의 문제여서이다. 그리고 만약에 dfs로 접근을 한다면, 멈출 조건을 설정하는 것이 너무 까다롭게 된다. 그래서 턴제의 bfs를 선택하였다. *2 , +1, -1 을 계속해서 한 뒤에 몇 ..
-
백준 1260(dfs와 bfs)전공/알고리즘 2020. 6. 17. 12:49
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제에 써있듯이 dfs랑 bfs를 구현할 수 있는가 묻는 단순한 문제이다. 여기서 중요한것은 bfs를 할 때, vector를 이용해서 인접리스트를 만드는 것이다. vector는 push_back, pop_back이 있어서 거의 queue처럼 사용할 수 있다는 것을 알아야 한다. 처음에는 이렇게 할 수 있다는 걸 모르고, 이차원 벡터로 만들어서 풀려다가 엄청나게..
-
백준 7576(토마토) bfs전공/알고리즘 2020. 6. 16. 15:00
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 딱 보고 bfs라고 생각이 든 문제. 이 문제를 통해서 bfs와 dfs의 작동원리 차이점을 좀 더 이해할 수 있게 되었다. dfs는 한 번 가면 끝이 없다. 끝을 볼 때 까지 간다. (return 이 될때까지 돈다.) bfs는 턴이라는 개념이 있다. 주변을 다 돌고, 한 턴이 지나고, 다음 턴이 시작이다. 문제에서 하루가 지나면 익은 토마토에 인접한 안 익은 토마토가 익는다고 했..
-
백준 10026(적록색약) dfs전공/알고리즘 2020. 6. 16. 13:36
https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 서로 같은 색의 인접한 것들끼리만 묶었을 때, 몇 가지로 분류할 수 있는가. 이제는 딱 봐도 탐색문제이다. dfs는 재귀함수이다. 따라서 핵심은 언제 return 할 것이고, 분류를 언제 끝냈다고 할 것인가이다. 1. 벽에 부딪히면 return한다. (index의 범위를 벗어나거나, 다른 색을 만났을 때) 2. 인접하면서 같은 색인 경우에 visited 를 true 로 해주어서 한번 조사한..
-
백준 1389(케빈 베이컨의 6단계 법칙 ) 플로이드 와샬전공/알고리즘 2020. 6. 15. 13:52
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 가장 적은 거리로 연결되는 index를 찾는 전형적인 그래프 문제. dfs로 풀었지만 dfs를 이용해서 풀었을 때 정확한 시간복잡도 계산도 모르겠고, 해서 다른 알고리즘을 찾아보았다. 플로이드 와샬 모든 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 a->b로 가는 최단 경로를 알아보려면, (a -> b) vs (a->c + c->b) 이..
-
백준 1012(유기농 배추) 그래프전공/알고리즘 2020. 6. 10. 14:33
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 엄청나게 쉽다고 생각한 문제 엄청나게 틀린 문제 대충 보자마자 방법을 알아챘다. 좌표를 입력받을 때마다 인접한 곳에 대해서 확인 후에 있으면 그 당사자 좌표를 갯수에서 빼주는 것이다. 그렇게 바로 코드를 짰고, for (int i = 0; i > a >> b; bug[a + 1][b + 1] = true; if (bug[a + 1][b + 2]) cnt++; else if..
-
백준 1461(도서관) 맞왜틀?전공/알고리즘 2020. 6. 9. 13:20
맞는데 왜 틀렸지? 라는 생각을 갖게된다. 나의 논리가 완벽하기에 나를 너무 믿기에 자꾸 틀린걸 알면서도 제출버튼을 클릭하고 제출한다. 알고리즘 문제를 풀다보면 논리의 허점을 찾기가 정말 힘들다. 단순 예제를 만들어서 확인해볼 생각도 안 하고, 확인했던 것만 확인하고 틀린다. 멍청 이 문제도 그랬다 그냥 결론은 딱히 없고 예제좀 제대로 넣고 풀어보자 처음부터 논리적으로 완벽하긴 더 힘들거 같으니깐 제발 https://www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치� ww..
-
백준 1080(행렬)전공/알고리즘 2020. 6. 8. 14:38
https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 문제를 정말 잘 읽어봐야 하는 문제. 이 문제에서 N*M의 행렬을 3*3의 부분행렬의 값을 1->0 0->1 로 변경하여 A와 B의 행렬이 같게 만드는 문제이다. 처음에 부분행렬이라고만 봐서 모든 부분행렬을 따져봐야 되나 이런 생각을 해보았다. 전체탐색으로 풀려고 했다. 왜냐하면 행렬의 변환이 무작위라고 느껴졌기 때문이다. 전체탐색 재귀로 풀게된다면 시간복잡도는 O(2^n)이므로 2^50, 약 10^17 엄청난..