목록전체 글 (616)

1일1알

백준 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
백준 1085번 직사각형에서 탈출 C++

#include #include #include #include #include #include using namespace std; int main() { int x, y, w, h; int min = 1001; cin >> x >> y >> w >> h; //x좌표 비교 (0에서 x까지의 거리와 w에서 x까지의 거리) if (x > w - x) { if (w - x h - y) { if (h - y < min) { min = h - y; } } else { if (y < min) { min = y; } } //네 개의..
알고리즘 2021. 10. 15. 15:11
이전 Prev 1 ··· 100 101 102 103 Next 다음