개발/알고리즘11 [백준 5014][C++] 스타트 링크 간단하게 BFS로 풀리리라고 생각했는데 생각보다 많이 틀렸다. 내가 관과했던 점은 18번째 줄이다. S == G 인 경우, 그리고 U 나 D 가 0인 경우 18번째 줄이 없으면 오답이 된다. 또, 처음에는 int형 배열 graph의 값이 0일 경우를 아직 방문하지 않은 경우로 표현했는데 (bool형 visited 사용하지 않았다) 이 경우 역시 U 나 D 가 0 일 경우 문제가 된다. 문제에서 나오는 범위를 유심히 확인해봤다면 틀리지 않을 수 있었던 문제 !! 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 34 35 36 37 38 39 40 41 42 #include #include #in.. 2020. 2. 9. [백준 2644][C++] 촌수계산 일단 풀고 나서 다른 사람들의 풀이를 보니... 내가 굉장히 이상하게 풀었다. 사람들의 수 n이 1push_back(curInd); } int main() { memset(graph, -1, sizeof(graph)); int N; int p1, p2; int M; cin >> N >> p1 >> p2 >> M; for (int i = 0; i > to >> from; graph[from] = to; } vector v1; vector v2; findHead(p1, &v1); findHead(p2, &v2); for (int i = 0; i 2020. 2. 7. [백준 1005][C++] ACM Craft 이 문제에서 배웠던 것은 그래프 문제에서 시작 지점을 찾기가 애매할 경우 오히려 도착 지점을 시작 지점으로 선택하는 방법도 있다는 점. 왜냐? 도착 지점은 항상 정해져 있기 때문에 어디서 끝날지 조건만 확실하게 정해주면 된다! (물론 간선의 방향은 초기화시 반대로 설정해야 한다) 그 후 재귀를 이용한 DFS로 풀었다. Node의 prevSum 변수로 직전 노드까지 경로의 weight들의 합을 계산하여, 여러번 계산함으로써 오는 성능 저하 문제를 해결하려고 했다. 또한 BFS는 그래프가 트리 구조가 확실하고, 회전하는 구조가 아닐 때 사용하는 것이 좋다. 이 문제의 경우도 BFS로 풀게 되면 각 노드들의 레벨을 따져주어야 하는 점이 골치아파진다. 이럴땐 DFS를 쓰자! 1 2 3 4 5 6 7 8 9 10.. 2020. 2. 6. [백준 2493][C++] 탑 이 문제에서 배운 것들 정리 시간복잡도 계산 내 코드의 경우 N 개의 입력에 대해서 O(N^2)인 것은 맞는 것 같다. (빅 오 표기법의 경우 최악의 경우를 따지므로) 하지만 실제로 이런 케이스는 N개의 입력 각각이 모두 N^2번의 연산을 하는것이 아니기 때문에 테스트 케이스를 통과하는 것이 아닐까 싶다. 모든 입력이 N^2번의 연산을 하지 않는 이유는 스택에서 삭제하는 연산 때문에 검사해야할 스택 크기 자체가 줄어들기 떄문이다. 알고보니 O(N)짜리 코드였다. 스택에 넣고, 삭제하는 연산을 N번 만큼 하기 때문!! 유의할 점은 이중 반복문이라고 해서 N^2이라고 생각하면 안된다는점. 참고 링크 : https://www.acmicpc.net/board/view/9807 글 읽기 - 탑 문제 - 시간복잡도.. 2020. 1. 23. [백준 10799][C++] 쇠막대기 굳이 스택을 이용하지 않고 문자열만 다루어서 풀 수도 있는 문제였다. 여는 괄호는 일단 스택에 넣어준다. 그리고 닫는 괄호를 기준으로 생각해 보면, ( ) 처럼 연달아서 여는 괄호, 닫는 괄호가 나올 경우 레이저를 뜻하고, ) ) 처럼 닫는 괄호들이 이어진다면 이는 막대기의 끝 부분을 의미한다. 레이저의 경우는 현재 스택의 크기만큼의 조각이 생기고 (18번째 줄) , 막대기의 끝 부분일 경우 해당 막대기의 끝 부분, 즉 1개의 조각이 더 생긴다. (20번째 줄) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #include using namespace std; int main() { stack pipes; .. 2020. 1. 23. 이전 1 2 다음
