백엔드 개발자로 가는길

자바 - 프로그래머스 92344 / 파괴되지 않은 건물

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=java 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krlv3 풀이 방법문제 이해N × M 보드, 각 칸마다 초기 내구도.K개의 스킬이 [type, r1, c1, r2, c2, degree] 형태로 주어짐.type = 1(적 공격) → (r1, c1) ~ (r2, c2) 구간의 내구도 degree만큼 감소type = 2(아군 회복) → 해당 구간 내구도 degree만큼 증가스킬이 모두 끝난 뒤, 내구도가 1 이상인 칸의 개수를 세서 반환.왜 단순 완전탐색(O(K·N·M))이면 안 되는..

풀이 방법틀린 방식유니온 파인드를 통해 사이클 발생 여부 판단사이클 발생시 → 트리 없음 기록사이클 미 발생시, parent 배열을 통해 루트 노드 개수 카운팅틀린 이유사이클 발생 시, 해당 그래프만 트리가 아니고, 다른 그래프는 트리일 가능성 존재parent 배열이 최신 상태로 업데이트 되지 않은 경우, 루트 노드가 아닐 가능성이 존재한다.해결 방법사이클 발생 시 → 사이클 발생 노드 기록루트 노드를 parent 배열 말고, find()를 통해 찾기맞는 풀이유니온 파인드를 통해 사이클 발생 여부 판단사이클 발생시, 해당 노드에 사이클이라고 표시사이클 미 발생시, 루트 노드가 사이클인지 아닌지를 자식 노드 둘로 판단자식 노드 둘다 사이클이 아니라면 루트 노드도 사이클 아님find()를 통해 노드들의 루트..

https://www.acmicpc.net/problem/2169골드2풀이 방법단순 dfs로 하면 시간 초과 발생합니다. (시간 복잡도: O(3^(N * M))N, M(1≤N, M≤1,000)현재 문제는 “각 칸까지 올 수 있는 최적 해를 모아 두고, 그 위에서 다음 칸의 최적 해를 구한다”가 목표→ DP 생각하기이동 경로 가능 경로: 오른쪽, 왼쪽, 아래따라서 위에서 부터 오른쪽에서 왼쪽으로 갈 때 max값과 왼쪽에서 오른쪽으로 갈 때 max값을 구한 뒤두 값중 더 큰 값을 아래로 내려주면 된다.이때 시작은 0,0에서 하기 때문에 이 경우에는 왼쪽에서 오른쪽의 경우만 생각하면 된다.dp 시간 복잡도매 행마다 두 번의 선형 스윕을 수행하므로 O(N×M)코드import java.util.*;import j..

https://www.acmicpc.net/problem/2109골드3구현 방법하루에 최대 한 강연 + 강연마다 마감일과 강연료가 있음 + 최대 수익이 목표→ 작업 스케줄링 문제⇒ 그리디 알고리즘p 값(강연료)가 높은 순, p값이 같은 경우 d값(마감일)이 작은 순으로 정렬하면 답을 구할 수 있습니다.마감일이 같은 경우, 마감일에 가장 가까우면서 일정을 잡을 수 있는 일자로 선정합니다.visited 배열을 이용하여 가능한 일자를 구합니다.날짜 찾기 최적화기존 방식에서는 visited 배열을 이용해 각 날짜마다 강연이 배정되었는지 확인하고, 빈 날짜를 찾기 위해 매번 O(n)의 선형 탐색을 수행했습니다.이를 개선하기 위해 유니온 파인드의 find() 함수를 이용하기로 했습니다.parent[날짜] = 그 날..

https://www.acmicpc.net/problem/2533골드3구현 방법문제 조건에서 “친구 관계가 트리 구조”라고 했기 때문에 사이클이 없고, 모든 노드가 연결되어 있습니다.따라서 DFS나 재귀를 통해 트리 순회가 가능해집니다.상태는 2가지로 나뉩니다.얼리어답터인 경우 : 자신의 친구는 얼리어답터가 아니여도 됩니다.얼리어답터가 아닌 경우 : 자신의 친구는 무조건 얼리어답터가 되어야 합니다.상태를 보면 각 노드는 하위 서브 트리의 최적해에 의존한다는 것을 알수 있습니다.따라서 DP를 이용하기로 했습니다.결론트리 순회를 하면서 각 노드의 두 가지 상태에 대해 이미 계산된 최적해(최소 얼리 어답터 수)를 저장해두고, 이를 다시 활용함으로써 중복 계산을 피해 최소 얼리어답터인의 수를 구하도록 하겠습니다..

