개인사

[G5] 백준 25556번 포스택 C++ 구현

리뷰 https://www.acmicpc.net/problem/25556문제를 보고 금방 아이디어가 떠올랐다. 스택없어도 풀릴것 같은데? 했는데 제출하니 AC를 받았다. 전역 변수n : 순열의 길이를 저장할 변수back : 스택의 마지막 요소의 값을 저장할 배열 함수없음 문제풀이n값을 입력 받고, n개의 순열의 요소를 변수 a에 입력 받고, 변수 flag를 false로 초기화 한다.back을 순회하며 값이 a보다 작은 스택을 찾으면 flag를 true로, 값을 a로 바꾼 후 break처리한다.모든 back의 값이 a보다 클 경우 NO를 출력하고 리턴 처리해 준다.n개의 요소를 처리할때 까지 기저 조건에 해당하지 않았으면 YES를 출력해 준다. 트러블 슈팅없음 참고 사항4개의 스택의 마지막 요소가 현..

[G1] 백준 1800번 인터넷 설치 C++ 다익스트라, 다이나믹 프로그래밍, 매개변수 탐색

리뷰 https://www.acmicpc.net/problem/1800다익스트라 + DP + 매개변수 탐색을 사용하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 정점의 개수를 저장할 변수p : 간선의 개수를 저장할 변수k : 공짜로 제공하는 케이블선의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 저장할 Edge타입 벡터 배열Pos : 현재 상태를 정의하기 위한 구조체, 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstrabool dijkstra(int mv) { priority_queue pq; pq.push({ 1, 0, 0 }); vector> dist(n + 1, vector(k + 1, mv + 1)); dist[1][0] = ..

리뷰 https://www.acmicpc.net/problem/16118달빛 늑대의 최단 거리를 구하는 로직에서 다익스트라 만으로는 구현이 불가하고 DP까지 섞어줘야 한다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 정점의 개수를 저장할 변수m : 간선의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 인접 리스트로 저장하기 위한 Edge타입 벡터 배열Fox : 여우의 움직임을 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다.Wolf : 늑대의 움직이을 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstra_Foxvector dijkstra_fox() { priority_queue pq; pq.push({ 1, 0 ..

리뷰 https://www.acmicpc.net/problem/27440세가지 연산을 통해 주어진 수를 1로 만드는 최단 연산 횟수를 구하는 문제 전역 변수n : 1로 만들기 위한 정수를 저장할 변수v : 각 수에 도달한 연산 횟수를 저장할 해시맵 함수1. divvoid div(ll cur, int val, queue& q) { if (cur % val) return; ll next = val != 1 ? cur / val : cur - 1; auto it = v.find(next); if (it != v.end()) return; v[next] = v[cur] + 1; q.push(next);} 연산을 수행하고, 수행이 유효하면 방문체크 후 큐에 추가하기 위한 함수 2. bfsint bfs() { q..

리뷰 https://www.acmicpc.net/problem/2463자동 타입 형변환에서 변수의 위치가 중요하다는 것을 새삼 다시 깨닫게 되는 문제였다. 전역 변수N : 정점의 최대 번호를 정의할 상수 변수MOD : 모듈러 연산값을 정의할 상수 변수n : 정점의 개수를 저장할 변수m : 간선의 개수를 저장할 변수ans : 정답을 저장하기 위한 변수total : 간선의 가중치 합을 저장하기 위한 변수Edge : 간선 정보를 정의할 구조체, 가중치를 기준으로 내림차순 정렬한다.edges : 간선 정보를 저장할 Edge타입 벡터nodes : 노드가 속한 그룹의 번호를 저장할 배열sizes : 노드가 속한 그룹의 크기를 저장할 배열 함수1. Findint Find(int a) { if (nodes[a] ==..

