728x90 분류 전체보기118 프로그래머스 - 섬 연결하기 (Java, 최소 신장 트리(MST), 크루스칼) 아이디어최소 신장 트리 (MST, Minimum Spanning Tree)크루스칼 알고리즘 최소 신장 트리의 경우 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재한다.크루스칼 알고리즘 (Kruskal Algorithm) : 간선 수가 적은 경우(희소 그래프, Sparse Graph)에 적합.프림 알고리즘 (Prim Algorithm) : 간선 수가 많은 경우(밀집 그래프, Dense Graph)에 적합. 크루스칼 알고리즘으로 문제를 풀었다. 크루스칼 알고리즘1. 간선 가중치 기준 오름차순 정렬2. 가중치 작은 간선부터 사이클을 만들지 않는 간선 선택 (= 그리디)3. 간선을 최소 신장 트리 집합에 추가 (트리 간 병합)사이클이 발생하는 경우= 특정 간선에 대한 양쪽 노드가 이미 같은 트리에 포함되어 .. 2025. 3. 5. 프로그래머스 - 구명보트 (Java, 투포인터) 아이디어투포인터 풀이어차피 2명씩밖에 못 타니,가장 무거운 사람과 가장 가벼운 사람을 함께 태울 수 있다면 함께 태워버리고아니라면 무거운 사람만 태우도록 했다. 먼저 정렬을 한다.가장 가벼운 사람에 대한 인덱스는 태울 때마다 증가하게 되고, 방문 처리를 해야 한다.방문 배열을 따로 만들거나 2중 반복문을 사용하는 대신 투포인터로 퉁쳤다.무조건 보트 수는 증가하게 되므로, 둘을 함께 태울 수 있을 때만 offset(가장 가벼운 사람 인덱스)을 증가시킨다. (근데 이게 그리디가 맞나...? 그리디 쥐약이라 그냥 투포인터로 풀었다)코드import java.util.*;class Solution { public int solution(int[] people, int limit) { int an.. 2025. 3. 5. 프로그래머스 - 큰 수 만들기 (Java, 그리디) 아이디어그리디 풀이먼저, 큰 수를 유지하려면 앞쪽에 나오는 수가 뒤쪽에 나오는 수보다 커야한다. 현재 수를 기준으로 현재 수가 다음 수보다 큰 지는 알 수 없으므로 현재 수는 answer에 무조건 추가한다.(현재 수와 answer의 수들만 비교할 것이다.) 처음에는 현재 수가 answer의 마지막 수보다 큰 경우 마지막 수를 제거하는 방식으로 접근했다.그러나 이 방식에서는 answer의 제거된 수 앞에 현재 수보다 작은 수가 여전히 남아있을 경우 최적해를 가질 수 없게 된다.그래서 answer의 마지막 인덱스부터 순회하여 현재 수보다 작은 수가 존재한다면 이를 모두 제거하도록 하였다. 만약 제거된 수가 k보다 작다면, 이는 추가된 수 앞에 이보다 작은 수가 없어서 제거 없이 계속 추가된 경우이다. 그러므.. 2025. 3. 5. 프로그래머스 - 조이스틱 (Java, 그리디) 아이디어먼저 이 문제는알파벳을 업데이트 하는 것과이동하는 것두 가지로 쪼갤 수 있다.알파벳 업데이트알파벳을 업데이트 하는 것은 단순히 A로부터 현재 알파벳에 도달하는 격차와,Z로부터 현재 알파벳에 도달하는 격차 + 1 중 더 작은 것을 선택하면 된다. 이동틀린 풀이이동하는 것이 문제인데, 처음에는 잘못 생각해서 다음과 같이 풀이를 했었다.현재 위치를 0으로 잡고 왼쪽, 오른쪽 거리를 매긴다왼쪽에서 가장 가까운 Not A, 오른쪽에서 가장 가까운 Not A 간의 거리를 비교한다더 가까운 쪽을 선택하여 현재 위치를 업데이트하고, Not A인 알파벳의 갯수를 감소시킨다.만약 Not A인 알파벳 갯수가 0이라면 종료. 종료 전까지 1 ~ 3 반복나머지 예제는 전부 맞았지만, 예제 3번에서 오답이 나왔다."BBB.. 2025. 3. 5. 프로그래머스 - 전력망을 둘로 나누기 (Java, 완전 탐색, bfs) 아이디어1. 연결된 노드 리스트 생성2. 간선 제거3. bfs 탐색연결된 노드 리스트 생성양방향 연결임에 주의하며, 특정 노드에 연결된 모든 노드들에 대한 리스트를 생성하여 map에 담아주었다.간선 제거wire들을 순차적으로 탐색하며, 현재 인덱스에 대한 wire를 제거한다.이는 곧 연결된 두 노드의 각각의 리스트로부터 반대쪽 노드를 제거하는 것과 같다.유의remove(index) : 리스트에서 특정 index에 해당하는 값 제거remove(Integer.valueOf(value) : 리스트에서 특정 value 제거bfs 탐색트리에서 하나의 간선을 끊게 되면, 반드시 2개의 트리로 분리된다.한 쪽 트리에 대해서만 탐색을 하면 나머지 트리에 속한 노드 수도 자연스럽게 알 수 있다.먼저 시작 노드를 정해주었.. 2025. 3. 5. 프로그래머스 - 소수 찾기 (Java, 백트래킹, 소수, 에라토스테네스의 체) 아이디어백트래킹 + 에라토스테네스의 체 백트래킹완전탐색, 순열, 조합 문제의 경우 백트래킹을 먼저 시도해보는 편이다. 일반적인 dfs 알고리즘에 visit 체크를 앞, 뒤로 추가하여 중복 방문을 막는다.딱히 종료 조건이랄 것도 없어서 종료 조건은 따로 주지 않았다. 에라토스테네스의 체소수를 판정하기 위해서는 특정 수보다 작은 수들로 나누어 떨어지는지 확인한다.하지만, 특정 수보다 작은 모든 수를 탐색하는 경우 시간초과가 발생할 수 있다.그러므로 에라토스테네스 체 알고리즘을 따라서 제곱근까지만 탐색한다.sqrt 사용 시 부동 소수점 오류가 날 수 있어서 역으로 생각하여 i * i 가 x보다 작거나 같은 경우까지 탐색해주었다. 마지막으로 중복값 제거를 위해서 Set을 사용했다. 코드import java.u.. 2025. 3. 4. 프로그래머스 - 이중우선순위큐 (Java) 먼저 이중우선순위큐를 구현하기 위해서 유의해야 할 점매번 정렬을 하는 것은 비효율적 (시간초과 문제) 풀이 1. 우선순위 큐 2개 (최대힙과 최소힙) 구현PriorityQueue : 중복값 허용. 삭제 시 중복값 존재하는 경우, 우선순위가 높은 값 하나만 삭제.import java.util.*;class Solution { public int[] solution(String[] operations) { int[] answer = { 0, 0 }; PriorityQueue minQ = new PriorityQueue(); PriorityQueue maxQ = new PriorityQueue(Collections.reverseOrder()); for(S.. 2025. 3. 4. AWS Developer Associate (DVA-C02) 7일의 전사 후기 먼저 이 글은 상당히 편한 말투로 작성되어 있음을 양해 부탁드립니다. 서론클라우드 관련 자격증 하나 따고 싶다는 생각도 있었고, 비즈니스 로직 구현에는 조금 익숙해졌으나 클라우드 인프라나 아키텍쳐 쪽으로 조금 더 공부해보고 싶다는 생각이 있어서 클라우드 대빵인 AWS의 자격증을 따기로 했다.사실 자격증 따려고 마음 먹은 거는 약 4개월 전인데 그동안 너무 바빴다... 접수 방법https://aws.amazon.com/ko/certification/certification-prep/testing/ AWS Certification 시험 일정 예약온라인 시험 감독은 집이나 사무실과 같이 사적인 공간에서 시험을 치를 수 있는 시험 응시 환경입니다. 자신의 컴퓨터로 시험에 응시하고, 화면 공유 애플리케이션과 웹캠.. 2025. 2. 20. 이전 1 2 3 4 ··· 15 다음 728x90
