백엔드 개발자로 가는길

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를 같다고 생각하는 경우첫번째 방법의 경우는 문제의 조건을 만족합니다.하지만 두번째 방법의 경우 결국 문..

백준 9372 / 상근이의 여행실버4구현 방법"가장 적은 종류의 비행기", "갔던 나라 재방문 가능", "모든 나라 방문해야함" 보고 바로 스패닝 트리라는것을 눈치 챘습니다.이 문제에서는 나라를 노드, 비행기를 간선이라고 생각하면 됩니다."그럼 모든 노드를 방문하면서 사이클이 존재하지 않는 그래프를 만들 때 필요한 간선의 수를 구하여라" 문제로 바뀌게 됩니다."가장 적은 종류의 비행기 == 사이클이 존재하지 않는 그래프"인 이유는 가장 적은 종류의 비행기라는 뜻은 간선을 최소화 하라는 뜻이 되기 때문입니다.참고로 비행 스케줄은 연결 그래프라고 했기 때문에 모든 나라는 이어져 있다고 생각하면 됩니다.현재 문제는 간선에 비용이 있지 않기 때문에 최소 스패닝 트리 알고리즘까지 적용할 필요가 없습니다.따라서 트..

https://www.acmicpc.net/problem/1647골드4구현 방법최적화 전"임의의 두 집 사이에 경로가 항상 존재", "비용 양수" 두가지를 통해 최소 스패닝 트리 문제임을 눈치 챘습니다.여기서 추가 조건으로 두개의 그룹을 만들라고 했습니다. 이는 하나의 최소 스패닝 트리를 만들고, 그 트리의 비용들 중 가장 큰 비용를 끊어주면 두 그룹이 나오고, 각각 최소 비용이 된다고 생각했습니다.최소 스패닝 트리는 크루스칼 알고리즘을 통해 구현했습니다. 하지만 꽤 느렸습니다. 따라서 두가지 방법을 통해 최적화 진행 했습니다. 방법1. 트리의 특징을 통한 최적화트리는 (노드 수 - 1)개의 간선을 가지고 있습니다. 현재 문제에서는 하나의 트리에서 간선 하나를 더 끊어서 두 그룹으로 만들면 됩니다.따라서..