백엔드 개발자로 가는길

자바 - 백준 2169 / 로봇 조종하기

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번 인덱스..

https://www.acmicpc.net/problem/9252골드4구현 방법전형적인 DP 문제이다.최대 1000글자 이므로 O(N^2)의 시간복잡도가 가능하다. 최대 문자열 길이 구하는 방법문자가 같은 경우의 점화식같은 문자인 경우, 각각 단어 인덱스를 1씩 증가하여 다음 문자부터 비교 진행dp[i][j] = dp[i - 1][j - 1] + 1;문자가 다른 경우의 점화식다른 문자인 경우, 두 단어 중 한 인덱스만 증가함dp[i][j] = Math.*max*(dp[i - 1][j], dp[i][j - 1]); 최대 문자열일때의 단어 구하는 방법dp의 가장 오른쪽 아래부터 진행한다.(역추적 진행)가장 오른쪽 아래의 숫자가 최대 문자열의 길이이기 때문이다.가장 왼쪽 위부터 진행할 경우, 최대값에 도달하지..

https://www.acmicpc.net/problem/2589골드5구현 방법땅인 경우 bfs를 이용해서 최단 거리 기준 가장 먼 곳을 구한다.이걸 모든 땅마다 반복하면서 가장 먼 곳을 구한다.bfs를 이용한 이유거리가 최단거리여야 하기 때문이다.dfs의 경우 최단 거리로 가지 않고 돌아갈 가능성이 존재한다.그럼 bfs를 사용해서 답을 구할 순 없을까?되긴 된다. 하지만 시간 초과가 발생한다. 즉, 너무 오래 걸려 비효율적이다.왜냐하면 bfs는 기본적으로 모든 경로를 다 탐색하게 된다. 따라서 경로마다 거리가 나오는데 그 중 최솟값을 구한 뒤, bfs 탐색을 마치면, 그 중에서 최대 거리를 또 구해야 한다.bfs의 경우에는 “경로마다 거리가 나오는데 그 중 최솟값을 구함”을 안해도 된다.코드import..