개인사

리뷰 일반적인 BFS를 사용하니 바로 시간 초과가 출력되었다!!벽을 의미하는 1을 보기 보단, 0부터 본 후에 1을 체크하는 방식이 효율적인 문제였다. 위에서부터 차례대로 group정보를 배열, 벡터, unordered_map을 사용하여 관리한 정보이다.배열이 시간은 가장 빠르고 벡터가 메모리 낭비가 덜 심하고 해시는 그닥 효율이 좋지 못했다.따라서 해당 문제는 벡터를 활용한 방법으로 설명하겠다.https://www.acmicpc.net/problem/16946 문제 풀이전역변수lst : 맵을 저장할 문자열 벡터group : 그룹의 면적을 저장할 벡터, 인덱싱을 위해 크기를 1을 가진 상태로 시작한다.groups : 그룹의 면적을 2D맵에 나타내기 위한 배열v : 방문을 체크하기 위한 배열, 사실상 gr..

리뷰 다각형의 면적을 구하는 방법은 또 처음 알았다! 슈메르카우스키의 공식... 이세상엔 천재가 많다.덕분에 좌표 평면상에서의 다각형의 공식을 구하는 방법은 잊지 않을 것 같다!https://www.acmicpc.net/problem/2166 문제 풀이꼭지점의 개수 n과, 정답용 변수 ans, 좌표 구조체 Pos와 그의 배열 poses를 전역 변수로 세팅한다.n값을 입력 받고 n개의 꼭지점 좌표를 받아와 poses배열에 추가해 준다.n - 1번째 까지의 꼭지점을 탐색하며 xi*yi+1 - yi*xi+1 을 구해준 뒤 ans에 더해준다.최종적으로 0번째와 n - 1번째 인덱스의 꼭지점을 처리해 준 뒤 ans를 2로 나누어 준다.ans에 절댓값을 씌운 뒤 소숫점 1자리까지 반올림하여 출력해 주면 된다.  참..

리뷰경로 상에 신호등이 있어 기다렸다가 움직여야 하는 최단 경로 문제, 다른 문제와 다른점은 신호등의 방향이 정해져 있어 교차로에 진입하는 경우를 잘 분배해 주어야 했다.https://www.acmicpc.net/problem/1400 문제 풀이행 범위n, 열 범위 m, 시작 좌표 sx, sy 도착 좌표 ex, ey, 방향 배열, 맵 정보 lst배열을 전역 변수로 세팅한다.우선 순위 큐에서 사용할 Pos구조체를 정의하고, compare함수도 넣어준다.신호등 정보를 받을 구조체 Light를 정의하고, 신호등 배열 lights를 60크기로 설정해 준다.main함수에서 무한루프를 실행하고 input함수에서 n, m이 0, 0이라면 while루프를 종료해 준다.input함수를 통해 n, m값을 받고 만약 n과 ..

리뷰 구현이 생각보다 빡세서 많이 애먹었다.. 4달 전에도 못풀었지만 4달이 지난 후에도 애를 먹은 문제 ㅠㅠ대신 멀티셋이라는 새로운 STL을 접하게 된 계기가 되었다.https://www.acmicpc.net/problem/7662 문제 풀이각 테스트 케이스마다 쿼리의 개수 k를 입력받고, 정수형 멀티셋 dic을 초기화 해준다.각 쿼리마다 I또는 D값이 입력되므로 해당 값을 문자 타입 order 변수에 입력 받는다.추가로 order 뒤에는 항상 정수 값이 입력되므로 정수형 변수 n에 값을 입력 받는다.order가 I인 경우 dic에 n을 insert 해준다.order가 D인 경우 dic이 비어있으면 continue, 아니라면 최대 최소에 따라 dic의 end와 begin을 erase 해준다.모든 쿼리에..

리뷰 가수의 출연 순서를 구하는 위상 정렬 문제, 보조PD 라는 것에 의미를 부여하는 함정에 빠지면 안된다.https://www.acmicpc.net/problem/2623 문제 풀이가수의 개수n, 보조 PD의 개수m, 인접리스트용 벡터 path를 전역변수로 설정해 준다.n과 m값을 입력 받고, m크기만큼의 루프를 돌려준다, 이후 가수의 개수 a와 가수 b를 입력 받아준다.가수의 개수를 전위 감소 연산을 통해 while루프를 돌려주고 그 이후의 가수 c를 입력 받아준다.b의 path에 c를 push_back을 해준 뒤 b를 c로 교체시켜 준다. 이후 계속 반복해 준다.위 작업을 통해 가수의 순서대로 우선 순위가 적용되어 가수간의 출연 순서가 만들어 진다.cnt벡터를 n + 1크기로, 값은 모두 0으로 초..

리뷰 하 너무 어려웠던 지옥같은 문제, 투 포인터 문제중에선 골드 2치고 굉장히 어려웠다.https://www.acmicpc.net/problem/7453 문제 풀이a, b, c, d배열에 값을 받아 줄 abcd를 최대치의 크기 4000 * 4의 크기로 전역 변수로 설정해 준다.ab와 cd 배열을 합칠 벡터 ab, cd와 정답을 저장할 변수 ans를 long long타입으로 전역 변수로 설정해 준다.n값을 입력 받고 n * 4 크기의 배열을 abcd 배열에 입력받아 저장해 준다.n * n크기의 브루트포스를 통해 각 경우의 수를 찾아 a + b는 ab에, c + d는 cd에 저장해 준다.ab와 cd 배열을 모두 오름차순으로 정렬해 준 후 투 포인터 탐색을 시작해 준다.p1은 ab벡터의 포인터로 0부터 시작..

리뷰 용액 문제의 상위 버전으로 세가지 용액의 특성값의 합이 0에 가까운 케이스를 뽑는 문제https://www.acmicpc.net/problem/2473브루트포스 + 투 포인터를 사용한다면 최악의 경우 n^2 / 2로 n값이 10만이면 시간 복잡도상 안 돌아갈 줄 알았는데 생각보다 빠르게 실행돼서 의문이 좀 가긴 했다. 문제 풀이용액의 개수 n과 용액의 특성값 정보 배열 lst를 전역 변수로 설정한다. 이때 용액 세개를 더하므로 타입은 longlongn을 입력 받고 lst 배열에 각 용액의 특성값을 입력받는다, 이후 오름차순으로 정렬해 준다.정답 출력용 al, am, ar 변수를 초기화 하고 ans값을 30억으로 설정해 준다, ans도 longlong타입으로 설정한다.첫번재 용액은 브루트포스를 통해 ..

리뷰 두 용액의 합이 0과 가장 가까워 지는 순서쌍을 출력하는 문제https://www.acmicpc.net/problem/2467 문제 풀이용액의 개수 n과 용액의 특성값을 저장할 lst배열을 용액의 최대치 만큼의 크기로 설정한다.n값을 입력 받고 n개의 용액의 특성값을 lst배열에 저장해 준 후 lst배열을 오름차순으로 정렬해 준다.left는 0부터 right는 n - 1부터 탐색을 시작하고 정답을 출력할 al, ar를 초기화 하고 ans는 매우 큰 값으로 초기화 한다.left가 right보다 작을때만 탐색을 진행해 준다. lst의 left와 right 인덱스를 더한값을 sum에 저장해 준다.sum의 절댓값이 ans보다 작으면 ans를 갱신시켜 준다, 만약 0일 경우 바로 탐색을 종료한다.ans가 갱..

리뷰 포인터 두개를 늘려가며 수열에서의 부분합이 특정 수 이상이 되는 가장 짧은 길이를 찾는 문제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 도시를 각..