Algorithm46 [Programmers] Lv.2 _ [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 https://school.programmers.co.kr/learn/courses/30/lessons/340212풀이퍼즐 난이도: diffs소요 시간: times제한 시간: limit숙련도: level 퍼즐 난이도가 숙련도보다 낮거나 같으면 (diffs[i] 해당 퍼즐의 소요 시간 (times[i]) 만큼만 소요. 퍼즐 난이도가 숙련도보다 높으면 (diffs[i] > level)해당 퍼즐의 이전 소요 시간 + 현재 소요 시간 을 난이도 - 숙련도 만큼 수행 후 현재 소요 시간 추가 소요. 퍼즐의 모든 소요 시간의 합이 limit보다 작은 숙련도 최솟값 구하기. 퍼즐의 숙련도는 최소: 1, 최대: max(diffs) 로 범위가 정해져있으며,수행 가능한 숙련도의 경계값을 찾는 문제이기 때문에 이분탐색 문제.. 2025. 1. 5. [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. 이전 1 2 3 4 5 6 ··· 8 다음
