개인사

리뷰 포인터 두개를 늘려가며 수열에서의 부분합이 특정 수 이상이 되는 가장 짧은 길이를 찾는 문제https://www.acmicpc.net/problem/1806 문제 풀이수열의 길이 n, 찾을 값 d, 정답 식별용 ans, 수열의 정보 배열lst를 전역 변수로 설정해 준다.n과 d값을 입력받고, n길이의 수열 정보를 lst 배열에 입력받아 준다.전위 포인터s와 후위 포인터e를 모두 0으로 초기화 해주고 sum을 lst의 0번째 인덱스의 수로 초기화 해준다.s가 e보다 앞서거나 e가 n의 범위를 벗어나기 전까지 while 루프를 진행한다.현재 sum값이 d보다 작다면 e를 증가시키고 sum에 lst의 e번째 인덱스의 수를 추가해 준다.만약 반대라면 ans를 e - s + 1과 비교하여 길이의 최소값을 갱..

리뷰 두 노드에서 출발해 LCA에 달할때 까지 도로 중 가장 짧은 거리와 가장 긴 거리를 구하는 문제https://www.acmicpc.net/problem/3176 문제 풀이도시의 최대 개수는 10만이므로 MAX_N을 10만 1로, LOG를 MAX_N을 LOG2를 취한 값 보다 크게 20으로 설정한다.도시의 개수 n과 쿼리의 개수 k를 전역 변수로 설정한다.부모 도시를 담을 배열par, 짧은 거리 및 긴 거리를 저장할 배열 mn, mx을 MAX_N * LOG 크기로 설정한다.깊이를 담을 배열dep, 유니온 파인드용 배열 nodes를 MAX_N크기로 설저어한다.인접 리스트 정보를 담을 구조체 Link를 만들어 주고 Link타입 벡터 links를 MAX_N크기로 설정한다.n값을 입력 받고 1~n 도시를 각..

리뷰 위상 정렬에 우선 순위 큐를 사용하여 최대한 난이도가 낮은 순서로 출력하는 문제https://www.acmicpc.net/problem/1766 문제 풀이문제의 수 n과 선수 문제의 개수 m, 인접 리스트 벡터path를 전역변수로 설정해 준다.n과 m값을 입력 받고, m개의 선수 문제 정보를 인접 리스트 path에 추가해 준다.선수 문제 개수를 저장할 cnt 벡터를 n + 1크기로, 내부 값을 모두 0으로 초기화 해준다.n개의 문제의 인접 리스트를 순회하며 인접 리스트에 담긴 문제의 개수를 증가시켜 준다.오름차순 정렬 형태의 우선순위 큐 pq를 초기화 해준다.다시 n개의 문제를 순회하며 cnt의 개수가 0개라면 pq에 추가해 준다.pq에 요소가 없을 때까지 순회하며 pq의 top요소를 뽑아 cn으로..

리뷰 LIS는 꼭 풀어봤으면 좋겠다. 난이도에 비해 코드길이가 정말 짧다! 꿀통 알고리즘https://www.acmicpc.net/problem/2352 문제 풀이포트의 개수 n개를 입력 받고 LIS를 저장할 정수형 벡터 ans를 초기화 해준다.n개의 입력을 받고, 입력 받은 포트 번호가 기존의 포트보다 크다면 ans에 push 해준다.만약 기존의 포트보다 작거나 같으면 해당 포트의 위치를 찾아 교체해 주면 된다.반복이 종료된 후 ans의 size를 출력해 주면 된다. 참고 사항lower_bound를 사용하려면 algorithm을 include 해주어야 한다.  정답 코드#include#include#includeusing namespace std;int main() { ios::sync_with_std..

리뷰 게임 상에서 각 건물이 지어질 수 있는 최소 시간을 구하는 문제 위상 정렬을 통해 쉽게 해결할 수 있다.https://www.acmicpc.net/problem/1516 문제 풀이건물의 개수 n과 각 건물의 건설 시간 t배열, 인접 리스트용 벡터 path를 전역 변수로 초기화 해준다.input 함수를 통해 n값을 입력 받고 1~n번째 건물의 건설 시간과 인접 리스트를 입력 받아준다.solution함수를 통해 각 건물의 건설 완료 시간을 구해줄 수 있다.각 건물의 건설 완료 시간 벡터 sum과 건물을 짓기위한 우선순위의 개수 벡터 cnt를 n + 1, 0값으로 초기화 한다.각 건물의 인접리스트를 순회하며 인접 리스트에 저장된 건물의 cnt를 1개씩 늘려준다.정수형 큐 q를 주비하고 cnt가 0인 건물..

