개인사

[G4] 백준 29811번 지각하기 싫어 C++ 멀티셋

리뷰 https://www.acmicpc.net/problem/29811인구 수가 중복이 되는지 여부를 알 수 없어 멀티셋을 사용하여 풀이하였다.  전역 변수MAX : 배열 크기의 최대값을 저장할 상수 변수n : 애지문에서 대운동장까지의 경로 수를 저장할 변수m : 대운동장에서 ITBT관까지의 경로 수를 저장할 변수k : 쿼리의 개수를 저장할 변수N : 애지문에서 대운동장까지의 경로의 인구를 저장할 배열M : 대운동장에서 ITBT관까지의 경로의 인구를 저장할 배열NV : 애지문에서 대운동장까지의 경로의 인구와 인덱스를 오름차순으로 정렬할 멀티셋MV : 대운동장에서 ITBT관까지의 경로의 인구와 인덱스를 오름차순으로 정렬할 멀티셋 함수없음  문제풀이n, m값을 입력 받는다.1 ~ n까지의 인구수를 N배열에..

[G2] 백준 1445번 일요일 아침의 데이트 C++ 다익스트라

리뷰 https://www.acmicpc.net/problem/1445문제는.. 어렵진 않은데 자잘한 실수라던가 지문을 제대로 읽지 않아 발생할 문제가 많다.  전역 변수n, m : 맵의 세로/가로 길이를 저장할 변수sx, sy, ex, ey : 시작 및 도착 위치의 좌표를 저장할 변수dx, dy : 4방향 탐색을 위한 방향 배열Pos : 좌표 정보 x, y, 쓰레기를 밟은 횟수 g, 쓰레기 근처를 지나간 횟수 ng를 정의할 구조체, 기본적으로 g를 기준으로 오름차순 정렬하고, g가 동일한 경우엔 ng를 기준으로 오름차순 정렬한다. 함수1. dijkstrapair dijkstra() 다익스트라를 통해 출발지에서 목적지까지 쓰레기를 밟거나 근처를 지나는 최소를 구하는 함수Pos 타입의 우선순위 큐 pq를 ..

[G4] 백준 24955번 숫자 이어 붙이기 C++ 너비 우선 탐색

리뷰 https://www.acmicpc.net/problem/24955문자열을 통해 숫자를 이어 붙이기를 구현했다.  전역 변수MOD : 모듈러 연산을 위한 상수 변수N : 배열의 최대 크기를 정의할 상수 변수n : 집의 개수를 저장할 변수q : 쿼리의 개수를 저장할 변수nodes : 대문에 쓰여있는 수를 저장할 배열v : 방문 여부를 체크하기 위한 배열edges : 인접 리스트를 저장하기 위한 벡터 배열P : 현재 노드 node와 이어 붙인 수 cv를 정의할 구조체 함수1. bfsstring bfs(int sn, int en) 너비 우선 탐색을 통해 시작 지점부터 목표 지점까지 방문하며 이어 붙인 수를 구하기 위한 함수매개 변수로 시작 지점의 번호 sn, 도착 지점의 번호 en을 전달 받는다.P타입의..

[G4] 백준 12886번 돌 그룹 C++ 너비 우선 탐색

리뷰 https://www.acmicpc.net/problem/12886문제를 잘못 읽어 접근이 이상했는데 돌의 개수를 두개만 비교해도 된다는 접근을 하게 되었다.  전역 변수a, b, c : 세개의 돌의 크기를 저장할 변수total : 세 돌의 크기의 합을 저장할 변수v : 방문 정보를 체크하기 위한 변수S : 두 돌의 크기를 정의할 구조체 함수1. bfsbool bfs() 너비 우선 탐색을 통해 세 돌의 크기가 같아질 수 있는지 체크하기 위한 함수S타입의 큐 q를 초기화 하고, 세 돌 중 아무 돌이나 두개를 묶어 push해준다.두 돌의 현재 크기를 기준으로 v배열에 방문 처리를 진행해 준다.q가 빌 때 까지 while 루프를 순회하고, 매 루프마다 요소를 한개씩 꺼내어 준다.두 돌을 각각 변수 a, ..