리뷰 https://www.acmicpc.net/problem/28707신박하긴한데 골드 1정도의 문제인가? 싶긴 하다. 전역 변수n : 배열의 길이를 저장할 변수m : 조작의 개수를 저장할 변수Order : 조작의 정보를 정의할 구조체orders : 조작 내용을 저장할 Order타입 벡터Cur : 현재 문자열과 소모한 비용을 정의할 구조체, 소모한 비용을 기준으로 오름차순 정렬한다.v : 각 문자열에 도달한 최소 비용을 저장할 해시맵 함수1. to_strstring to_str(const vector& lst) { string temp = ""; for (int i = 0; i 배열 정보를 문자열 형식으로 변환하기 위한 함수 2. dijkstraint dijkstra(string st, const ..

리뷰 https://www.acmicpc.net/problem/20501사실상 통과하지 못할 것 같았는데 아슬아슬하게 첫트에 통과되었다.(+추가) 비트 집합의 버킷 크기를 크게 할수록 시간이 빨라진다. 전역 변수N : 사용자의 최대 수를 정의할 상수 변수B : 최대 비트 버킷을 정의할 상수 변수n : 사용자의 수를 저장할 변수q : 쿼리의 수를 저장할 변수bits : 사용자별 친구 관계를 저장할 1바이트 2차 배열 함수없음 문제풀이n값을 입력 받고, n*n크기 행렬을 통해 친구 관계를 bits배열에 초기화 해준다.q값을 입력 받고, 변수 m을 n을 8로 나눈 나머지가 있을 경우 n/8+1로, 맞아 떨어진다면 n/8로 저장한다.q번의 쿼리문을 수행하고, 매 쿼리 마다 변수 a, b에 친구 번호를 입력 ..

리뷰 https://www.acmicpc.net/problem/2585다익스트라 + DP로 접근했다가 급유 처리 로직이 애매해서 다익스트라 + 매개변수 탐색으로 변경했다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 급유지의 개수를 저장할 변수k : 급유할 수 있는 최대 횟수를 저장할 변수Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 인접 리스트로 저장할 Edge타입 벡터 배열Pos : 급유지의 좌표 정보를 정의할 구조체poses : 각 급유지의 좌표 정보를 저장할 배열PF : 비행 상태를 정의할 구조체, 누적 연료 사용량을 기준으로 오름차순 정렬한다. 함수1. get_fuelint get_fuel(int x1, int y1, int x2, int y2) { double..

리뷰 https://www.acmicpc.net/problem/27211맵의 경계선이 없는 환경에서 플러드필을 통해 섬의 개수를 구하는 문제 전역 변수N : 맵의 최대 변의 크기를 정의할 상수 변수n : 맵의 세로 길이를 저장할 변수m : 맵의 가로 길이를 저장할 변수v : 맵 정보 및 방문 여부를 체크할 2차원 배열dx, dy : 4방향 탐색을 위한 방향 배열Pos : 현재 위치의 x, y좌표를 정의하기 위한 구조체 함수1. bfsvoid bfs(int sx, int sy) { queue q; q.push({ sx, sy }); while (!q.empty()) { Pos pos = q.front(); q.pop(); int cx = pos.cx, cy = pos.cy; for (int i = ..

리뷰 https://www.acmicpc.net/problem/1911간단한 그리디 알고리즘 문제 전역 변수n : 물웅덩이의 개수를 저장할 변수l : 널빠진의 길이를 저장할 변수 함수없음 문제풀이n, l값을 입력 받고, pair타입의 오름차순 정렬 우선순위 큐 pq를 초기화 한다.n개의 물웅덩이의 시작과 끝 좌표 정보를 입력 받아 pq에 push해준다.변수 c를 pq의 top요소의 first값으로 저장하고, 변수 ans를 0으로 초기화 한다.pq가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내 변수 s, e에 값을 파싱해 준다.c가 e이상일 경우 continue처리해 준다. 아닐 경우 c를 s와 비교해 더 큰값으로 갱신해 준다.변수 diff에 e-c를 저장하고, div를 diff..