본문 바로가기

알고리즘

 (82)
유니온 파인드(Union Find) 각 개체들의 집합 상태를 트리로 표현한 하나의 자료 구조다. 도식화한 모습이 트리 형태란 거지, 실제로 트리 자료구조를 직접 구현해야 하는 것은 아니다. 정확히는 각 개체들끼리 공통 부분이 없어야 한다는 조건이 있지만, 이 설명은 서로소란 것에 대한 수학적 접근이 필요하므로 위키를 보는 것을 추천한다. + 대부분 블로그 설명을 보면 정점끼리 묶는 예시가 많고 이 블로그도 그렇게 작성했다. 다만, 어떤 경우에는 정점이 아닌 다른 부분들을 합쳐야 한다는 것을 알아두자. ex) 간선의 가중치 등 다음과 같이 1~5 까지의 노드가 있다. 처음 각 노드들의 root 노드는 자기 자신이다. (부모 노드라 하는게 맞는데 편의상 root로 함) Union 서로 다른 두 개체를 합친다. 정확히는 값이 낮은 개체로 uni..
프로그래머스 - 쿼드압축 후 개수 세기 분할 정복 문제 1. 정사각형을 같은 크기로 4등분(길이 / 2) 2. 루프를 4번 돌려서 4등분한 길이만큼 정사각형 분할 3. 1~2 의 작업을 길이가 1이될 떄 까지 반복 4. 길이가 1일 때 현재의 원소 반환 5. 이렇게 분할된 값들을 모아서, 0과 1이 각각 몇 번 나왔는지 셈 6. 루프를 통해 0이나 1이 4번 나오면 적절히 처리해줌 7. 6번에서 0이 4번 나오면 0반환, 1이면 1 반환, 아니라면 2 반환 8. 5~7 반복 코드 더보기 class Solution { int[] answer = new int[2]; public int[] solution(int[][] arr) { int ret; ret = divide(arr, arr.length, 0 ,0); // 모든 원소가 0이나 1인 경..
프로그래머스 - n^2 배열 자르기 예시 1번은 좌표료 표현하면 다음과 같이 표현할 수 있다. 여기서 규칙을 찾을 수 있다. 행과 열의 값중 최대 값 + 1이 해당 칸에 있는 수이다. 예를 들자면 (1, 2)에서 가장 큰 값은 2이고, 여기에 1을 더하면 3 그렇다면 공식을 다음과 같이 세울 수 있다. a = 행 / n b = 열 % n a, b 중 최대값 + 1 코드 더보기 더보기 class Solution { public int[] solution(int n, long left, long right) { int[] answer = new int[(int)(right - left + 1)]; int division = 0, remain = 0; int answerIndex = 0; while(left
프로그래머스 - 전력망을 둘로 나누기 dfs를 사용해 풀었다. 1. 1번 노드부터 dfs 실행. 방문한 노드는 다시 탐색하지 않는다. 2. 각 노드는 연결된 노드 중 방문하지 않은 노드들에 dfs 실행 3. 연결된 노드들에 대해 dfs가 끝난 노드는 자신을 포함해 dfs를 보낸 노드 수를 더한 값을 반환 ex) 예시 1번 기준 7번 노드에선 8, 9번 노드에 dfs를 실행하고 8, 9번은 각각 1을 반환 7번 노드에 대한 탐색이 끝났으면, 자기 자신을 포함해 3 반환. 4. 3번에서 반환된 값은 | (n - 반환 값) - 반환 값| 연산을 해 현재 답과 비교해 작은 것을 저장 5. 모든 노드의 탐색이 끝날 때 까지 2~4번 반복 이 결과가 끝날 때의 각 노드의 값들은 다음과 같다. (예시 1번 기준) 코드 더보기 더보기 import java..
프로그래머스 - 이진 변환 반복하기 평범한 level 2문제 replaceAll이 생각보다 빠르지 않단 것을 알았다. 풀이 순서는 다음과 같다. 1. 문자열 s에서 0의 개수를 센다. 2. 문자열 s의 길이 - 0의 개수를 이진변환 한다. 3. 1이 되면 1,2번을 반복한 횟수와 그 떄 까지 센 0의 개수를 반환 내 풀이와 결과 더보기 더보기 class Solution { public int[] solution(String s) { // 이진 변환 횟수, 제거된 모든 0 int[] answer = new int[2]; int zeroCount = 0; int round = 0; while(true) { answer[0]++; zeroCount = 0; for(int i = 0; i < s.length(); i++) { if(s.charAt..
프로그래머스 - 빛의 경로 사이클 30분 내로 풀 거를 이해 잘못해서 3시간 가량 소비한 문제 `_' 단편적인 것만 보고 거기에 맞추느라 고생했다. https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 문제에 중요한 힌트가 하나 있는데 한 격자에서 들어오고 나가는 방향은 언제나 똑같음. 이게 무슨 말이냐면 시작을 왼쪽위에서 아래서부터 하든, 오른쪽 아래에서 위에서부터 하든 도달하는 순서만 다를 뿐이지, 반드시 해당 방향..
0-1 BFS 간단한 BFS문제인줄 알았는데, 일반적인 bfs 그래프 풀이로는 메모리초과나 시간초과가 자명한 문제였다. 나름대로 최적화 기준을 세워서 풀어봤지만 한참을 틀린 뒤 태그를 보고 검색을 해보니 바로 이해가 됐다. 왜 0-1가 붙는데? 간선의 가중치가 0과 1밖에 없어서 그렇다. 즉, 비용없이 정점을 지나는 경우와, 비용을 들여 정점을 지나는 경우로 나뉜다. 이게 되게 난해한 부분이, 매 순간마다 비용없이 정점을 지나는 경우를 고려해 큐에 넣어야 하기 때문에 메모리가 초과되거나, 무한루프를 돌아 시간초과가 나버린다. 해결 방법 덱 자료형을 사용하면 편하다. 다른 자료형을 사용해도 풀 수 있지만, 개인적으론 덱이 편했다. 비용을 들이지 않고 지나는 경우엔, 덱의 선두에 넣어야 한다. 비용을 들이고 지나는 경우엔..
백준 [2065] 나룻배 단순 큐 문제여서 쉽게 생각했다가 한번 꼬이니 쭉 꼬여서 당황한 문제 처음엔 왼쪽과 오른쪽 큐를 만들어 독립적으로 관리했는데 이렇게 되다보니 현재 방향이 왼쪽이냐 오른쪽이냐 구분하는 코드로 너무 길어져서 큐 배열 2개로 만들어서 0, 1로 관리했다. 전체 코드 (스압 주의) 더보기 import java.io.*; import java.util.*; class TimeTable { int order; // 입력된 순서 int arriveTime; // 도착한 시간 public TimeTable(int order, int arriveTime) { this.order = order; this.arriveTime = arriveTime; } public int getOrder() { return order; }..

티스토리툴바