리뷰 https://www.acmicpc.net/problem/31792트리 맵과 lower_bound를 활용한 문제  전역 변수q : 쿼리의 개수를 저장할 변수dic : 책의 가격을 저장할 트리 셋cnt : 가격별 책의 개수를 저장할 배열 함수없음  문제풀이q값을 입력 받고, q번의 while 루프를 수행 하고 매 루프마다 변수 op에 값을 입력 받아준다.op가 3이 아닌 경우 책의 가격을 변수 price에 입력 받아 저장해 준다.op가 1인 경우 dic에 price가 존재한다면 cnt의 price를 1만큼 증가시켜 준다.dic에 price가 존재하지 않으면 dic에 price를 insert해주고, cnt의 price를 1만큼 증가시켜 준다.op가 2인 경우 dic에 price가 존재한다면 cnt의 p..

리뷰 https://www.acmicpc.net/problem/1374간단한 정렬 + 우선순위 큐 문제  전역 변수n : 강의의 개수를 저장할 변수ans : 정답을 저장할 변수T : 강의의 시작 시간 st와 종료 시간 et를 정의할 구조체, et를 기준으로 오름차순 정렬한다.lst : 강의 정보를 저장할 T타입 배열pq : 강의 정보를 저장할 T타입 우선순위 큐 함수1. cmpbool cmp(const T& left, const T& right) 정렬 시 사용하기 위한 커스텀 비교 함수매개 변수로 T타입 변수 2개를 각각 left, right로 전달 받는다.right의 st가 left의 st보다 크다면 true를 리턴하여 두 요소의 순서를 바꾸어 준다. 문제풀이n값을 입력 받고, n개의 요소를 입력 받아..

리뷰 https://www.acmicpc.net/problem/2098비트마스킹 + DP를 사용해 푸는 기본적인 외판원 순회 문제, 새로운 알고리즘을 알게 되었다.  전역 변수N : 배열 크기의 최대값을 정의할 상수 변수n : 도시의 수를 저장할 변수w : 인접 행렬을 저장할 배열dp : 다이나믹 프로그래밍 정보를 저장할 배열 함수1. tspint tsp(int mask, int cur) 모든 도시를 순회하고 시작점으로 돌아오는 최소값을 구하는 함수매개 변수로 현재 도시 방문 비트 정보 mask와 마지막으로 방문한 도시 번호 cur을 전달 받는다.기저 조건으로 mask가 (1 이 때 현재 도시에서 시작점으로 돌아갈 수 없는 경우 매우 큰 값을 리턴해 주어야 한다.두 번째 기저 조건으로 이미 dp값이 계산..

리뷰 https://www.acmicpc.net/problem/25577선택 정렬을 구현하고, 교환 횟수를 구하는 문제  전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 원소의 개수를 저장할 변수lst : 초기 원소 정보를 저장할 배열sorted : 정렬 원소 정보를 저장할 배열dic : 인덱스를 매핑하기 위한 해시맵 함수없음  문제풀이n에 값을 입력 받고, n개의 원소 정보를 lst배열에 입력 받는다.sorted배열에 lst의 값을 복사하여 저장하고, dic엔 현재 입력된 원소의 인덱스를 매핑해 준다.sort 함수를 통해 sorted 배열을 오름차순으로 정렬해 준다.변수 cnt를 0으로 초기화 해주고, n번의 for문을 순회해준다.만약 lst와 sorted 배열의 현재 인덱스의 값이 상이할 ..

리뷰 https://www.acmicpc.net/problem/13023N이 2000이라 가지치기가 필요할 것이라 생각했는데 그냥 제출해도 되는 문제였다.  전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 사람의 수를 저장할 변수m : 친구 관계의 수를 저장할 변수ans : 정답 여부를 저장할 변수v : 방문 정보를 저장할 배열edges : 인접 리스트를 저장할 배열 함수1. dfsvoid dfs(int level, int node) 깊이 우선 탐색을 통해 연속된 5명의 친구 관계가 있는지 체크하는 함수매개 변수로 재귀 단계 level과 현재 노드 번호 node를 전달 받는다.기저 조건으로 재귀 단계가 5가 될 경우 ans를 true로 변환 후 return 처리한다.node의 인접 리스트를 순..

리뷰 https://www.acmicpc.net/problem/9466싸이클에 속하지 못한 노드의 개수를 구하는 문제  전역 변수N : 배열의 최대 크기를 정의할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : 노드의 개수를 저장할 변수cnt : 싸이클에 속하지 못한 노드의 개수를 저장할 변수lst : 이동할 다음 노드를 저장할 배열v : 방문 상태를 저장할 배열cycle : 싸이클에 속했는지 여부를 저장할 배열 함수1. dfsvoid dfs(int node) 깊이 우선 탐색을 통해 싸이클 유무를 찾기 위한 함수매개 변수로 탐색할 현재 노드의 번호를 전달 받는다.v배열에 현재 노드의 상태를 1로 변경해 준다.다음 노드를 변수 next에 저장해 준다.v배열의 next값이 0이라면 dfs함수에 ne..