https://www.acmicpc.net/problem/1520골드3구현 방법잘못된 접근BFS를 통해서 상,하,좌,우 를 탐색하여1. 인덱스 범위에 있고,2. 갈 곳의 높이가 현재 높이 보다 작은 경우갈 수 있는 경로를 더해주는 방식으로 구현했습니다.또한 한번도 도착하지 않은 경우에는 큐에 넣어 탐색을 진행할 수 있도록 했습니다. 하지만 이렇게 하는 경우, 나중에 추가된 경로의 개수가 반영되지 않는 문제가 발생했습니다.이는 한 번 방문한 노드의 경우 다시 탐색하는 과정이 없기 때문에 추가된 경로의 개수가 업데이트되지 않기 때문이였습니다. 해결 방법나중에 경로를 추가하는 상황을 만들지 않도록 하면 됩니다.현재 문제에서는 높은 건물에서 낮은 건물로 간다는 방향성이 있습니다.이를 통해 다음 경로를 정하기 전..

https://www.acmicpc.net/problem/1027골드4구현 방법1. 서 있을 건물을 정한다.2. 볼 건물을 정한다.3. 사이 건물들이 시야를 가리는지 확인한다.  a. 사다리꼴 면접 공식으로 최대 건물 높이를 구합니다.  b. 큰 사다리꼴 = 사이 건물 높이로 나눠진 사다리꼴 + 사이 건물 높이로 나눠진 사다리꼴4. 사이 건물들이 시야를 안 가릴 경우, 볼 수 있는 건물수를 하나 늘린다. 주의 사항범위를 주의해야합니다.최대 높이가 1,000,000,000이기 때문에 계산 과정에서 오버플로우를 조심해야합니다. 개선 방법사다리꼴 면접으로 중간 높이를 구하지 않고, 기울기 차이로 판단 가능합니다. 코드import java.util.*;import java.io.*;/** * 백준 1027 * ..

https://www.acmicpc.net/problem/1939골드3구현 방법1. 문제 조건N: 섬의 수 (2 ≤ N ≤ 10,000)M: 다리의 수 (1 ≤ M ≤ 100,000)C: 다리의 최대 중량 (1 ≤ C ≤ 1,000,000,000)두 섬 사이의 여러 경로 중, 한 번의 이동에서 옮길 수 있는 물품들의 최대 중량을 구해야 한다.다리마다 중량 제한이 존재하며, 이를 초과하면 경로로 사용할 수 없다.2. 완전탐색의 비효율성만약 BFS를 통해 모든 가능한 경로를 탐색하는 방식으로 접근하면:시간 복잡도는 최악의 경우 O(2^M)에 도달할 수 있다.이유: 각 다리를 선택하거나 선택하지 않는 경우의 수를 모두 고려해야 하기 때문이는 M=100,000일 경우 비현실적으로 많은 계산을 요구하기 때문에 적..

구현 방법조건(1 ≤ N ≤ 1,000, 1 ≤ A[i] ≤ 1,000)N : 수열의 길이A[i] : i번째 수열A의 값구현조건 1에 의해서 시간복잡도 O(N^2)으로 충분히 풀 수 있다고 생각했다.→ 따라서 DP 사용!바이토닉 부분 수열이 될 수 있는 경우는 3가지가 있다.계속 증가계속 감소증가하다가 감소바이토닉 부분 수열이 될 수 있는 경우가 3가지를 바탕으로 필요한 정보는 다음과 같다.dpDESC[i] : i번째부터 (N - 1)번째까지 감소하는 수열 중 가장 긴 수열dpASC[i] : 0번째부터 i번째까지 증가하는 수열 중 가장 긴 수열위의 두 정보를 더하고, 중복된 i번째 하나를 빼면 원하는 답이 나온다.dp[i] = dpASC[i] + dpDESC[i] - 1;코드import java.util..

구현 방법느린 버전조건≤ M ≤ N ≤ 8입력으로 주어지는 수는 10,000보다 작거나 같은 자연수중복되는 수열을 여러 번 출력하면 안됨수열은 사전 순으로 증가하는 순서로 출력구현1번 조건에 의해 순열을 사용해도 N!으로 시간초과 안남.2번 조건에 의해 자료형은 int3번 조건을 만족하기 위해 Set checked을 통해 중복 제거4번 조건을 만족하기 위해 입력값 숫자들을 오름차순으로 정렬한 뒤, 순열을 한다.속도 개선위 방식은 속도가 느렸습니다.속도가 느린 가장 큰 이유는 “Set checked을 통해 중복 제거” 로직입니다.제거해야 하는 중복은 “뽑힌 순열 기준 같은 자리에 다른 인덱스의 같은 숫자”인 경우 입니다.예시로 1, 2, 2, 3이 있다고 했을 때,1 2(1번 인덱스)와 1 2(2번 인덱스..