백엔드 개발자로 가는길

백준 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)개의 간선을 가지고 있습니다. 현재 문제에서는 하나의 트리에서 간선 하나를 더 끊어서 두 그룹으로 만들면 됩니다.따라서..

프로그래머스 59411 / 오랜 기간 보호한 동물(2)LV3구현 방법처음에 timediff로 코드를 작성했습니다.그런데! 틀렸다네요? 혹시나 해서 datediff로 했더니 맞더라구요.근데 이상하잖아요. 아니 datediff보다 오히려 더 정확하게 timediff로 했는데 틀렸다니요.아니 그럼 일수가 같으면 어쩔려고...(물론 현재 문제에선 문제가 되는 부분은 아니였습니다.)왜 안되는지 궁금해서 못참겠더라고요. 그래서 원인을 찾아봤습니다.이유는 다음과 같았는데요.timediff의 경우, 최대 범위가 838:59:59까지더라고요.... 그래서 그 이상 차이는 모두 같은 취급을 해버리니까 틀렸더라고요... 유유아래 이미지는 제가 직접 쿼리문을 통해 확인해본 결과 입니다.또한 stackoverflow에도 관련 ..

백준 15681 / 트리와 쿼리골드5구현 방법구현 방법은 루트 노드에서 시작해서 dfs를 이용해 자식노드들을 모두 방문하면서 노드 수를 지속적으로 더하면서 구현했습니다.이렇게 하면 모든 노드 방문이 끝남과 동시에 각 노드를 루트로 하는 서브 트리의 정점 수를 알 수 있게 됩니다.따라서 현재 문제의 노드 수(N), 쿼리 수(Q)의 범위가(2 ≤ N ≤ 10^5, 1 ≤ Q ≤ 10^5) 커도 O(N + Q)의 시간복잡도로 해결 가능합니다.구현 방법은 쉬운편인데 이 아이디어를 생각하는게 꽤 어려웠습니다. 아마 트리 특징에 익숙하지 않아서 그런것 같습니다.트리 특징사이클이 존재 하지 않습니다.(임의의 두 정점 U와 V에 대해, U에서 V로 가는 최단경로는 유일)간선수 = 노드수 - 1아무 정점이나 잡고 부모와..