리뷰 https://www.acmicpc.net/problem/15899서브 트리에서 특정 값 이하의 개수를 구하는 문제  전역 변수N : 정점의 개수를 저장할 변수MOD : 모듈러 연산을 위한 변수lst : 각 노드의 색을 저장할 배열color : 노드 방문 정보를 기준으로 색을 저장할 배열edges : 인접 리스트를 저장할 벡터 배열n : 정점의 개수m : 쿼리의 개수를 저장할 변수c : 색의 최대값을 저장할 변수it : 트리 탐색 시 진입 시간을 저장할 배열ot : 트리 탐색 시 탈출 시간을 저장할 배열t : 트리 탐색 시 시간을 저장할 변수ans : 정답을 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열 함수1. dfsvoid dfs(int node, int par) 깊이 우선 탐색을 통..

리뷰 https://www.acmicpc.net/problem/29197원점에서 보이는 직선의 개수를 구하는 문제  전역 변수z : 기울기가 없는 직선을 저장할 해시맵one, two, three, four : 1 ~ 4사분면에 위치한 직선을 저장할 해시맵n : 학생의 수를 저장할 변수 함수없음  문제풀이n을 입력 받고, n명의 학생의 좌표를 입력 받아 사분면을 구분하여 기울기를 각 해시맵에 저장한다.모든 해시맵의 크기를 더해 출력한다. 트러블 슈팅없음  참고 사항원점에서 보는 것이기 때문에 각 사분면 마다 체크를 진행해 주어야 한다.기울기가 없는 경우 divide zero에 유의하여야 한다. 정답 코드#include#includeusing namespace std;unordered_map z;unorde..

리뷰 https://www.acmicpc.net/problem/19940BFS로 0 ~ 59초에 해당하는 모든 그리디한 값을 구해두고 O(1)로 푸는 문제  전역 변수N : 시뮬레이션 시 나올 수 있는 최대값을 저장할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : 테스트 케이스 마다 시간을 저장할 변수T : 각 버튼을 클릭한 횟수 ah, at, mt, ao, mo와 남은 시간 cur을 정의할 구조체ts : 각 버튼을 클릭한 횟수의 최적값을 저장할 T타입 배열v : 시간 방문 여부를 체크하기 위한 배열 함수1. bfsvoid bfs() 너비 우선 탐색을 통해 각 시간에 도달하는 최적값을 구하기 위한 함수T타입의 큐 q를 초기화 하고, 모든 값을 0인 상태로 q에 push해준다.q가 빌 때 까지 ..

리뷰 https://www.acmicpc.net/problem/15662톱니바퀴를 회전시켜 연쇄반응을 구현하는 문제  전역 변수t : 톱니바퀴의 개수를 저장할 변수k : 회전의 횟수를 저장할 변수flag : 회전 방향을 체크하기 위한 변수deq : 톱니바퀴의 상태를 저장할 덱 배열 함수1. turn_rightvoid turn_right(int idx) 톱니바퀴를 오른쪽으로 회전시키는 시뮬레이션을 진행할 함수매개 변수로 톱니바퀴의 번호 idx를 전달 받는다.톱니바퀴 번호가 idx인 덱에서 뒤의 요소를 뺀 뒤 앞의 요소로 집어넣는다.작업 후에는 flag를 반전시킨다. 2. turn_leftvoid turn_left(int idx) 톱니바퀴를 왼쪽으로 회전시키는 시뮬레이션을 진행할 함수매개 변수로 톱니바퀴의 ..

리뷰 https://www.acmicpc.net/problem/2149실버 3 문제가 왜이리 어렵고 디버깅이 힘든지 모르겠다..  전역 변수a : 키를 저장할 변수b : 암호문을 저장할 변수IC : 인덱스 idx와 문자 ch, 문자열 str을 정의할 구조체ics : IC타입의 벡터 함수1. cmp_CHbool cmp_CH(const IC& left, const IC& right) 단어를 기준으로 오름차순 정렬하기 위한 함수 2. cmp_IDXbool cmp_IDX(const IC& left, const IC& right) 인덱스를 기준으로 오름차순 정렬하기 위한 함수 문제풀이a, b를 입력 받고, 키의 길이를 m, 각 키에 할당될 암호문의 길이를 n으로 초기화 한다.ics벡터를 m크기로 resize해주고..

