Algorithm
[백준] 5014번 - 스타트링크
☞ 이번 문제는 풀면서 정말 많은 방법들을 갖고 접근해보았다. 처음에는 재귀를 이용해 풀려고 했는데, 재귀를 끝내기 위한 조건을 찾는 와중에 어떻게 하면 Up and Down을 계속 지속하며 뺑뺑 도는 부분은 나올 수 있을지에 대한 부분에서 막혔었다. 그래서 다른 방법을 찾아 보았고, 대부분 어떤 점에서 다른 점까지의 거리를 구하는 문제에 사용되는 너비우선탐색(BFS)법을 사용해보았다. ● BFS로 풀기 위해 해당 건물을 인접리스트의 형태로 표현 해보았다. int tmp[2] = { U, -(D) }; for (int i = 1; i > F >> S >> G >> U >> D; adj = vector(F+1); int tmp[2] = { U, -(D) }; for (int i = 1; i
[백준] 2178번 - 미로 탐색
이 문제는 위의 그림과 같이 입구(0,0)에서 출구(N-1,M-1) 까지의 거리를 찾는 문제이다. 거리를 찾는 문제이기 때문에 너비우선탐색을 이용해서 푸는 방법을 쉽게 생각 할 수 있었다. matrix를 이용해서 문제를 풀면 간다하며 마지막으로 저장되어진 dist 행렬에서 N-1,M-1번째 수만 결과를 출력하면 간단하게 풀 수 있다. 여기서 더욱 더 시간을 줄이기 위해 방향을 아래와 같이 행렬에 저장하였다. int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} }; #include #include #include #include #include using namespace std; int N, M; int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} }..
[백준] 11266번 - 단절점 (Articulation Point)
이 문제의 유형은 깊이 유형 탐색을 통해 절단점을 찾는 것이다. 절단점이란? - 무향그래프에서 어떠한 점의 인접한 간선들을 모두 지웠을 때 -> 해당 Component가 2개로 나뉠때의 어떤한 점이 절단점 ● 어떠한 점이 절단점이 될 수 있을 조건 - 2가지 1) 기준점이 u일때 자손 v들이 역방향 간선을 통해 u의 선조들로 올라갈 수 있을 때 if (!root && subtree >= discovered[here]) { isCutVertex[here] = true; } subtree = isCutVertexDfs(there, false) 의 의미는 현재 점의 역행 간선이 존재 할 때 자신의 선조 어느 곳까지 올라 갈 수 있는지 보여준다. 따라서 subtree는 discovered를 저장하기 때문에 su..
[백준] 10942번 - 팰린드롬?
이번 문제는 팰린드롬이라는 생소한 단어가 나왔는데, 문제에서 팰린드롬의 정의를 해주지 않아 인터넷에 팰린드롬이라는 단어를 찾아봤습니다. 위키백과에서는 palindrome을 회문이라 했으며, 회문이란 숫자나 문자를 정방향으로 읽어도, 거꾸로 읽어도 같은 숫자나 문자를 말합니다. 처음에 이 문제를 해결하기 위해서 각 위치에 맞는 짝을 찾아 비교하기 위해 규칙을 찾아보았는데, 따로 규칙을 찾을 필요없이 우리가 S, E를 선택했기 때문에 (S+i) = (E-i) 라는 규칙을 쉽게 생각 할 수 있었습니다. 그리고 이 문제 조건에서 시간 제한을 0.5초를 두었기 때문에 Dynamic programming을 이용해야 함을 알 수 있었습니다. int palin(int s, int e) { if (s >= e) { re..
[c++] 입력은 여러 개의 테스트 케이스로 이루어져 있다.
문제의 조건에 이런 까다로운 것이 있을 때, c++에서는 어떻게 해결하면 될까? ● 보통 c++을 사용하는 개발자들이라면 scanf 대신 cin을 많이 사용 할 것이다. cin에는 EOF라는 모듈이 있는데, eof 기능을 사용하면 쉽게 해결된다. int a, b; while (true) { cin >> a; if (cin.eof() == true) { break; } //여기에 결과 값 입력! } 여기서 주목해야할 점은 cin.eof인데 ctrl+x를 입력할 때 프로그램에 끝냄 명령을 주는데, 이때 cin에 입력받은 값이 없을 때 신호를 주면, cin.eof는 true값을 반환을 하여 while문을 빠져나오게 된다. 따라서, 쉽게 저 조건을 해결 할 수 있게된다. 궁금하신 것이 있으시다면 언제든지 댓글로..
[백준] 1725번 히스토그램 & [프알문] 울타리 잘라내기
이번 문제는 1725번 히스토그램인데, 프알문의 울타리 잘라내기 문제와 풀이 방식이 똑같아 포스팅하였습니다. 울타리 잘라내기와 마찬가지로 이 문제를 브루트포스로 접근하게 되면 시간복잡도가 너무 높으므로 분할 정복으로 접근하였습니다. 지금부터 울타리를 반으로 쪼개며, 확장을 하면서 분할 정복을 할 것입니다. 먼저 기저사례를 기본적인 분할 정복에서의 기저사례와 같은 left==right일시 기본 높이 값을 반환해주며, 그 후 left~mid, mid+1~right로 나누어 계산을 할 것입니다. 먼저 반으로 쪼개가며 확장을 시키면 모든 케이스를 확인 할 수 있습니다. 그렇기 때문에 반으로 쪼개가는 것이고, 확장을 시킬 때 왼쪽으로 갈지 오른쪽으로 갈지는 더 높은 케이스를 찾아가도록 설정을 해주었습니다. #in..