백엔드 개발자로 가는길

https://www.acmicpc.net/problem/2015골드4 구현 방법틀린 접근법1. 모든 누적합을 구해, 원하는 값이 나오면 카운트 => 시간 초과시간 복잡도가 O(n^2)이 되기 때문입니다. 올바른 접근법sum(i) - sum(j - 1) = sum[j ... i]특징을 이용해야 합니다.현재 저희는 목표값 K를 구해야 하기 때문에 sum[i] - sum[j - 1] = K인 값을 구하는게 목표입니다.이 식은 sum[i] - K = sum[j - 1]로 바꿀 수 있습니다.이를 통해 현재까지의 부분합에서 목표값 K를 뺏을 때의 값이 존재하는지 확인하면서 갱신해주는 방법으로 구현하면 O(n)으로 답을 낼 수 있습니다.코드import java.util.*;import java.io.*;/*** 백..

https://www.acmicpc.net/problem/14938골드4구현 방법1. bfs 구현 방법1. 갈수 있는 범위 내에서 bfs 돌면서 지나간 지역을 체크 한다.2. 지나간 지역의 아이템을 다 더한다.3. 최댓값 갱신한다.주의할 점은 bfs 돌 때 방문 체크를 하면 안된다. 이유는 이미 방문한 노드에서 다른 노드로 갈 수 있는 경우가 생기기 때문이다.하지만 이 방법은 노드까지의 최단 경로를 고려하지 않아서 중복된 노드 탐색이 발생하게 된다. 2. 다익스트라 구현 방법항상 최단 경로로 노드를 탐색한다면 노드 탐색의 중복이 발생하지 않게 된다. 코드1. bfsimport java.util.*;import java.io.*;/** * 백준 14938 * 서강그라운드 * 골드 4 * https://ww..

https://www.acmicpc.net/problem/1562골드1 구현 방법길이가 N인 계단수를 구하는 방법은 길이가 (N-1)인 계단수에서 하나의 숫자를 추가해 주면 된다.이때 (N-1)인 계단수의 마지막 수에서  + 1이거나 - 1인 수를 하나 추가하면 만들어진다.그럼 이제 계단수를 구하기 위해 필요한 정보를 알수 있다.계단수 길이, 현재 계단수의 마지막 자리수가 필요하게 된다.하지만 문제 조건에서 0~9 모든 수가 나와야 한다고 했으므로, 현재 만들어진 계단수도 필요하게 된다.또한 완전 탐색할 경우 9^N개의 경우의 수가 나오므로 시간초과 가능성이 매우 높다.따라서 전의 계단수로 현재 계단수를 구하기 때문에 "다이나믹 프로그래밍"을 이용하기로 했다.이때 현재 만들어진 계단수는 비트마스크를 이용..

https://www.acmicpc.net/problem/1509골드1구현 방법문자열에 대해 모든 팰린드롬을 구하는 방법은 dp[시작문자 위치][끝 문자 위치]를 사용해서 구했다. https://kdozlo.tistory.com/53이제 dp[시작 문자 위치][끝 문자 위치]를 이용하여 팰린드롬 수로 분할의 개수의 최솟값을 구해야 한다. 처음에 dfs로 하면 되겠다 싶어서 구현했는데 두가지 문제점이 있었다.첫번째로는 끝에서부터 팰린드롬 수인 경우 그 다음을 카운터 하는 방식으로 구현했는데, 이렇게 했을 때 항상 최적의 최소값이 나오지 않는다. 따라서 그리디하게 풀면 안되고 모든 경우를 따져야 한다.두번째 문제는 시간복잡도가 너무 높다. 문자열의 최대 길이가 2500인데 심지어 모든 경우를 따지면 2^25..

백준 2473 / 세 용액골드3구현 방법N개의 용액중에 3개를 선택하여 0에 가장 가까운 세 용액을 출력해야 한다.N의 범위는 최대 5000이기 때문에 완전 탐색하면 시간 초과가 난다.자연스럽게 시간복잡도를 줄일 방법을 찾을 텐데 떠오르는 알고리즘이 이분탐색과 투포인터 두개 였다. 이분탐색이분탐색으로 구현할 경우, 처음과 끝을 기준으로 가운데 탐색을 지속적으로 한다.이러면 두 용액을 고정시켜 놓고 나머지 한 용액을 이분탐색으로 정하는 방식으로 구현 해야한다.이러면 시간복잡도가 O(n^2 * longn)이 된다. 투포인터투포인터로 구현할 경우, 두 포인트가 움직이면서 범위를 조정한다. 자 그러면 한 용액만 고정시켜놓고 구현이 가능해진다이러면 시간복잡도가 O(n * n)으로 이분탐색보다 빠르다.코드impor..

