문제https://school.programmers.co.kr/learn/courses/30/lessons/42890 풀이 과정어려웠던 문제였다..속성 조합을 구한 다음 유니크 속성을 구하는 것까지는 아이디어를 내긴 했는데, 최소성에서 막혔다.결국 풀이를 참고해서 문제를 해결했다. 문제 접근 방식1. 속성 조합 구하기컬럼 개수가 n일 때, 속성 1 ~ n개를 선택하는 모든 조합을 구한다. 예시속성: 학번 = 0, 이름 = 1, 전공 = 2, 학년 =3조합 => [0, 1, 2, 3, 01, 02, ....... 0123]List combinations = new ArrayList();boolean[] visited = new boolean[columnLength];for (int i = 1; i 2...
Algorithm
문제https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 과정이 문제는 연결 리스트 문제이다. 처음에는 자바에서 제공해주는 LinkedList로 접근했었는데, 효율성 테스트에서 실패했다.이 문제는 리스트의 삽입/삭제를 효율적으로 처리할 수 있는 자료구조를 사용해야 한다. 왜 자바의 LinkedList는 실패하는 것일까?기본적으로 연결 구조는 삽입/삭제는 빠르고, 읽는 속도가 느리다.자바의 LinkedList는 노드 연결 구조를 가진다. 기본적으로 삽입/삭제 연산만을 보면 빠르지만, 삽입/삭제 시 해..
문제 풀이과정 DP를 사용하여 강아지 마리수에 대한 최소 행동횟수를 구할 수 있다. 문제 이해N = 7, M = 1, A = 2, B = 3 인 경우총 7마리의 강아지를 구하고, 닫힌 구간은 3 ~ 4이며, 한 번의 행동으로 추가할 수 있는 강아지 수는 2 또는 3이다.여기서 A또는 B 행동을 통해 닫힌 구간에 해당되면 강아지는 0마리가 된다. => 해당 구간의 마리수는 만들 수 없다. 문제 접근DP 배열 정의dp[i] = i 마리를 만들기 위한 최소 행동 횟수 닫힌 구간은 -1로 설정조건 단순화하기 위해 A, B 통일A 는 작은 수, B는 큰 수로 통일점화식i - A 또는 i - B 에서 왔는지를 검사둘 다 불가능하면 -1,둘 중 하나라도 가능하면 그 중 최소값 + 1 코드import java..
문제문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 과정처음에는 info와 query를 하나씩 비교하여 조건을 만족하는 지원자를 찾는 방식으로 접근했었는데, 시간초과로 실패했다.해결 방법이 마땅히 떠오르지 않아, 정답 풀이를 참고해보았다. 문제 접근 방식1. 모든 경우의 조건을 Map에 관리하나의 지원자 정보가 만들 수 있는 조건을 모두 생성하여 Map에 관리한다.key: 조건value: 점수(리스트)예시: java backend junior pizza 150 => 총 16개의 조합을 ..
문제 풀이 과정이 문제는 도시의 모든 집이 연결되어 있으면서, 최소 비용을 구하는 문제이다.=> 최소 신장 트리를 활용하는 문제이다. 최소신장트리(Minumum Spanning Tree: MST)란?무방향 그래프에서 선택한 트리 중, 모든 노들을 포함하면서 가중치의 합이 최소가 되는 트리를 말한다.최소신장 트리를 찾는 대표적인 알고리즘크루스칼(Kruskal)프림(Prim) 문제 접근모든 간선(x, y)과 가중치(z)를 리스트에 저장한다.모든 간선에 대한 전체 비용(cost)을 구한다.리스트를 가중치(x)를 기준으로 오름차순한다.크루스칼 또는 프림을 통해 MST에 포함된 간선들의 가중치(minCost)를 합산한다.전체 간선의 비용(cost)와 MST에 포함된 간선(minCost)을 빼서 절약 비용을 구해 ..
문제풀이 과정N과 M 최대값이 2,000,000,000이므로 완전 탐색으로 풀기에 시간 초과가 발생할 것이다.문제 조건을 잘 이해해서 패턴을 찾아야 풀 수 있는 문제이다. (그리디) 이동 방법2칸 위로, 1칸 오른쪽1칸 위로, 2칸 오른쪽1칸 아래로, 2칸 오른쪽2칸 아래로, 1칸 오른쪽 위 조건을 따져보면,세로 길이 N이 특정 길이 이상이라면 위 아래로 이동하기 때문에 무제한으로 이동할 수 있다.즉, 세로 길이가 특정 길이를 넘어간다면 가로 길이가 길어질수록 방문 횟수가 커진다. N = 1일 때세로가 1이므로 이동 불가이므로 시작위치 방문칸은 시작 위치뿐이다.if (N == 1) { result = 1;} N = 2일 때세로 길이가 2이므로 이동 방법 중 2, 3번 방법만 선택 가능하다이동횟수 4..
문제 풀이 과정학생 이름이 주어질 때 인기도가 높은(많이 언급된) 학생부터 출력하는 문제이다.인기도가 같으면 학생 이름 기준으로 오름차순 정렬하여 출력한다. 문제 접근입력 받기학생 이름을 Map의 key로 저장한다.학생 인기도를 Map의 value로 저장하여 관리한다.이름이 언급되면 해당 학생의 인기도(value)를 +1 증가해준다.Map map = new HashMap(); // key=이름, value=인기도 StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i 정렬map.entrySet()은 set을 반환하는데, set은 순서를 유지하지 않으므로 ArrayList로 변환한다.sort() 메서드를 통해 리스트..
문제 풀이 과정길이가 서로 다른 N개의 과작 주어질 때, 같은 길이의 조각 M개를 만들 수 있는 최대 길이를 구하는 문제이다. 문제 조건막대 과자를 자르는 것은 가능하지만 붙이는 것은 불가능하다.길이가 1 선형 탐색(잘못된 접근)처음에는 이 문제를 선형 탐색 방식으로 접근을 했었다.과자 중 최대 길이(MAX_LEN)를 구한다.MAX_LEN부터 1씩 길이를 줄여나가면서 시도한다.각 길이(len[i])에 대해 현재 길이(l)로 만들 수 있는 조각 수를 계산한다.M개 이상이면 결과 저장 후 종료한다.long MAX_LEN = Long.MIN_VALUE;Long[] len; for (int i = 0; i 0; l--) { long count = 0; for (int i = 0; i = M)..
문제 풀이 과정피보나치 문제를 풀어보았다면 어려움이 없는 문제이다.피보나치 수열과 비슷한 규칙을 가지는 수열에서 N번째 수를 출력하는 문제이다. 규칙f(n) = f(n-1) + f(n-3)f(1) = f(2) = f(3) = 1N의 범위는 1 ~ 116이므로 int형의 범위에 벗어나는 경우가 발생하므로 long형 사용 재귀를 활용한 풀이(메모제이션 X) => 시간 초과메모제이션 없이 재귀로 풀었을 때 중복 계산이 많아지므로 시간 초과가 발생한다.public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new Buffered..
문제 풀이 과정1번부터 시작해서 가장 멀리 있는 방까지의 거리를 구하는 문제이다.방은 N개, N-1개의 연결 정보가 주어지며, 양방향으로 연결되어 있다. 이 문제에서 주의할 점은 입력값 C의 범위가 1 ~ 1,000,000,000 이다.결과를 구할 때 C(거리)에 대한 누적 거리를 구해야 하므로 LONG 타입을 사용해야 한다.저는 이것 때문에 계속 실패했어요.... 입력값 저장 방식입력 예시N = 4A = 1, B = 2, C = 3A = 2, B = 3, C = 2A = 2, B = 4, C = 4 각 인덱스가 방 번호를 나타내며, 인접한 방과 거리 정보를 저장한다.graph.get(1) => [Node(number = 2, distance = 3)]graph.get(2) => [Node(number ..
