본문 바로가기

Algorithm45

[Programmers] Lv.1 _ 가장 많이 받은 선물 조건기록을 비교하여1. 기록이 존재할 경우 => 더 많이 준 사람의 선물 개수 +12. 기록이 존재하지 않는 경우 or 주고 받은 선물의 개수가 같은 경우 => 선물 지수가 더 큰 사람의 선물 개수 +13. 선물 지수까지 동일한 경우 => 선물을 주고 받지 않음 풀이입출력 예시에 친절하게 표가 나와있어 쉬운 문제긴 했다.먼저 주고 받은 선물 2차원 표, 선물 지수 1차원 리스트를 선언한다.선물 기록 리스트인 gifts를 돌며 준 사람, 받은 사람의 idx를 찾아 1) 준 사람은 선물 지수 + 12) 받은 사람은 선물 지수 - 13) 선물 2차원 표에 기록 ([준 사람 인덱스][받은 사람 인덱스])를 기록한다. 이후 2차원 표를 이중 for문으로 돌며 조건에 맞는 경우를 따져 최댓값을 찾는다. def so.. 2024. 6. 11.
16948_데스 나이트 ▶ 실버 1 (BFS) 풀이BFS를 이용하는 문제이다.먼저 이동할 수 있는 경우와 없는 경우를 구분하였다. (bfs를 돌리면서 이동할 수 없는지 확인할수는 없기 때문에 미리 거르는 방식으로)규칙을 찾아보니 1) x좌표(= r) 가 2의 배수인 경우, y좌표(= c)는 2k + 1이 성립.2) x좌표(= r) 가 4의 배수인 경우, y좌표(= c)는 2k 이 성립. 인 것이 보였다.이 때, 2의 배수는 4의 배수를 포함하고 있으므로 4의 배수일 경우부터 걸러야 한다. // 도착 불가인지 확인 int tmp1 = abs(r1 - r2); int tmp2 = abs(c1 - c2); if (tmp1 % 4 == 0) { if (tmp2 % 2 == 0) { ans = bfs(r1, c1, r2, c2);.. 2024. 2. 19.
3584_가장 가까운 공통 조상 ▶ 골드4 (트리) 풀이 부모 노드 값을 가지고 있는 배열: tree 조상을 담을 vector: A 를 선언하고 먼저 입력받은 간선 정보를 이용하여 각 노드의 부모 노드를 채워준다. 그 후, 공통 조상을 구할 두 노드 중 첫 번째 노드의 모든 조상 노드들을 A에 삽입한다. 마지막으로 두 번째 노드의 모든 조상 노드를 A에 삽입하는데, 이 때 A에 이미 존재하는 값이라면 이것이 두 노드의 공통 조상 노드이므로 그 값을 출력하고 배열과 vector를 초기화하고 다음 테스트케이스를 진행한다. 코드 #include #include #include #include #include #include #include #include #define MAX 10001 using namespace std; int tree[.. 2023. 8. 7.
1967_트리의 지름 ▶ 골드4 (트리) 풀이 노드들의 가중치 합 중 최댓 값을 구하는 문제인데, 중요한 것은 꼭 루트 노드를 포함해야할 필요가 없다. 그래서 모든 노드를 기준으로 dfs를 진행해서 가중치 최댓값을 구하면 된다. 코드 #include #include #include #include #include #include #include #define MAX 10001 using namespace std; int n; vector graph[MAX]; bool visited[MAX]; int ans; void dfs(int i, int value) { visited[i] = true; if (value > ans) { ans = value; } for (int j = 0; j < graph[i].size(); j++).. 2023. 8. 5.
11725_트리의 부모 찾기 ▶ 실버 2 (트리) 문제 풀이 처음엔 queue 를 선언하여 parent 배열이 다 채워질 때까지 노드 쌍을 queue에 다시 삽입하는 방법을 생각했다. 하지만 O(N^2) 시간복잡도로 시간 초과가 났다. 그래서 bfs, dfs 중 bfs를 이용하여 풀었다. 코드 #include #include #include #include #include #include #include #define MAX 100001 using namespace std; int n; vector tree[MAX]; queue q; bool visited[MAX]; int parent[MAX]; void bfs() { q.push(1); while(!q.empty()) { int start = q.front(); q.pop(); .. 2023. 8. 4.
11497_통나무 건너뛰기 ▶ 실버1 풀이 간단하게 수를 정렬하여 인접한 수의 차의 최대가 최소가 되도록 하면 되는데, 중요한 것은 첫 인덱스와 마지막 인덱스 역시 인접하다고 간주하는 것이다. 1, 2, 3, 4, 5가 주어진다면 가장 큰 수인 5를 중심으로 멀어질수록 정렬한 순으로 작아지면 된다. 결국, 1, 3, 5, 4, 2의 순으로 배치해야 최솟값을 구할 수 있다. 따라서 일단 주어진 배열을 정렬하고, 2칸 씩 건너뛰면서 수의 차를 확인한다. n이 짝수일 경우에는 n / 2번을, n이 홀수일 경우에는 n / 2번 시행한 후 마지막 인덱스도 포함하기 위해 한 번 더 시행한다. 코드 #include #include #include #include #include #include using namespace std; int ar.. 2023. 3. 16.

티스토리툴바