리뷰 https://www.acmicpc.net/problem/14267더 쉬운 방법이 있는데 익숙한 방법으로 풀었다.  전역 변수N : 배열 크기 최대값을 저장할 상수 변수n : 직원의 수를 저장할 변수m : 칭찬의 수를 저장할 변수lst : 인접 리스트를 저장할 벡터 배열it : 오일러 경로의 진입 시간을 저장할 배열ot : 오일러 경로의 탈출 시간을 저장할 배열t : 오일러 경로의 시간을 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열lazy : 업데이트 값 정보를 저장할 배열 함수1. dfsvoid dfs(int cur) 오일러 경로를 구하기 위한 함수매개 변수로 현재 직원의 번호를 전달 받는다.현재 직원의 it배열의 값에 t를 전위 증가한 값을 저장한다.현재 직원의 인접 리스트를 순회하..

리뷰 https://www.acmicpc.net/problem/2151최소한의 거울을 설치하여 한쪽 문에서 다른 문으로 이동하는 경로를 찾는 문제  전역 변수n : 맵의 가로/세로 길이를 저장할 변수sx, sy : 탐색을 시작할 문의 좌표를 저장할 변수ex, ey : 도착할 문의 좌표를 저장할 변수lst : 맵 정보를 저장할 문자열 배열bool : 설치한 거울의 개수로 방문 정보를 체크할 배열Pos : 시뮬레이션 시 사용할 현재 좌표 x, y, 현재 방향 d, 설치한 거울의 수 c를 정의할 구조체, c를 기준으로 오름차순 정렬해 준다.dx, dy : 4방향 탐색을 위한 방향 배열 함수1. dijkstraint dijkstra() 다익스트라를 사용해 출발 문에서 도착 문까지 이동할 때 최소 설치 거울의 개..

리뷰 https://www.acmicpc.net/problem/17396문제 조건을 읽고 분명 int로 터진다는건 알고 있었지만... 실수를 해서 두번이나 틀렸다. ㅠ  전역 변수N : 분기점의 최대 개수를 저장할 상수 변수n : 분기점의 개수를 저장할 변수m : 간선의 개수를 저장할 변수lst : 각 분기점이 시야에 노출되는지를 저장할 정수형 배열Edge : 간선 정보 중 다음 노드 nn, 간선의 가중치 nt를 정의할 구조체edges : 인접 리스트를 저장할 Edge타입 벡터 배열Pos : 시뮬레이션 시 사용할 현재 노드 cn, 현재 누적 시간 ct를 정의할 구조체, ct를 기준으로 오름차순 정렬한다. 함수1. dijkstrall dijkstra() 다익스트라를 통해 시야를 피해 넥서스 까지 가는 최단..

리뷰 https://www.acmicpc.net/problem/2866행을 위에서 부터 한 줄씩 제거하며 같은 열에 있는 문자열의 중복이 없는 최대로 삭제가 가능한 행의 개수를 구하는 문제  전역 변수n, m : 테이블의 세로/가로 길이를 저장할 변수ans : 정답을 저장할 변수lst : 테이블 정보를 저장할 문자열 배열 함수없음  문제풀이n, m값을 입력 받고, n개의 문자열을 lst배열에 입력 받아준다.변수 l을 0으로, r을 n - 1로 초기화 하고, l이 r미만인 경우 true로 while루프를 실행해 준다.매 루프마다 변수 mid에 l + r을 2로 나눈 몫을 저장해 주고, string, bool타입 해시맵 v를 초기화 해준다.변수 flag를 true로 초기화 하고, 변수 s에 mid행 부터 마..

리뷰 https://www.acmicpc.net/problem/1520DFS + DP를 활용하여 푸는 문제, 그냥 DFS로 접근했다가 시간 초과를 계속 받았다.  전역 변수n, m : 맵의 세로/가로 길이를 저장할 변수lst : 맵 정보를 저장할 2차원 배열v : 방문 처리를 위한 2차원 배열dp : 우하단으로 이동 가능한 경로의 개수를 저장할 2차원 배열dx, dy : 4방향 탐색을 위한 방향 배열 함수1. dfsint dfs(int x, int y) 너비 우선 탐색 + DP를 통해 우하단으로 이동 가능한 모든 경로의 개수를 구하는 함수첫 번째 기저 조건으로 맵의 우하단에 도달하였다면 1을 리턴해 준다.두 번째 기저 조건으로 이미 dp값이 저장되어 있다면 해당 값을 리턴해 준다.현재 좌표의 dp값을 0..