전공
-
백준 1644(소수의 연속합)전공/알고리즘 2020. 6. 25. 00:53
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 www.acmicpc.net 겨울에 스터디하면서 서강대 raararaara님에게 배운 문제. 그치만 강의가 좋다고만 생각했지, 백준 문제 풀 생각은 전혀 안 했었다. 그러다가 오늘 친구가 풀어보라길래 그때 생각이 나서 강의록을 참조하였다. 이 문제는 부분합 문제이다. 부분합 문제는 여러가지 알고리즘이 있는데 이렇게 정렬된, 연속한 합을 구할 때는 투포..
-
백준 2206(벽 부수고 이동하기)전공/알고리즘 2020. 6. 25. 00:43
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net N, M 이 마무리이고, 벽은 한번만 뚫을 수 있으며, 최단 거리로 간다. 모든 가능한 경우를 확인해서, 그 중 가장 짧은 거리를 출력한다. 위 조건들을 보고 이 문제는 무조건 dfs다 라고 생각했다. 하지만 시간초과의 문제에 봉착했고, bfs로 돌렸다. dfs의 시간초과 여부를 계산하는게 아직 많이 어렵다. 아 근데 dfs로 풀린 코드도 있다. 이게 어떻게 가능했는지..
-
백준 9019(DSLR)전공/알고리즘 2020. 6. 22. 16:06
https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스� www.acmicpc.net BFS에 대해서 좀 더 생각하게끔 해주었던 문제. 앞서 풀었던 치즈같이 queue 두 개를 이용해서 총 몇번의 횟수가 필요한지 구하려고 했었다. 하지만 문제는 문제에서 요구하는 바가 횟수가 아닌 경로였고, 경로를 구하려면 재귀의 방식이 필요하지 않을까 생각을 하였다. 재귀로 경로를 출력하기에 더 편리하게 느껴졌다. 경험이 있어서 그런지 그래서 재귀와 bfs를 동시에 사용하면 어떨까..
-
백준 2636(치즈)전공/알고리즘 2020. 6. 19. 15:07
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제에서 요구하는 게 무엇인지 제대로 파악하고, 논리를 구성해야 하는 문제. 치즈가 공기와 닿으면, 녹는다. 다 녹을 때 까지 얼마나 걸리는가, 녹기 직전 치즈의 양은? 가장 핵심은 먼저 초기에 공기와 닿는 치즈의 좌표를 구하는 일이었다. 가장자리의 공기부터 시작해서 이어진 모든 공기를 구분하고, 가장 처음 만난 치즈는 무조건 치즈의 가장자리가 되므로 그 좌표들을 치즈의 테두리로 정한다. 치즈의 테두리를 queue1..
-
백준 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 로 해주어서 한번 조사한..