삼성 알고리즘에서 배웠던 것들 조금 고급이나 많이 접해보지 못한 것들 알고리즘이랑 자료구조들 공부해봅시다. 그래프란? 그래프는 노드랑 간선으로 이루어진 자료구조이고 순환 구조가 없는 걸 트리 자료구조라고 할 수 있음. 간선에 방향이 존재하는지 여부가 중요하니까 잘 파악할 것. 기본적인 DFS나 BFS는 많이 접해봤으니까 덜 접해본 알고리즘들을 공부해보자. 서로소 집합 (Union-Find) 오늘 풀었던 문제에서도 나왔는데 집합을 이루는지 확인하고 하나의 집합으로 만들 수 있는 그런 알고리즘. Union 연산 (합집합) 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산임. def union(a, b): parentA = find(a) parentB = find(b) if paren..

💡https://www.acmicpc.net/problem/1300 문제 설명 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. 출력 B[k]를 출력한다. 문제 풀이 해당 문제를 처음 보고 든 생각은 n의 값이 너무 크기 때문에 직접 정렬을 하는 방식을 이용할 수 없을 것 같다라는 생각이 들었습니다. 정렬을 한다면 메모리와 시간적으로 모..

💡https://school.programmers.co.kr/learn/courses/30/lessons/152995 문제 설명 ※ 문제에 대한 자세한 설명은 위 링크를 참조해주세요! 일단 해당 문제에서 찾아야 하는 것은 완호의 랭킹입니다. 그리고 이 랭킹을 알기 위해선 인센티브를 받을 수 있는지 여부가 모든 값들에 대해서 알아야 합니다. 현 시점에서 가장 간단하게 생각하면 모든 노드를 돌면서 해당 노드가 인센티브를 받을 수 있는지 여부를 체크하고 완호가 인센티브를 못받는 사람을 제외하고 자기보다 더 큰 사람의 수를 센다면 랭킹을 구할 수 있겠죠. 하지만 주어진 scores의 크기가 10만이기에 O(N^2)에 해당하는 알고리즘을 사용할 수 없습니다. 최대 O(NlogN) 정도로 풀어줘야합니다. 이때 잘 ..

💡https://www.acmicpc.net/problem/17484 문제 설명 ※ 문제에 대한 세부 내용은 위 링크를 통해 확인해주세요! 지구와 달 사이의 격자형 루트를 따라서 움직였을 때, 최소한의 연료를 쓰는 루트가는 경우 얼마의 연료가 소모되는지에 대해 알아야 하는 문제입니다. 일단 문제에서 볼 수 있는 부분이 입력 값 제한이 굉장히 작다는 생각이 들고 그래서 어떻게 풀어도 시간 제한으로 틀리는 경우는 드물 것 같다는 생각이 듭니다. 먼저, 제가 한 생각은 DP로 풀자는 생각이 들었습니다. 최소한의 연료 소모량을 구해야 한다는 부분과 이전까지 이동한 최소 연료 소모량을 이용해서 그 다음 위치에서의 최소 연료 소모량을 구할 수 있을 것 같다는 부분에서 DP를 생각했습니다. 방향이라는 제한이 없었으면..

더보기 🔗 https://school.programmers.co.kr/learn/courses/30/lessons/43238 문제 정보 ※ 자세한 문제에 대한 정보의 위의 링크를 참조해주세요! 제한 사항 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다. 심사관은 1명 이상 100,000명 이하입니다. 문제 요약 해당 문제에서는 아래와 같이 말합니다. 🗨️ 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. **하지만** 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고..

더보기 🔗 https://school.programmers.co.kr/tryouts/74944/ 문제 정보 ※ 자세한 문제에 대한 정보의 위의 링크를 참조해주세요! 제한 사항 1 ≤ grid의 길이 ≤ 500 1 ≤ grid의 각 문자열의 길이 ≤ 500 grid의 모든 문자열의 길이는 서로 같습니다. grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다. 문제 요약 문제에서 요구한 사항을 요약하면 다음과 같습니다. 격자에 ‘S’가 있으면 이전 방향 그대로 직진. 격자에 ‘L’이 있으면 좌회전. 격자에 ‘R’이 있으면 우회전. 격자 밖으로 나가면 0으로 이동 (순환되는 구조). 이러한 요구 사항이 주어졌을 때, 순환되는 경로의 길이를 배열로 받아서 오름차순으로 정렬 후 반환해야합니다. 문..