백엔드 개발자로 가는길

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://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 풀이 방법주의할 점"두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. "=> 임의의 두 정점 사이의 가중치가 여..

https://www.acmicpc.net/problem/2758골드4구현 방법N = 뽑아야 하는 개수M = 최대 수 1. 완전 탐색 - 시간 초과처음에 현재 뽑은 수의 두배 이상의 수를 선택해야 하기 때문에 재귀를 이용하면 시간 복잡도가 O(n * log m)이라고 착각했다. 하지만 실제 시간 복잡도는 O(m * 2^n)를 가진다. 이분 탐색처럼 반틈만 탐색하는게 아니기 때문이다. 2. 삼중 포문을 사용한 DP1번의 문제점은 같은 계산이 반복적으로 이루어진다는 문제점이 있다.예를 들어서 1에서 재귀가 나누어지면 다음에는 두배인 2부터 2000까지의 재귀가 발생한다.다음 재귀인 2에서 재귀가 나누어지면 다음에는 두배인 4부터 2000까지의 재귀가 발생한다.이 두 경우를 보더라도 4 ~ 2000이 겹치게 ..

https://www.acmicpc.net/problem/1106골드4구현 방법전형적인 DP 유형이라고 생각이 들었습니다. knapsack 유형과 비슷하기도 했기 때문입니다.풀이 방법은 dp 배열을 만들고 채울 수 있는 인원의 비용과 현재 비용을 비교하면서 최소값을 업데이트 하는 방식으로 구현했습니다.점화식dp[현재 인원 + 채울 수 있는 인원] = Math.min(dp[현재 인원 + 채울 수 있는 인원] , dp[현재 인원] + 채울 수 있는 인원 cost) 이때 주의할 점은 목표 인원을 넘더라도 비용이 더 작은 경우를 고려해야 한다는 점 입니다.코드import java.io.*;import java.util.*;/*** 백준 1106* 호텔* 골드4* https://www.acmicpc.net/pro..

https://www.acmicpc.net/problem/16120골드4구현 방법백준 9935 문자열 폭발 문제와 동일하다.문자열 하나하나를 스택에 넣고 4개 이상이 들어오면 PPAP가 맞는지 확인하고 맞으면 P로 바꾸면 된다.코드import java.io.*;/*** 백준 16120* PPAP* 골드4* https://www.acmicpc.net/problem/16120*/public class Boj16120 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = b..