백준 10942 / 팰린드롬?골드 4구현 방법투포인터 이용해서 풀었다. 하지만 질문마다 팰린드롬을 구하면 겹치는 구간에 대한 질문마다 다시 투포인터를 돌려야해서 느릴거라고 예상했다.그리고 역시 예상이 맞았다.자 그럼 어떻게 풀면 중복 구간이 해결될까?당연히 구했던 구간을 기억하고 있으면 된다!그럼 뭘 해야한다? 바로 다이나믹프로그래밍!!먼저 시작 인덱스, 끝 인덱스를 각각 행,열로 가지는 이차원 배열을 생성한다.먼저 길이가 1인 경우, 무조건 팰린드롬이다.길이가 2인 경우, 두 인덱스의 숫자가 같으면 팰린드롬이다.길이가 3 이상인 경우, 시작과 끝 인덱스가 같고, (시작 + 1)과 (끝 - 1) 범위가 팰린드롬인 경우 팰린드롬이다.코드DP 방식import java.io.*;import java.util...

백준 2212 센서골드5구현 방법범위을 봤을 때 완전 탐색은 시간초과 날게 뻔했다.그래서 바로 매개변수 탐색을 생각했다. 하지만 최소 거리마다 구간을 나누어서 확인해줘야하는데이런 방식으로 해도 시간초과 문제를 해결할 수 없다고 판단했다. 결국엔 완전탐색과 같은 방법이 된다.그럼 dp인가? 생각했다. 임의의 두 센서의 구간 차이를 저장하고 이를 바탕으로 최소 거리를 구하면 되지 않을까? 생각했다.하지만 반복되는 규칙이 보이지 않아 아니라고 판단했다.결국 위 세 방식 모두 최후에는 구간을 나누는 경우의 수를 모두 생각해본다는 완전탐색이 되어버렸다!!그럼 이문제는 그리디겠다 라는 생각이 들었다.그러나 로직이 떠오르지 않아 힌트를 보고 풀었다. 너무 아쉽...구현방식먼저 센서 좌표를 배열로 저장하고 오름차순 정..

백준 16974 레벨 햄버거골드5구현 방법반복되는 패턴, 큰 입력데이터 범위를 보니 이거 DP 문제다 생각했다.여기서 나오는 규칙현재 레벨 햄버거 길이 = 전 레벨 햄버거 길이 * 2 + 3현재 햄버거 패티 수 = 전 햄버거 패티 수 * 2 + 1규칙을 바탕으로 필요한 레벨까지의 햄버거 길이와 패티수를 구할 수 있다. 이걸 바탕으로 이제 X길이까지 먹었을 때 먹은 패티 수를 구하면 된다,현재 햄버거는 정중앙을 기준으로 (햄버거 번 + 전 레벨 햄버거)가 있고, 정중앙은 햄버거 패티이다.따라서 현재 햄버거 길이의 정중앙을 기준으로, 재귀를 이용한 분할 정복 방법을 사용하여 패티 개수를 세면 된다.재귀 종료 조건첫번째 종료 조건. level이 0이면 패티뿐이므로 1를 return 한다.두번째 종료 조건. 현..

백준 1644/ 소수의 연속합골드3구현 방법이문제는 사실 제목에 풀 방향이 나와있어서 어렵지 않았다.소수 == 소수를 구하는 알고리즘을 사용해라연속합 == 투포인터 사용해서 부분합 구하기처음 방식소수 구하기 위해 "현재 판별하고자 하는 수의 제곱근보다 작은 자연수로 모두 나누기"을 이용했다.따라서 입력값 N 범위 내의 모든 소수를 위의 방법을로 구한 뒤, 투 포인터를 이용해서 가능한 구간합의 경우의 수를 구했다.구간합의 경우의 수 구하는 방법은 아래와 같다.시작, 끝 인덱스를 0으로 잡고, 현재까지의 구간 합을 첫번째 소수값으로 한다.만약 현재까지의 구간 합과 구하고자 하는 수가 같다면 횟수를 하나 증가시키고, 현재까지의 구간합에 시작 인덱스의 소수를 뺀다. 그후 시작 인덱스를 하나 증가시킨다. -> 다..

백준 17609 / 회문골드5구현 방법양끝 문자가 같은 단어를 구하는 문제입니다.투포인터를 이용하여 단어 비교하는 것이 핵심입니다.문제에서는 한 문자를 제외 했을 때도 가능하다는 조건이 있어서 투 포인터로 돌리고 만약 두 문자가 다르다면 오른쪽 끝이나 왼쪽 끝을 기준으로 현재문자의 다음 문자로 이동하여 비교하는 식으로 구현했습니다.하지만 이 경우 예외가 존재했습니다.예를들어 abcbbca인 경우, 두번째 차례에서 b와 c가 다릅니다. 이경우 두가지 방법이 있습니다.첫번째 방법. 왼쪽 끝인 b 다음 문자 c와 오른쪽 끝 c를 같다고 생각하는 경우두번째 방법. 오른쪽 끝인 c 다음 문자인 b와 왼쪽 끝 b를 같다고 생각하는 경우첫번째 방법의 경우는 문제의 조건을 만족합니다.하지만 두번째 방법의 경우 결국 문..