문제 파악https://www.acmicpc.net/problem/1717풀이집합을 합치는 행위를 수행하거나, 두 원소가 같은 집합인지 리턴해주기만 하면 된다루트 개념을 가져가면 쉽게 풀이할 수 있다.말로 풀어 설명하자면 부분집합의 대표(루트)를 설정하고, union 시 하나의 대표로 병합해 준다.이전에 풀이한 최소 스패닝 트리 문제와 유사하게 풀이했다. (https://diggingcode.tistory.com/70)이런 경우 대체로 1차원 배열을 선언해서 풀이하는 편이다.초기에는 각 원소들이 부분집합의 대표이므로 배열에 스스로의 인덱스를 할당해준다.이를 탐색 및 union 시 업데이트 해 주도록 하자.재귀적으로 루트를 찾는 함수를 호출하도록 구현하였다.코드import java.io.*;public c..

문제 파악https://www.acmicpc.net/problem/1074풀이재귀적으로 순서대로 방문한다..?재귀보고 눈이 돌아가서 재귀/큐로 풀었다가 OOM을 만났다 🙂‍↕️더보기OOM 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReade..

문제 파악https://www.acmicpc.net/problem/1101어려운 점보통 카드를 옮기는 문제는 한 개씩 옮긴다고 생각하기 마련인데, 이 문제는 1개 이상의 카드를 한 번에 옮긴다는 점이 독특했다.규칙을 단순화하는 게 까다로웠던 것 같다! 풀이카드를 한 번에 많이 옮길 수 있다는 점과, 조커 박스가 있다는 점을 주목해야 한다.정리가 필요한 박스에서 최대한 많이 꺼내서 다른 정리가 필요한 박스로 옮겨주고,최종으로는 조커 박스에 몰아넣으면 최소 이동이 된다.여기서 정리가 필요한 박스란 다음과 같다.두 가지 이상의 색깔이 섞여 있는 경우한 가지 색상으로만 이루어져 있으나, 동일 색상으로 이루어진 또 다른 박스가 있을 경우만약 1 카드만을 가진 박스가 5개라면, 그 중 4개만 손봐야 한다 구현은 두..

문제 파악https://school.programmers.co.kr/learn/courses/30/lessons/77886 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이크게 두 가지 구현이 필요하다주어진 문자열에서 110을 모두 제거규칙에 따라 110들을 사전순으로 이른 위치에 삽입1. 주어진 문자열에서 110을 모두 제거StringBuffer를 활용하여 주어진 문자열을 순환하며 가장 끝자리가 110이라면 삭제하고,그렇지 않으면 계속 버퍼에 쌓아주자2. 규칙에 따라 110들을 사전순으로 이른 위치에 삽입규칙을 찾기 위해 세 자리까지만 나열해 보도록 하자..한 자리 수두 자리 수세 자리 수0 ➡️ 0..

문제 파악https://www.acmicpc.net/problem/17070아직 첨부하지 않았지만 파이프를 배치하는 예시도 그림으로 제시해 주는 친절한 문제이다 🥹풀이DP로 풀게 되었다.파이프의 배치를 보면 ↘️ 방향으로 진행되므로, 행과 열이 증가하는 방향으로 조사하며 DP 배열을 업데이트하면 될 것이다.DP 변수의 선언과 초기화파이프를 배치하는 경우의 수를 저장하는 3차원 배열을 선언하여 사용해주도록 한다.이 때 가로 | 세로 | 대각선 파이프가 끝나는 위치를 기준으로 배열을 업데이트해주면 편하다.따라서 (0,0)에 가로 파이프가 놓여 있는 경우 DP[0][1][가로파이프]에 해당하는 부분이 1이 되겠다.파이프 배치 방법앞서 말했듯 파이프의 끝점(↘️ 방향)을 기준으로 한다.가로 파이프(R,C) 기..

문제 파악https://www.acmicpc.net/problem/1679풀이DP 문제이다.동전 문제와 유사한 방법으로 풀 수 있다. (참고 : 동전)풀이 단계는 다음과 같다. DP 배열 선언 및 초기화DP 배열은 정수를 만들기 위해 필요한 정수의 최소 사용 횟수를 저장한다.예를 들어 DP[100]는 100원을 만들기 위해 필요한 정수의 최소 개수이다. DP 배열의 최대 크기는 '가장 큰 후보 정수 * K + 2' 로 설정한다.3,4,5 정수를 최대 10번 사용 가능하다면 51까지 연산을 필요로 한다. 보다 편한 연산을 위해 DP[0]은 0으로 초기화해 주고,그 외의 원소는 '가장 큰 후보 정수 * K + 1' 로 초기화해주었다. 최솟값 계산가장 작은 후보 정수부터 시작해 최솟값을 업데이트해 준다.문제에..