리뷰 처참한 전투흔적.. 위상 정렬의 응용 문제였는데 꽤나 애를 먹었다.최소 거리를 구하는 부분은 쉽게 나왔으나 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는게 어려웠다.처음엔 거리 배열을 사용하여 max로 갱신될 경우 이전 경로로 교체를 해주고, 값이 같을땐 현재 저장된 거리에 새로 들어온 경로를 더해주는 방식으로 생각했었다.하지만 이전까지 같은 경로로 오다 갈라진 후 다시 합쳐지는 케이스에서는 해당 방법을 사용할 수 없었다.이후 set를 사용해 왔던 경로를 모두 저장해 준 뒤 set의 크기를 출력해 주었으나 메모리 초과가 났다.결국 왔던 길을 역추적 해서 검증이 가능한 길의 개수만 구해지는 방식으로 풀이하였다.해당 방식이 맞는 접근 방법이나, 중복이 가능한 케이스들을 놓쳐서 방문 처리를 하고 나니..

리뷰 위상 정렬을 통해 가중치가 있는 간선을 갖고 특정 노드의 최소값을 구하는 문제https://www.acmicpc.net/problem/1005 문제 풀이테스트 케이스의 개수 tc, 노드의 개수 n, 간선의 개수 m, 목표 노드 dest를 전역변수로 초기화 해준다.인접 리스트를 담을 정수형 벡터 path, 각 노드의 소요시간 정보 times의 크기를 n의 최대값으로 설정해 준다.init 함수를 통해 times 배열 초기화, path 백터를 초기화 해준다.input 함수를 통해 n, m값과 각 노드의 소요시간, 간선정보, 목표 노드를 입력 받는다.solution 함수를 통해 dest 노드가 건설이 완료 되기까지의 최소 시간을 출력해 준다.cnt, sum 벡터를 n + 1 크기로, 초기값은 0으로 초기화..

리뷰 위상 정렬의 가장 기본이 되는 문제https://www.acmicpc.net/problem/2252 문제 풀이n, m과 정수형 벡터 path를 n의 최대 크기인 32001로 전역 변수로 초기화 해준다.input 함수를 통해 n, m값을 받고 m개의 키 정보를 받아 path 벡터에 연결 리스트를 추가해 준다.solution 함수를 통해 위상 정렬을 수행해 준다, 정수형 벡터 cnt를 n + 1크기, 0으로 초기화 result를 초기화 해준다.1 ~ n을 탐색하여 i번째 path를 탐색하여 인접리스트에 저장된 노드의 cnt를 늘려준다.정수형 큐 q를 초기화 하고 1 ~ n을 탐색하여 만약 cnt가 0인 키 정보가 있다면 큐에 추가해 준다.큐가 빌때까지 while 루프를 돌며 현재 키를 result에 추..

리뷰 5달만에 다시 찾아와 깨부신 문제 파이썬에 비해 입력을 처리하는데 시간이 더 쓰인거 같다.https://www.acmicpc.net/problem/14911 문제 풀이정수형 벡터 lst를 초기화 해주고 getline을 통해 첫 줄을 문자열로 받아와 준 뒤 두번째 줄은 정수 l에 저장해 준다.문자열 s를 stringstream타입 ss로 변환해 주고, 공백을 기준으로 문자를 뽑아 정수형으로 변환 시킨다.변환시킨 정수를 lst에 넣어준 뒤 length변수에 lst의 사이즈를 구해준다.lst를 오름차순으로 정렬시킨 후 length!번의 브루트포스 알고리즘을 실행해 준다.만약 lst[i] + lst[j]가 l과 같다면 set에 해당 숫자 쌍을 추가해 준다.브루트포스가 끝나면 ans에 저장된 숫자 쌍을 모두..

리뷰 5달만에 다시 덤볐으나 문제 조건을 제대로 읽지 않아 또 져버렸다... https://www.acmicpc.net/problem/26596 문제 풀이재료의 개수 m과 황금 비율을 비교할 gold_rate를 1.618로, 문자열, 정수로 이루어진 맵 dic를 초기화 해준다.m값을 입력 받고 m만큼 루프를 돈 뒤 재료명과 값을 입력받아 재료명을 키로 갖는 맵에 값을 더해준다.flag를 0으로 초기화 해주고 맵을 두개로 나누어 순회하며 특정 재료의 값 * 황금비율이 다른 재료의 값과 동일한지 찾아준다. 이때 재료가 동일한 경우에는 황금 비율로 인정하지 않는다.만약 황금 비율을 찾았다면 flag를 1로 변경한 후 break 처리를 해준다.flag가 1인 경우 Delicious! 를, 아닐 경우 Not De..