개인사

리뷰 https://www.acmicpc.net/problem/1744처음엔 백트래킹을 통한 완전 탐색을 통해 구현하였지만 N값이 50이라 당연하게도 시간 초과가 났다.이후 우선순위 큐를 사용해 그리디하게 구현하였고, 음수끼리 묶은 경우 양수가 나오는 점을 그리디하게 수정하였더니 AC를 받게 되었다.  전역 변수n : 수열의 길이를 저장할 변수ans : 정답을 저장하고 출력하기 위한 변수p : 1이상의 수를 저장하기 위한 우선순위 큐m : 0이하의 수를 저장하기 위한 우선순위 큐 함수없음  문제풀이n을 입력받고 n개의 원소를 정수형 변수 num에 입력 받아준다.만약 num이 0이하라면 m에, 1이상이라면 p에 push를 해준다.p가 빌 때까지 루프를 돌며 정수형 변수 num에 p의 top인 요소를 뽑아준..

리뷰 https://www.acmicpc.net/problem/9019어디서 많이 풀어본 것 같은 문제, 처음엔 문자열로 접근했다가 보기 좋게 시간 초과를 받았다.정수형으로 접근하니 AC를 받긴 했으나 가지치기가 더 필요해 보여 최적화는 아닌듯 하다.  전역 변수t : 테스트 케이스의 개수를 저장할 정수형 변수s, e : 각 테스트 케이스의 초기값과 목표값을 저장하기 위한 정수형 변수v : 방문 여부를 체크하기 위한 정수형 배열Cur : 현재 탐색 중인 숫자와 여태까지의 명령을 저장하기 위한 구조체 함수1. bfsstring bfs() 너비 우선 탐색을 통해 목표 값을 찾고 사용한 명령어를 리턴하기 위한 힘수Cur타입의 큐 q를 초기화 하고 초기값 s와 빈 문자열 ""를 넣어준다.초기값의 방문 처리를 체..

리뷰 https://www.acmicpc.net/problem/1277노드간 간선을 직접 초기화 하고, 가중치가 소수타입인 다익스트라 문제  전역 변수n : 발전소의 개수w : 남아있는 전선의 개수m : 전선(간선)의 제한 길이Pos : 각 노드의 x, y 좌표 위치를 저장할 구조체Edge : 각 간선이 가르키는 다음 노드와 가중치를 정의할 구조체Node : 최단 경로를 찾을 때 사용할 구조체poses : 각 노드의 위치 정보를 저장할 Pos타입 배열lst : 각 노드에서의 간선 정보를 인접 리스트로 저장할 Edge타입 벡터 배열 함수1. dijkstraint dijkstra() n번째 발전소 까지 최단 경로를 구하기 위한 함수Node타입 우선순위 큐 pq를 초기화 한다.pq에 1번 발전소와 현재 까지의..

리뷰 https://www.acmicpc.net/problem/1263골드 치고는 굉장히 쉬운 그리디 알고리즘 문제  전역 변수n : 작업의 개수를 저장할 변수Job : 작업을 정의할 구조체, 소요 시간 및 데드라인과 우선순위 큐용 cmp함수를 정의한다. 함수없음  문제풀이n을 입력 받고, Job타입의 우선순위 큐 pq를 초기화 한다.n개의 작업의 소요 시작 및 데드라인을 입력 받고 pq에 push해준다.si가 최대 100만이니 정수형 변수 now를 100만보다 크게 설정해 준다.pq가 빌 때까지 즉, 모든 작업을 처리할 때 까지 루프를 수행한다.만약 pq의 top보다 now가 크다면 pq의 top으로 now를 변경해 준다.정수형 큐 q를 초기화 하고, now보다 크거나 같은 데드라인을 가진 작업을 pq..

리뷰 https://www.acmicpc.net/problem/1092그리디 문제지만 여러가지 자료 구조와 알고리즘을 접목하여 푼 문제주어지는 화물이 1만개 이하이므로 이진 탐색 메서드를 통해 O(LogN) 내로 풀이가 가능하다.  전역 변수n : 주어지는 크레인의 개수m : 주어지는 화물의 개수ans : 정답을 저장하기 위한 변수mc : 크레인의 max값을 저장하기 위한 변수mb : 화물의 max값을 저장하기 위한 ㅂ젼수wait : 현재 턴에 아직 사용하지 않은 크레인을 저장할 정수 타입의 큐used : 현재 턴에 사용한 크레인을 저장할 정수 타입의 큐boxes : 화물 정보를 저장하기 위한 정수 key와 정수 value타입의 맵 함수없음  문제풀이n값을 입력 받고, n개의 크레인 정보를 받아 mc에 ..

