백엔드 개발자로 가는길

구현 방법조건(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..

https://www.acmicpc.net/problem/2504골드5구현 방법조건에 만족하지 않는 경우는 크게 3가지가 존재한다.1. 괄호 모양이 다른 경우2. 여는 괄호가 더 많은 경우. (, [3. 닫는 괄호가 더 많은 경우. ), ] 스택을 활용하여 문제를 해결했고, 아래 규칙을 반복적으로 수행했다.1. 여는 괄호는 스택에 넣는다.2. 닫는 괄호가 나오면 같은 모양의 여는 괄호가 나올 때까지 스택에서 꺼낸다. 이 때 나오는 숫자를 다 더해준다.3-1. 더해진 숫자가 0인 경우, 가장 안쪽 괄호 쌍이므로 2나 3을 스택에 넣는다.3-2. 더해진 숫자가 0이 아닌 경우, 해당 숫자에 2나 3을 곱한 뒤 스택에 넣는다.3-3. 같은 모양이 아닌 경우, 0을 출력한다.4. 1~3 반복 후, 스택에서 숫자..

https://www.acmicpc.net/problem/1101골드4풀이 방법박스의 상태는 크게 세가지로 분류 할 수 있다어떠한 색도 없는 경우색이 한가지인 경우색이 두가지 이상인 경우1번의 경우 이동이 발생하지 않는다2번의 경우 앞서 같은 색이 한가지 있었던 경우 이동이 발생한다 하지만 처음 나오는 종류의 색인 경우 이동할 필요가 없다.3번의 경우, 모두 이동을 해야한다. 이 문제에서는 모든 색을 포함할 수 있는 조커 박스가 있기 때문에 그곳으로 이동하면 될 일이다.이제 조커 박스를 선택하는 기준에 대해 생각해야 한다. 이건 문제에 힌트가 있었다. 같은 색을 가진 모든 카드가 조커 박스에 들어있는 것도 가능 , 조커 박스는 색이 다른 카드를 보관해도 된다.두 문장을 통해 조커 박스는 같은 색을 가진 ..

https://school.programmers.co.kr/learn/courses/30/lessons/273712lv3구현 방법item_tree에서 parent_item_id에 등장하지 않은 item_info의 item_id를 출력하면 된다. 방법은 3가지 정도 있다. 1. not in 사용in을 사용할 때 null이 나오는 경우를 고려해야 한다. in에서 null이 나올 때 항상 false로 처리하여 데이터가 나오지 않기 때문이다.2. not exists 사용3. left join 사용코드-- 업그레이드 할 수 없는 아이템 구하기-- https://school.programmers.co.kr/learn/courses/30/lessons/273712-- not in 사용select i.item_i..

https://www.acmicpc.net/problem/2098골드1구현 방법도시수 범위: 2이상 16이하단방향 → 두 도시간 이동 비용은 대칭 아님모든 도시간 비용은 양의 정수모든 도시를 방문하고 처음 도시로 돌아오는 최소 비용방문 했던 도시는 재방문 불가능5가지의 조건을 통해 전형적인 TSP 문제임을 알 수 있습니다.해당 문제를 완전 탐색으로 풀 경우 O(N!)의 시간복잡도를 가집니다.따라서 비트마스크와 DP를 활용하여 시간 복잡도를 줄여야 합니다.이 방식을 통해 O(N * N * 2^N)으로 줄일 수 있습니다.비트마스크방문 상태 표현DP 테이블 정의dp[도시 수][비트마스크] = 이동 비용DP 점화식W[i][j]: 도시 i에서 도시 j로 이동하는 비용dp[j][visited∣(1 다익스트라 알고리..

https://www.codetree.ai/training-field/search/problems/the-tip-of-the-iceberg?&utm_source=clipboard&utm_medium=text실버1구현 방법실버1이라고 만만하게 봤다가 된통 당한 문제!input 데이터 범위를 보면 아래와 같기 때문에 O(n)으로 해결해야 한다.빙산들의 개수 N, 빙산의 높이 H(i)1 ≤ N ≤ 100,0001 ≤ H(i) ≤ 1,000,000,000처음에는 높이를 기준으로 매개변수 탐색을 진행 해서 O(nlogn)으로 풀려고 호기롭게 도전했으나,무수히 많은 예외 케이스들이 존재했다. 다시 생각해보면 높이 자체와 빙산의 개수는 아무런 연관관계가 없기 때문에 아주 잘못된 접근임을 깨닮았다.그럼 빙산의 개수는 ..

https://www.acmicpc.net/problem/1865골드3구현 방법"한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우" -> 음의 사이클이 있는지 판단해 달라는 문제였다. 벨만-포드 알고리즘을 사용하면 되지만, 문제 조건을 보면 정점의 범위가 1~500 사이이고, 테스트케이스 범위가 1 ~5이다. 따라서 O(n^3)의 시간 복잡도를 가진 플로이드-워셜 알고리즘으로도 충분히 풀 수 있다고 판단했다.(500 * 500 * 500 * 5 = 625,000,000) Floyd-Warshall 풀이 방법주의할 점"두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. "=> 임의의 두 정점 사이의 가중치가 여..