궤도

문제 풀이 그냥 모든 배열을 탐색하면서 풀면 시간복잡도가 O(n^2)이 나와서 시간초과가 뜬다. 그러니까 투 포인터를 써야한다. myunji.tistory.com/362 [백준] 2470번 : 두 용액 문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용 myunji.tistory.com 이 문제에서는 양방향에서 좁혀왔는데, 이번엔 한쪽에서 출발할 것이다. 일단 8이하의 모든 소수를 저장한 배열이 있다고 하자. 양 포인터 사이에 있는 모든 수를 합하면 2가 나온다. 우리의 목표 숫자인 8보다 작다. 그럼 오른쪽 포인터를 하나 증가해서 범위를 넓혀준다. 원래 한..

문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용하기 위해 배열을 정렬한다. 투 포인터라는 뜻은 포인터를 2개 사용한단 것이다. 포인터들은 양쪽에서 출발할 때도 있고 한쪽에서 출발할 때도 있는데 이 문제는 양쪽에서 출발할거다. 양 포인터가 가리키는 값들을 합하면 -1이 나온다. 일단 이게 -1과 가장 가까우니까 저 두 조합을 저장해두고... -1은 0보다 작으니까 두 수의 합이 커져야 한다는 뜻이다. 오름차순 정렬이기 때문에 빨간 포인터를 오른쪽으로 옮기면 합이 커지고, 파란 포인터를 왼쪽으로 옮기면 합이 작아질 것이다. 그러니 빨간 포인터를 오른쪽으로 옮..

문제 풀이 루트노드를 직접 찾아야 한다는 것을 몰라서 많이 헤맸다. 그것만 아니었어도 30분은 아꼈을텐데... 이 문제를 보자마자 제일 먼저 한 생각은 레벨 순회를 해야겠다는 것이었다. dfs에 속한다고 볼 수 있는 preorder, inorder, postorder와 달리 level traversal은 bfs에 속한다. 아무튼 이걸 사용해서 각 레벨별 정점을 정리해야겠다고 생각했다. level1 - 1 level2 - 2, 3 level3 - 4, 5, 6, 7 이런식으로 저장될테니 나중에 레벨마다의 너비를 구할때도 각 레벨의 첫번째 값과 마지막 값의 길이만 구하면 된다. 근데 문제는 각 정점의 열을 구하는 것이었다... 처음에는 분할정복으로 각 정점의 열을 구했는데 이것도 문제는 없는 코드였다. 굳이..

문제 풀이 myunji.tistory.com/287 [백준] 1697번 : 숨바꼭질 문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아 myunji.tistory.com 이 문제에서 지나온 경로를 추가하는 코드만 추가하면 된다. bfs를 통해 거리를 갱신하면서 직전 위치도 함께 저장한다. 그리고 도착점부터 시작점까지 거슬러 올라가며 스택에 쌓고 출력하면 된다. 소스코드 #include #include #include #include using namespace std; const int MAX = 100000; pair pos[MAX + 1]; que..

문제 풀이 일단 다른 섬끼리 다리를 이어야 하기 때문에 각각의 섬을 구분해야 한다. 이런식으로 말이다. myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 myunji.tistory.com 이 문제에서처럼 dfs를 사용해 각 섬을 구분지을 것이다. 그리고 가장자리에 위치한 모든 땅들에 대해 bfs로 최단거리를 구하는데 만약 이전의 bfs로 구해놓은 최단거리가 4 였다면 거리가 4보다 커질 때 bfs 탐색을 종료해 시간을 아낀다. 소스코드 #include #include..

문제 풀이 이런 그래프가 있다고 하자. 이 그래프를 탐색할 시 선택의 순간이 2번 있다. 바로 1번 정점과 2번 정점에서이다. 1번 정점에선 2번 또는 3번 정점으로 갈 수 있다. 2->3의 순서로 큐에 넣어도 되고 3->2의 순서로 큐에 넣어도 된다. 2번 정점에선 마찬가지로 4->5 또는 5->4의 순서로 큐에 넣을 수 있다. 이 순서는 순전히 처음에 그래프의 연결된 정점을 어떤 순서로 저장했느냐에 따라 달라진다. 1->2, 3으로 저장했다면 2->3의 순서로 큐에 들어갈 것이고 1->3, 2로 저장했다면 3->2의 순서로 큐에 들어갈 것이다. 입력된 방문 순서에 따라 정점의 저장 순서를 바꿀 것이다. 먼저 인접 정점의 정보를 이렇게 저장했었다고 가정하자. 1->2, 3 2->1, 4, 5 3->1,..

문제 풀이 굉장히 비효율적인 방법으로 풀었는데 시간초과가 나지 않았다. 문제를 풀고나서 효율적으로 작성한 코드를 몇개 봤지만 도통 이해가 되지 않아서...강해져서 돌아와야겠다. 아무튼 내가 한 비효율적인 방법은 정점의 개수만큼 dfs를 실행한 것이다. 최대 입력이 3,000이라 시간초과가 발생할 것이라고 생각했는데 그렇지 않았다. 사실 다른 효율적인 방법을 나름 시도해봤지만 영 제대로 풀리지가 않았다. myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 그..

문제 풀이 myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 사이클을 찾는 방법을 배웠다. 이번에도 똑같은 방법으로 dfs를 하면서 사이클을 찾으면 된다. 그냥 사이클 여부만 확인하면 되는거라 간단한 문제다. 소스코드 #include #include #include #include using namespace std; vector board; //문자, 방문여부 int N, M; bool isCycle; pair dir[4] = {{-1, 0}, //상 ..