리뷰 https://www.acmicpc.net/problem/16509상을 움직이는 문제지만, 이동 중 다른 기물이 있다면 이동할 수 없는 조건이 추가된 문제  전역 변수Pos : 말의 위치와 현재 까지 이동한 시간을 기록하기 위한 구조체King : 왕의 위치를 저장하기 위한 Pos타입 변수Elep : 상의 위치를 저장하기 위한 Pos타입 변수r, c : 맵의 행과 열의 제한을 두기 위한 정수형 상수 변수dx, dy : 상의 이동을 시뮬레이션 하기 위한 방향 배열, 각 케이스 마다 하드 코딩 해주었다.map : 왕의 위치를 1로 표기하여 좀 더 편하게 시뮬레이션 하기 위한 정수형 2차 배열v : 방문 처리를 기록하기 위한 정수형 2차 배열 함수1. bfsint bfs() 너비 우선 탐색을 통해 상이 왕..

리뷰 https://www.acmicpc.net/problem/13544간만에 푼 머지소트 트리 문제, 예제 답이 제대로 나오지 않아 한참 찾았는데 query 함수 내에서 범위 처리를 잘못했었다.세그먼트 트리 문제는 항상 조그만 실수에도 문제 전체가 달라져 버리니 주의 요망  전역 변수N : 수열의 최대 길이를 저장하기 위한 정수형 상수 변수n : 문제에 주어지는 수열의 크기m : 문제에 주어지는 쿼리의 개수i : 탐색할 범위의 왼쪽j : 탐색할 범위의 오른쪽k : 탐색할 값last : 이전 쿼리의 결과nodes : 수열 정보를 저장하기 위한 정수형 배열tree : 세그먼트 트리 정보를 저장하기 위한 정수형 벡터 배열 함수1. buildvoid build(int node, int s, int e) 머지 ..

리뷰 https://www.acmicpc.net/problem/9372문제 분류로 풀어보기에서 MST에 있길래 시도했으나 일반적인 BFS나 DFS로도 해결이 가능한 문제  전역 변수t : 테스트 케이스의 개수n : 국가의 개수m : 주어지는 인접 리스트의 개수v : 방문 처리용 정수형 배열 함수1. bfsint bfs(int sn, const vector>& lst) 너비 우선 탐색을 통해 방문한 간선의 최소 개수를 구하기 위한 문제매개변수로 시작 국가의 번호 sn과 인접 리스트 lst를 전달 받는다.정수형 타입 큐 q를 초기화 하고 sn을 큐에 삽입해 준다.sn을 방문처리 해주고, 방문한 국가 cnt를 1로, 탑승한 비행기의 수 result를 0으로 초기화 한다.q가 빌때 까지 반복문을 수행하고, 매 ..

리뷰 https://www.acmicpc.net/problem/14713문제가 잘 이해되지 않았는데 예상되는 케이스를 반례로 넣었더니 AC를 받았다.알고리즘 분류에 큐가 적혀있는데 큐 없이도 문제가 해결 가능했다, 어쩌면 더 최적화 코드가 있을 지도?  전역 변수n : 앵무새의 개수idx : 각 앵무새가 읽은 단어의 인덱스를 저장하기 위한 정수형 배열 함수없음  문제풀이key가 문자열, value가 pair타입인 해시맵 dic을 초기화 해준다.n값을 입력 받고, 이후 문자열을 getline으로 받을 것이기 때문에 cin.get()를 수행해 준다.n번의 반복문을 실행하고, 정수형 변수 index를 0으로 초기화 해준다.빈 문자열 변수 s를 초기화 하고 getline을 통해 cin값을 s에 저장해 준다.st..

리뷰 https://www.acmicpc.net/problem/2504스택 문제인건 알겠으나 괄호의 배치에 따른 정답 연산에 애먹은 문제  전역 변수s : 입력되는 괄호의 정보를 저장할 문자열 변수stack : 괄호의 여닫기를 체크하기 위해 스택으로 사용할 문자 타입의 벡터 함수없음  문제풀이괄호로 이루어진 문자열을 s에 입력 받아준다.정답을 출력할 변수 ans를 0으로, 시뮬레이션에 사용할 변수 temp를 1로 초기화 한다.문자열 s의 길이만큼의 반복문을 실행해 준다.만약 s[i]가 '(', '['라면 temp에 2배, 3배를 곱해주고 스택에 괄호를 추가해 준다.만약 s[i]가 ')'라면 우선 스택이 비어있거나 스택의 맨 위가 '('가 아니라면 탐색을 중지하고 0을 출력한다.맞다면 s[i - 1]이 '..