목록알고리즘 (528)

1일1알

백준 12851번 숨바꼭질2 C++

bfs로 풀 수 있는 문제인데 특이한 점은 가장 빠른 시간만 구하는 게 아니라 그 방법이 몇 가지인지까지 구해야 한다. 최초 도달했을 때 시간을 구하고 그 시간과 같은 시간에 도착 할때마다 Count를 증가시켜주면 된다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; vector visited(100001, false)..
알고리즘 2021. 10. 20. 12:46
백준 16953번 A->B (C++)

bfs로 문제를 해결하였다. 초기 cnt=1 처음 큐에 pair로 (A, cnt)을 넣고 (A * 2, cnt + 1) 와 (A * 10 + 1, cnt + 1)을 bfs로 탐색하면서 A의 값이 B의 값과 같아지면 cnt를 출력하는 방식으로 해결하였다. 같은 숫자를 또 방문하는 것을 방지하기 위해 탐색 시간 복잡도가 O(1)인 unordered_set에 방문한 값을 넣어줘서 중복을 방지하고, A * 2나 A * 10 + 1이 B보다 커지면 큐에 넣지 않는 식으로 구현하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef lo..
알고리즘 2021. 10. 19. 10:45
백준 11660번 구간 합 구하기 5 C++

dp 테이블을 이용하여 누적 합을 저장해서 풀 수 있는 문제이다. 예제의 숫자들을 각 행마다 누적 합을 저장하여 저장한다. (2,2)부터 (3,4) 까지의 합은 이 부분의 합을 구하면 되기 때문에 dp[2][4]-dp[2][2-1] + dp[3][4]-dp[3][2-1] = (14 - 2) + (18 - 3) = 27 이렇게 구할 수 있다. 이것을 코드로 나타내면 #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin...
알고리즘 2021. 10. 18. 13:19
백준 11725번 트리의 부모 찾기 C++

그래프, 트리 관련 문제이다. 우선 (n+1)*(n+1) 행렬을 만들어서 트리를 인접 행렬을 통해 나타내는 방식을 생각해볼 수 있다. 노드가 양방향으로 연결되어있기 때문에 (1,6)을 받으면 (1,6)과 (6,1) 모두 저장한다. 하지만 이런 방식으로 풀면 비어있는 공간도 모두 탐색하면서 시간이 오래 걸려 시간 초과가 날 것 같아서 다른 방법을 생각해보았다. 2차원 벡터를 사용하여 노드와 연결된 노드만 저장하는 방식이다. vector[1] : 4, 6 vector[2] : 4 .... 이런식으로 만들었다. 우선 루트가 1이라고 했으니 큐에 1을 넣고 시작한 뒤 노드 r을 1로 저장하고 pop을 한번 해준다. 그리고 vector[r] 을 탐색하면서 원소가 아직 방문이 되지 않았을 경우에 해당 원소를 큐에 ..
알고리즘 2021. 10. 17. 12:39
백준 9465번 스티커 C++

다이나믹 프로그래밍 bottom-up 방식으로 풀 수 있는 문제이다. 우선 두 가지 경우가 있다. 1. 왼쪽 위에서 시작하는 경우 2. 왼쪽 아래에서 시작하는 경우 1번의 경우를 예를 들어 살펴보면 한 칸 떨어진 대각선을 선택하는 경우와 두 칸 떨어진 대각선을 선택하는 경우로 나눌 수 있다. 다른 어떤 곳을 선택하더라도 결국 이 두 가지로 나뉜다. (100을 선택: 50->50->100, 20을 선택: 50->50->20 or 50->70->20, 10을 선택: 50->50->100->10) 위 경우들을 살펴보면 결국 위의 두 가지의 경우들의 조합으로 만든 선택임을 알 수 있다. 마지막 스티커까지 도달했을 때 1번의 경우와 2번의 경우 중 큰 값이 답이 된다. max(dp[0][n], dp[1][n]) ..
알고리즘 2021. 10. 16. 13:09
백준 4153번 직각삼각형 C++

#include #include #include #include #include #include #include using namespace std; int main() { int a, b, c; int arr[3]; while (1) { cin >> a >> b >> c; //while문 종료 if (a == 0 && b == 0 && c == 0) break; arr[0] = a; arr[1] = b; arr[2] = c; //오름차순 정렬 sort(arr, arr + 3); if (arr[0] * arr[0] + arr[1] * arr[1] == arr[2] * arr[2]) { cout
알고리즘 2021. 10. 15. 15:26
이전 Prev 1 ··· 85 86 87 88 Next 다음