개인사

리뷰 https://www.acmicpc.net/problem/1321세그먼트 트리를 활용해 군인을 적절한 부대에 배치시키는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 부대의 개수를 저장할 변수lst : 각 부대의 병사 수를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = lst[s]; else { int mid = (s + e) / 2; build(node * 2, s, mid); build(node * 2 + 1, mid + 1, e); tree[node] = tree[node * 2] + tree[node * 2 + 1]; }} 누적..

리뷰 https://www.acmicpc.net/problem/10090세그먼트 트리를 활용하여 배열 내 자신의 뒷 숫자 중 자기보다 작은 숫자의 개수를 구하는 문제  전역 변수N : 배열의 최대 길이를 저장할 상수 변수n : 배열의 길이를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) 세그먼트 트리의 초기화를 진행할 함수매개 변수로 노드 정보 node, 탐색 구간 s, e를 전달 받는다.기저 조건으로 리프노드에 도달한 경우 현재 노드의 값을 1로 저장해 준다.좌, 우 자식 노드로 재귀를 진행하고, 재귀를 빠져나오며 현재 노드를 두 노드의 합으로 저장해 준다. 2. updatevoid update(int node,..

리뷰 https://www.acmicpc.net/problem/19598회의실의 개수와 관련된 문제들은 일반적인 회의실 문제와 좀 다른 것 같다.  전역 변수n : 회의의 개수를 저장할 변수lst : 회의의 시작과 종료 시간을 저장할 배열 함수없음  문제풀이n값을 입력 받고, n개의 회의의 시작과 종료 시간을 lst배열에 입력 받는다. 이 때 종료시간을 앞에 저장해 준다.lst배열을 오름차순으로 정렬해 준다, 종료 시간 기준으로 오름차순 되어야 한다.멀티셋 dic을 초기화 해주고, 정답을 저장할 변수 ans를 0으로 초기화 해준다.n개의 회의 정보를 순회하며 현재 회의의 시작 시간을 기준으로 dic에서 upper_bound해준다.반환된 이터레이터가 dic의 begin()이라면 dic에 현재 회의의 종료시..

리뷰 https://www.acmicpc.net/problem/25417왠진 모르겠는데 조건문에 ||와 &&를 섞어서 작성 후 제출했었다 어이없게 두번을 틀렸다.  전역 변수lst : 맵 정보를 저장할 2차원 배열v : 방문 정보를 체크할 2차원 배열Pos : 현재 위치 x, y와 소요 시간 t를 정의할 구조체, t를 기준으로 오름차순 정렬한다.dx, dy : 4방향 탐색을 위한 방향 배열 함수1. bfsint bfs(int sx, int sy) 너비 우선 탐색을 통해 출발지 부터 도착지 까지 이동 하는 최소 시간을 구하는 함수매개 변수로 시작 위치의 좌표 sx, sy를 전달 받는다.Pos타입의 우선순위 큐 pq를 초기화 하고, 초기 위치 sx, sy와 소요 시간 0을 push해준다.v배열에 시작 위치를..

리뷰 https://www.acmicpc.net/problem/26086쿼리가 들어왔을 때 마다 처리해 주는건 당연히 시간이 터질 것 같았지만 한번 내봤다.  전역 변수n : 작업 고유번호의 제한값을 저장할 변수q : 쿼리의 개수를 저장할 변수k : 최종 출력할 작업의 인덱스를 저장할 변수deq : 작업 순서를 저장할 덱OP : 작업 종류 op, op가 0일 경우 작업 번호 val을 정의할 구조체ops : 작업 정보를 저장할 OP타입 배열last1 : 마지막 정렬 작업의 인덱스를 저장할 변수 함수없음  문제풀이n, q, k값을 입력 받고, q번의 for문을 개행해 q개의 쿼리를 입력 받아준다.변수 op에 작업의 종류를 입력 받아준다.op가 0일 경우 변수 num에 작업의 고유 번호를 추가로 입력 받은 후..

