11725번: 트리의 부모 찾기dfs를 이용한 문제이다. dfs를 통해 입력받은 연결된 노드들을 순차적으로 순회하며 parent 배열에 현재 노드를 저장해주었다. 간단하게 풀 수 있었던 문제였다.

1167번: 트리의 지름dfs를 이용한 문제이다. 먼저 트리의 지름을 구하는 법에 대해 알아야 한다. 트리의 지름은 임의의 두 점의 거리 중 가장 긴 것을 말한다. 이를 공식화 해볼 수 있는데 아래와 같다.정점 x에서 가장 거리가 먼 정점 y를 구한다.정점 y에서 가장

1202번: 보석 도둑그리디와 우선 순위 큐를 이용하는 문제이다. 각 배낭마다 최대 무게가 있고 최대 한개의 보석만을 담을 수 있다. 우선 입력받은 보석 정보들과 가방 무게들을 오름차순으로 정렬해주었다. 그 후 반복문을 돌며 해당 배낭의 무게에 담을 수 있는 보석들의

1713번: 후보 추천하기주어진 조건을 직접 구현하는 문제이다. 맵을 사용하였으며 키에는 추천받은 학생 번호를, 값에는 추천수와 값이 위치한 인덱스를 저장해주었다. 현재 값이 맵에 이미 있을 경우 그 값의 추천수를 +1해주고, 없다면 새로 추가해주었다. 추가해줄 때 만

12015번: 가장 긴 증가하는 부분 수열 2이분 탐색을 이용한 문제이다. lis 알고리즘을 이용하여 문제를 해결했다. 입력받은 값들을 벡터 result에 차례대로 넣어주는데 이때 현재 백터에 들어갈 값이 result.back()보다 작다면 lower_bound를 통해

1655번: 가운데를 말해요우선 순위 큐를 이용하여 풀 수 있는 문제이다. 문제를 보면 주어지는 입력마다 정렬을 하여 가운데에 해당하는 수를 출력해주어야 한다. 그리고 제한 시간도 0.5초밖에 되지 않기에 힙 정렬을 사용하는 우선 순위 큐를 사용해주어야 한다. 큐는 오

15661번: 링크와 스타트백트래킹을 이용한 문제이다. 기존 백트래킹과 비슷하게 진행이 된다. 다른 점이라면 result를 구하는 조건이다. 만약 N=4일 때 check에 저장될 수 있는 기록 중 1 0 0 0과 0 1 1 1은 같은 결과를 리턴하게 된다. 그렇기에 N

16637번: 괄호 추가하기직접 구현을 하는 문제이다. 재귀를 이용해 구현하였다. 괄호를 사용했나 하지 않았나 두가지로 분기하여 재귀를 사용해주었다. pre의 경우 현재 인덱스 포함 이전 까지의 연산 결과를 저장한다. 재귀를 통해 최댓값을 구해 출력해주었다. 굉장히 어

1915번: 가장 큰 정사각형dp를 이용한 문제이다. 1로 이루어진 가장 큰 정사각형을 구해야 하는데 이를 dp 배열을 이용해 구해주었다. 먼저 가장 위쪽과 왼쪽에 1일 경우 dp에 1을 저장해주었다. 그리고 i=1, j=1에서 반복문을 시작하여 정사각형의 길이를 구해

1052번: 물병그리디를 이용한 문제이다. 같은 양의 물이 들어있는 물병끼리는 하나로 합칠 수 있다. 그렇기에 N을 2로 나누어가다보면 최종적으로 남는 물이 들어있는 물병의 개수를 알 수 있다. 만약 개수가 K 이하라면 물병을 추가로 구매할 필요가 없다. 코드는 반복문

4485번: 녹색 옷 입은 애가 젤다지?그래프 탐색을 이용한 문제이다. 이 문제는 bfs와 다익스트라 두 방식으로 해결할 수 있다. 사실상 우선순위 큐를 사용했냐 안했냐 차이이다. 우선순위 큐를 이용한 다익스트라 쪽이 시간이 거의 1/2 일 정도로 더 빠르다. 지나온

2138번: 전구와 스위치그리디를 이용한 문제이다. 이 문제의 키포인트는 i==0일 때 상태를 바꾸냐 안 바꾸냐이다. 현재 위치를 i라고 한다면 i의 상태를 바꾸면 i-1과 i+1의 상태가 바뀌게 된다. 그렇기에 i-1의 상태를 바꿀려면 i를 바꾸어주면 된다. 반복문이

12851번: 숨바꼭질 2bfs를 이용한 문제이다. 기존 bfs와 비슷하게 흘러가지만 주의할 점이 있다. N = 1일 때 1 + 1과 1 \* 2가 구분이 안되게 된다. 구분을 하기 위해 푸시를 할 때 check\[next] = true를 해주는 것이 아닌 큐에서 꺼냈

1939번: 중량제한이분 탐색과 bfs를 이용한 문제이다. 입력 단위가 크기 때문에 bfs만을 사용하면 시간 초과가 발생한다. 그렇기에 이분 탐색을 이용해주었다. 0을 left, 10억을 right로 지정하고 가운데 값을 mid로 주어 반복문을 돌며 bfs를 돌려주었다

16139번: 인간-컴퓨터 상호작용누적 합을 이용한 문제이다. 먼저 문자열을 입력받고 모든 알파벳을 대조하며 카운트를 해주었다. 이때 카운트는 0 ~ r 까지의 카운트를 저장하게 된다. 그 후 질문을 입력받으면서 입력에 해당하는 값을 출력해주었다. 이 때 시작 지점 l

2436번: 공약수정수론을 이용한 문제이다. 먼저 공식에 대해 알고 있어야 한다. 두 수 A, B가 있을 때, A = a \* GCD(A,B), B = b \* GCD(A,B)을 만족하는 a, b가 있다고 하자. 이럴 경우 LCM(A,B) = a \* b \* GCD(

16987번: 계란으로 계란치기백트래킹을 이용한 문제이다. 사실상 문제에서 조건들을 다 알려주었기에 조건대로 로직을 짜주면 된다. 가장 왼쪽 계란부터 시작하여 dfs를 시작한다. 반복문을 돌며 하나씩 비교해 내구도를 바꾸어주면서 깊이 탐색을 이용한다. 이때 더이상 깨지

1351번: 무한 수열dp를 이용한 문제이다. N의 범위를 보면 int의 범위를 넘기때문에 자료형을 long long으로 해주었다. 기존 dp에서는 최대 범위만큼 배열을 만들어 저장해주었지만 범위가 크기때문에 map을 이용하여 저장해주었다. 재귀를 통해 m\[N]을 구

7662번: 이중 우선순위 큐우선순위 큐를 이용한 문제이다. 우선순위 큐를 양방향으로 구현해주기 위해 오름차순과 내림차순 두가지 우선순위 큐를 사용해주었다.반복문을 돌며 커맨드에 따라 동작을 하게 되는데 중요한 점은 cnt를 통해 n의 개수를 카운트해주는 점이다. 이

2143번: 두 배열의 합누적 합, 이분 탐색을 이용한 문제이다. 먼저 A와 B의 모든 누적 합들을 구해준다. 그리고 B의 누적합을 오름차순으로 정렬을 한 후 A의 누적 합 크기만큼 반복문을 돌면서 T와의 차이와 같은 값을 B 누적 합에서 찾아 시작과 끝 인덱스를 구해