0. 학습 목적크루스칼 알고리즘의 목적과 작동원리를 이해한다.최소 스패닝 트리가 무엇인지 이해한다.트리와 그래프의 차이점을 이해한다.1. 크루스칼 (Kruskal) 알고리즘이란?주어진 그래프 내에서 최소 스패닝 트리를 찾는 알고리즘이다.그리디한 방식을 진행되며, 내부에서 트리 구성원 여부를 가리기 위해 유니온 파인드를 활용한다. (1) 그래프와 트리의 차이둘 다 간선과 정점으로 이루어져 있지만, 다음 항목에서 차이를 보인다. 구분그래프트리사이클의 여부사이클이 존재할 수 있다.사이클이 없다.간선의 개수간선의 개수를 특정할 수 없다.정점이 N개라면 간선의 개수는 N-1개이다.(2) 최소 스패닝 트리란?그래프 내에 트리의 조건을 만족하면서도 가중치 비용이 최소 비용인 부분집합을 의미한다.여기서 트리의 조건은 ..

0. 학습 목적iterator.next()를 활용하여 Collections의 자료구조들을 순회하면서, 자료 구조 내의 값들을 수정하려고 하면 ConcurrntModificationException이 나는 이유를 이해한다. Fail-Fast Interator와 Fail-Safe Iterator의 차이를 이해한다.1. Fail-Fast 전략과 Fail-Safe 전략Fail-Fast 전략 은 시스템 작동 중 실패 지점이 생기면 그 즉시 모든 작동을 멈추는 전략이다. 이는 실패 지점에 대한 명확한 판단과 일관성 유지를 목표로 한다.Fail-Safe 전략 은 시스템 작동 중 실패를 맞딱뜨린 상황에도 작동을 중단하지 않는다. 다만 최대한 실패가 커지지 않는 방향으로 나아가는 전략이다.Java는 Iterator 패턴..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/22861(1) 조건 분석 📊폴더 구조 형성 명령어맨 마지막에 1이 오면 폴더 간의 부모-자식 관계를 나타냄맨 마지막에 0이 오면 특정 폴더에 파일 삽입 명령어폴더 이동 명령어폴더 A, 폴더 B 구조로 알려주면 폴더 A를 B로 옮긴다.폴더 하위 파일 수 + 파일 유형 출력 명령어2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, 자료구조 먼저 개념을 나누고자 한다.직속 파일: 해당 폴더에 존재하는 파일이다.하위 파일: 해당 폴더의 하위 폴더 중 어딘가에 존재하는 파일이다.(0) 폴더의 종류를 구분하는 이유폴더 정리 (small)를 풀면서 직속파일과 하위파일을 구분없이 누적하여 풀었던 풀이자들은 해당 풀이..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/22860(1) 조건 분석 📊문제에서 요구하는 폴더의 하위 파일 종류와 개수를 출력하라.main 폴더 아래 같은 이름의 폴더는 2개 이상 존재할 수 없다.한 폴더는 자신의 레벨에서 같은 이름의 파일을 두 개 이상 가지지 못한다.```bash-- 불가능 예시FolderAㄴfile1ㄴfile1 # 2. 코드가 나오기까지 🛠️**`KEY WORD`: `자료구조`, `유니온파인드`** ## (0) 자료 구조 세팅해당 문제는 다음과 같은 이유로 HashMap 3개와 유니온 파인드용 `parents` 배열이 필요하다.1. 폴더 이름만 주어진다. 폴더 이름으로는 index 활용 풀이가 어렵다. - 계층 구조 표현 ..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/22859(1) 조건 분석 📊/* * 1. main 태그 지우기 v* 2. div 별로 구분 v* 3. div에서 title 추출해서 출력 v* 4. div 내부에 P태그 하나당 다음 과정 진행 * (1) P 태그 내부의 모든 태그 지우기 * (2) 문장 시작과 끝의 공백 지우기 * (3) 공백 2개짜리는 하나로 바꾼다. * (4) P 태그 자체를 지우기 * */ 2. 코드가 나오기까지 🛠️KEY WORD: 정규 표현식 정규 표현식으로 div 태그 추출 -> title만 빼서 출력정규 표현식으로 p 태그 추출 -> 위의 4가지 과정 하고 글만 출력(1)..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/22856(1) 조건 분석 📊중위 순회로 나오는 마지막 노드를, 문제에서 주어진 조건인 '유사 중위 순회' 방식으로 노드를 순회 했을 때, 몇 번의 이동만에 중위 순회 상 마지막 노드에 도달할 수 있는지 이동 횟수를 구해라여기서 이동이란 하나아ㅢ 노드에서 다른 노드로 한 번 움직이는 행위이다.2. 코드가 나오기까지 🛠️KEY WORD: DFS 중위 순회 마지막 노드 구하기유사 중위 순회 구현해서 마지막 노드까지의 방문 횟수 구하기(1) 시간복잡도 분석 ⏳최대 노드 개수가 $100,000$ 개 인데, DFS는 $O(V + E)$ 임으로, $200,000$ 개를 안 넘는다.3. 코드 🌐import java.i..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/21922(1) 조건 분석 📊문제에 나온 물건 4가지에 따라 바람의 방향이 바뀌는 것을 나타내는 게 관건이다.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, BFS 매번 사방 탐색하는 것이 아니고, 초기에 정한 방향을 물건을 만나지 않는 한 유지해야 한다.물건을 만나면, 그것에 맞게 방향을 바꿔줘야 한다.방향 배열을 썼고, 각 물건마다 함수화하여 그것에 맞게 방향을 바꿔주는 것으로 구현했다.(1) 시간복잡도 분석 ⏳최악의 경우 4방 움직임 모두가 전체 연구실을 돌 수도 있다. 그 경우를 계산해보면,$2,000 \times 2,000 \times 4 = 16,000,000$ 번의 연산 횟수가 된다.3..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/20165(1) 조건 분석 📊턴이 존재하고, 매 턴마다 공격자가 공격하고, 수비자가 수비한다.공격자의 행동은 다음과 같다.특정 도미노를 동서남북 중 한 방향으로 넘어트린다.해당 도미노의 길이-1만큼 그 방향의 도미노가 넘어진다.연쇄작용이 일어난다. (즉 넘어진 도미노의 길이만큼 그 이후 도미노가 추가로 더 넘어지고, 이것이 더 이상 넘어질 도미노가 없을 때까지 반복한다.) 수비자는 도미노 하나를 일으켜 세운다.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, BFS 공격을 구현할 수 있느냐가 문제 풀이의 관건이었다.필자는 재귀가 시간 소모를 높이고 계산을 복잡하게 만들 것이라 판단되어 BFS로 이를 ..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/20164(1) 조건 분석 📊현재 조회 중인 수의 자릿수 중 홀수 인 자릿수의 개수 세기계산은 다음과 같이 진행현재 보는 수의 자릿수가 1이면 계산 종료자릿수가 2이면 두개로 쪼개서 더한 뒤에 1번부터 다시 시작자릿수가 3이상이면 임의로 3덩어리의 숫자로 쪼갠 뒤 전부 더하기. 이후 1번부터 다시 시작2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션, 완탐문제에서 제시된 조건을 전부 표현하면 된다. 자릿수가 최대 9개이고, 재귀를 거듭할수록 자릿수의 개수는 줄어들 것이므로, 시간 초과 걱정은 없다.3. 코드 🌐import java.io.*;import java.util.*;public class Mai..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/17837(1) 조건 분석 📊A. 말에 대한 규칙말은 각자 나아가려는 방향이 있다.하나의 칸에 여러 말이 있을 시, 윷놀이처럼 기존에 있던 말이 새로 해당 칸에 온 말을 업는다. (stack)하나의 말이 자신의 방향으로 움직일 때 업힌 말들도 같이 움직인다. (이떄 자신의 나아가려는 방향은 바뀌지 않는다.)말들은 자신이 나아갈 다음 칸의 색깔에 따라 행동이 미세하게 바뀐다.B. 보드 칸 별 규칙흰 칸을 밟을 경우, 업은 말 전부 같이 움직이는 거 외에 특이 사항 없음빨간 칸을 밟을 경우, 자신을 포함한 업은 말들의 위치가 거꾸로 되어야 한다.(exA->B->C (TOP) 순으로 업혀 있었다면, C -> B -..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42747(1) 조건 분석 📊현재 확인 중인 논문의 인용횟수가 h번 이상, 전체 논문 중 h번 이상 인용된 논문의 수도 h개 이상이 될 수 있는 h값의 최대값을 구하라2. 코드가 나오기까지 🛠️KEY WORD: 정렬 정렬로 풀면 된다는 것은 명확했는데, 문제는 저 문장을 어떻게 해석할 것이냐다.내가 잘못 풀었던 지점까지 더해서, 설명하면 두 가지로 나뉠 수 있을 것 같다.오름차순으로 전체 논문의 인용횟수를 정렬이제 배열의 첫 번째 논문부터 순회하며 2번을 시행한다.2-1 현재 조회 중인 논문의 인용 횟수 확인, 이후 그 오른쪽 논문의 수를 확인하여,인용 횟수 2..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746(1) 조건 분석 📊배열에 주어진 숫자들을 일렬로 나열해서 최대값을 만들어야 한다.[6, 10, 2] -> 62102. 코드가 나오기까지 🛠️KEY WORD: 정렬, Comparator배열 진행은 다음과 같이 한다. a, b 가 있다고 했을 때,ab, ba 구조의 숫자를 만든다 .이 둘의 대소관계를 비교해서 내림차순으로 정리한다.이를 위해서 Arrays.sort() 를 사용했고, int를 Integer Wrapper Class로 교환했다.이렇게 한 이유는 Arrays.sort()에 두번째 인자인 Comparator를 오버라이딩할 경우, 첫 번째 인자가 객..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/427483. 코드 🌐import java.util.*;class Solution { public int[] solution(int[] array, int[][] commands) { int [] answer = new int [commands.length]; for(int i = 0; i 4. 트러블 슈팅 or 배운 점📝없음.

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628(1) 조건 분석 📊이중 우선순위 큐는 다음 연산이 가능한 자료구조를 의미한다.I 숫자: 형태의 명령어는 큐에 주어진 숫자를 삽입D 1: 큐에서 최댓값을 삭제D -1: 큐에서 최소값을 삭제2. 코드가 나오기까지 🛠️KEY WORD: 우선순위 큐, HashMap maxHeap, minHeap Java에는 최대값과 최소값을 ArrayDeque처럼 머리와 꼬리에서 동시에 뺄 수 있는 자료 구조가 없기 때문에, 우선순위 큐를 두 개 활용하여야 한다.이때 많은 사람들이 궁금해할 것은 '어떻게 이 둘의 Sync를 맞출 거냐' 는 것일 거다.만약 숫자 내림차순 ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627(1) 조건 분석 📊Job의 요소로는, 작업의 번호, 작업의 요청 시각, 작업의 소요 시간이 있다. Job은 매 초마다, 대기큐에 적재된다.대기큐는 다음과 같은 약속으로 내부 우선순위가 정해진다.소요 시간이 짧을수록 우선순위가 높다.소요 시간이 같다면 요청 시각이 빠를수록 우선순위가 높다.소요시간, 요청시각이 같다면, 작업 번호가 작을수록 우선순위가 높다.디스크는 하나의 일을 그것의 소요시간만큼 해낸다.이때, 임의의 작업이 그것의 요청시각부터 끝날때까지 걸린 시간을 a라고 했을 때, 모든 작업의 a의 평균을 구하라. 2. 코드가 나오기까지 🛠️KEY WO..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626(1) 조건 분석 📊주어진 모든 음식의 스코빌 지수가 K를 넘어설 때까지 가장 안 매운 두 음식을 합친다.음식을 합치는 공식은 다음과 같다.섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)2. 코드가 나오기까지 🛠️KEY WORD: 우선순위 큐맵기 오름차순으로 줄 세운다.큐 맨 앞의 음식이 전체 음식 중 스코빌 지수 최소값임으로 이것이 K보다 높으면 모든 음식이 K보다 지수가 높다는 것이다. (이때 계산 반복문을 탈출한다.)두 개 뽑아서 합친다.예외 처리:큐 안에 음식이 하나 이하로 남..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584(1) 조건 분석 📊매초 주식 가격이 하나씩 나온다.하나의 주식 가격이 그 밑으로 떨어지지 않은 기간을 구하여라[!example][3,1,2,3] 으로 각 초마다의 주식 가격이 주어졌을 경우,0초의 주식 가격은 그 다음 초에 1로 바로 떨어진다. 따라서 가격이 떨어지지 않은 기간은 1초이다.반면 1초대의 주식가격은 주식 가격 배열이 끝날 때까지 그보다 밑으로 떨어지지 않는다.2. 코드가 나오기까지 🛠️KEY WORD: STACK 활용 STOCK이란 클래스를 만든다. 멤버변수는 해당 주식 가격이 나왔던 초(index)와 가격(price)이다.STACK에 ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42583(1) 조건 분석 📊대기 중인 트럭이 순서대로 다리를 지난다. 다리는 길이와 내구도 무게가 존재하는데, 최대 그 길이 수만큼의 트럭만 올라갈 수 있으며, 올라간 트럭의 무게 합이 다리의 내구도 무게를 넘어서면 안된다. 트럭은 1초에 다리를 한 칸씩 건넌다. 한칸 = 다리의 길이/1 2. 코드가 나오기까지 🛠️KEY WORD: 큐 활용 모든 대기 트럭이 다리를 지날 때까지 반복해야한다.반복의 기준은 초단위이다. 1초마다 버스가 움직이고, 새로운 버스가 다리에 들어오기 때문이다. 문제에 제시된 조건 그대로 구현하면 되는 것이라서, 추가 설명은 SUDO CO..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42587(1) 조건 분석 📊각 프로세스는 무조건 우선순위가 높은 순으로 실행된다.이때 인수로 주어진 숫자가 원래 대기 큐 상 위치인 프로세스가 실행되는 순서는 언제일까?2. 코드가 나오기까지 🛠️KEY WORD: 큐 활용 프로세스의 실행 우선순위가 높은 것부터 내림차순한 우선순위 큐 만들기(우선순위 큐는 '실행 대기 중인 프로세스 중 우선순위가 높은 순' 이다.프로세스의 원래 위치를 담은 일반 큐 만들기우선순위 큐의 peek()의 우선순위 == 프로세스의 poll()의 우선순위이면, 현재 프로세스 실행해도 된다. 이때 해당 프로세스는 이미 실행 후 종료했으므..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12909(1) 조건 분석 📊( 문자로 열렸으면 반드시 ) 로 닫혀야지만 올바른 괄호 라고 부를 수 있다.문제에서 주어진 예시 문자열이 올바르면 true, 아니면 false를 출력하라.2. 코드가 나오기까지 🛠️KEY WORD: 스택 활용 사전 설정: top = stack의 맨 윗부분을 가리킴(이 들어오면 top++ 이후 해당 자리에 새로운 값 집어넣기)이 들어오면 현재 top 위치의 값 지우고, top-- 하기 ) 가 들어왔는데, top == -1 이면, 이미 현재 문자는 자신의 짝이 없다는 것이므로 false를 출력전체계산 이후에 stack이 비어있다면, 모..

1. 문제에 대하여 📦문제 링크: http://school.programmers.co.kr/learn/courses/30/lessons/42586(1) 조건 분석 📊각 기능은 진도가 100%일 때 배포가 가능하다.기능마다 순서가 있고, 후순위 기능이 먼저 진도 100%가 되었어도, 선순위가 아직 진도 100%가 아니면 기다려야 한다.선순위가 100%가 되면, 그것의 연속된 후순위 진도 100%인 것도 같이 배포된다.(즉 특정 날짜에 [100%, 100%,, 0%, 100%] 로 되어 있는 경우, 첫 기능과 두 번재 기능만 배포 되고, 4번째 기능은 3번째가 100%가 될 때까지 기다려야 한다.)2. 코드가 나오기까지 🛠️KEY WORD: 큐 활용문제에서 제시한 그대로 구현하면된다.필자는 큐를 활용했..