리뷰 https://www.acmicpc.net/problem/1884다익스트라이지만 고려해야할 요소가 거리 뿐만이 아닌 문제  전역 변수k : 교통비의 값을 저장할 변수n : 도시의 개수를 저장할 변수r : 도로의 개수를 저장할 변수Edge : 간선 정보 다음 노드 nn, 도로의 길이 l, 도로의 통행료 t를 정의할 구조체edges : 간선 정보를 인접 리스트로 저장할 Edge타입 벡터 배열Pos : 시뮬레이션 정보 현재 노드 cn, 현재 길이 cl, 현재까지의 통행료 ct를 정의할 구조체, cl이 동일하면 ct가 작은 순서대로, 아니라면 cl이 작은 순서대로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() 다익스트라를 통해 통행료 한도 내에서 1번 도시에서 N번 도시까지 가는 최..

리뷰 https://www.acmicpc.net/problem/15559오랜만에 재밌는 문제를 풀었다.  전역 변수n, m : 맵의 세로/가로 크기를 저장할 변수ans : 그룹의 개수를 저장할 변수lst : 이동할 방향의 인덱스를 저장할 2차원 배열g : 그룹 정보를 저장할 2차원 배열G : 그룹 번호를 저장할 변수B :  재귀를 빠져나올 때의 그룹 번호를 저장할 변수dx, dy : 4방향 탐색을 위한 방향 배열 함수1. dfsvoid dfs(int x, int y) 깊이 우선 탐색을 통해 그루핑을 진행하기 위한 함수매개 변수로 탐색을 진행할 위치의 좌표 x, y를 전달 받는다.첫 번째 기저 조건으로 현재 위치의 그룹이 G와 동일할 경우 리턴해 준다.두 번째로 현재 위치의 그룹이 지정 되었으며 G보다 작..

리뷰 https://www.acmicpc.net/problem/17092어음.. 풀긴했는데 이게 맞나 싶다.  전역 변수n, m : 맵의 세로/가로 크기를 저장할 변수q : 검정색 칸의 개수를 저장할 변수dic : 검정색 칸의 개수가 0~9개인 부분 모눈종이의 개수를 저장할 해시맵lst : 맵 정보를 저장할 2차원 해시맵 함수없음  문제풀이n, m, q값을 입력 받고, dic의 0의 값을 (n - 2) * (m - 2)로 초기화 해준다.dic의 key 1 ~ 9의 value를 0으로 초기화 해준다.q번의 while 루프를 수행하고, 매 루프마다 검은색 칸의 좌표를 입력 받아준다.lst의 x, y좌표에 해당하는 값을 1로 저장해 준다.x, y좌표에서 주변 9칸의 3 * 3크기의 모눈종이를 순회하며 검은칸의..

리뷰 https://www.acmicpc.net/problem/11562다익스트라로도 풀이가 가능한데 시간이 아슬아슬하다.  전역 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수k : 쿼리의 개수를 저장할 변수 함수없음  문제풀이n, m값을 입력 받고, n + 1 * n + 1크기의 2차원 벡터 dist를 매우 큰 값으로 초기화 해준다.m개의 간선 정보를 받아 dist벡터에 양방향 간선을 추가해 준다.이 때 만약 e가 0이면 반대 방향의 가중치는 1로, e가 1이면 양 방향 모두 가중치를 0으로 저장해 준다.간선 입력을 모두 받은 후엔 자기 자신으로 이동하는 가중치를 모두 0으로 저장해 준다.플로이드 와샬 알고리즘을 수행하여 각 노드간 최단 거리를 갱신하여 dist벡터에 저장해 준다..

리뷰 https://www.acmicpc.net/problem/12834다익스트라 알고리즘을 통해 최단 거리를 구하는 문제  전역 변수n : KIST 기사단 팀원의 수를 저장할 변수v : 노드의 개수를 저장할 변수e : 간선의 개수를 저장할 변수a, b : KIST와 씨알푸드 노드 번호를 저장할 변수Edge : 간선의 이동할 노드 node, 가중치 val을 정의할 구조체edges : 간선 정보를 인접리스트로 저장할 Edge타입 벡터 배열lst : KIST 기사단의 노드 번호를 저장할 배열ans : 정답을 저장할 변수Pos : 이동 정보의 현재 노드 node, 누적 가중치 val을 정의할 구조체, val을 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra(int sn) 시작 노드로..