개인사

리뷰 https://www.acmicpc.net/problem/17352그래프에서 다른 그룹인 두 노드의 번호를 출력하는 문제 전역 변수N : 배열의 최대 크기를 정의할 정수형 상수 변수n : 노드의 개수를 저장할 정수형 변수v : 방문 여부를 저장할 논리형 배열edges : 간선 정보를 저장할 정수형 벡터 배열 함수1. bfsvoid bfs(){ queue q; q.push( 1 ); v[ 1 ] = true; while ( !q.empty() ) { int cn = q.front(); q.pop(); for ( int nn : edges[ cn ] ) { if ( v[ nn ] ) continue; v[ nn ] = true; q.push( nn ); } }} 같은 그래프 내..

리뷰 https://www.acmicpc.net/problem/16432깊이 우선 탐색과 메모제이션을 활용해 푸는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수flag : 최적 경로를 찾았는지 여부를 저장할 변수edges : 간선 정보를 저장할 벡터 배열v : 이미 방문한 상황인지 여부를 체크하기 위한 2차원 배열 함수1. dfsvoid dfs( int level, vector& stack ){ if ( flag ) return; if ( level == n ) { flag = true; for ( int i : stack ) cout n까지 도달 가능한 최적의 경로를 찾기 위한 함수 문제풀이n값을 입력 받고, n개의 날에 가진 떡을 입력 받아 ..

리뷰 https://www.acmicpc.net/problem/6248점심시간에 부랴부랴 푼 기본적인 다익스트라 문제 전역 변수N : 배열의 최대 개수를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수x : 중심 노드의 번호를 저장할 변수Edge : 간선 정보를 정의할 구조체edges : 인접 리스트를 저장할 Edge타입 벡터 배열Pos : 현재 위치와 누적 가중치를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra(){ priority_queue pq; pq.push( { x, 0 } ); vector dist( n + 1, 2e9 ); dist[ x ] = 0; while ( !pq.empty() ) { co..

리뷰 https://www.acmicpc.net/problem/12980오랜만에 풀어본 쉽고 재미있는 백트래킹 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 순열의 크기를 저장할 변수s : 목표 점수를 저장할 변수ans : 목표 점수와 일치하는 순열의 개수를 저장할 변수arr : 칠판에 적혀있는 순열 정보를 저장할 정수형 배열visit : 숫자를 사용했는지 여부를 저장할 논리형 배열can_use : 0에 들어올 수 있는 숫자를 저장할 정수형 벡터 함수1. Printvoid Print( int cnt, vector& maked ){ for ( int d : maked ) { cout 디버깅용 함수 2. BackTrackingvoid BackTracking( int level, int..

리뷰 https://www.acmicpc.net/problem/32644오랜만에 풀어본 세그먼트 트리 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 문제를 푼 회원수를 저장할 변수m : 당첨 인원수를 저장할 변수arr : 각 회원의 가중치를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build( int node, int s, int e ){ if ( s == e ) tree[ node ] = arr[ s ]; else { int mid = ( s + e ) / 2; build( node * 2, s, mid ); build( node * 2 + 1, mid + 1, e ); tree[ node ] = tree[ node * 2 ] +..

리뷰 https://www.acmicpc.net/problem/14588간만에 풀어본 플로이드 와샬 문제, 재미있었다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수q : 쿼리의 개수를 저장할 변수pos : 각 노드의 x좌표 범위를 저장할 변수dist : 각 노드간 거리를 저장할 2차원 정수 배열 함수1. Initvoid Init(){ for ( int i = 0; i > l >> r; pos[ i ] = { l, r }; } for ( int i = 0; i 입력 및 초기화를 담당하는 함수 2. FloydWarshallvoid FloydWarshall(){ for ( int k = 0; k 플로이드 와샬을 통해 노드간 최단 거리를 구하기 위한 함수 문제풀..

리뷰 https://www.acmicpc.net/problem/34949N번 노드에서 모든 노드까지의 거리를 구하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수dist : n번 노드에서 모든 노드까지의 거리를 저장할 배열edges : 간선 정보를 저장할 정수형 벡터 배열 함수1. bfsvoid bfs(){ queue q; q.push( n ); dist[ n ] = 0; while ( !q.empty() ) { int cn = q.front(); q.pop(); for ( int nn : edges[ cn ] ) { if ( dist[ nn ] != -1 ) continue; dist[ nn ] = dist[ cn ] + 1; q.pu..

리뷰 https://www.acmicpc.net/problem/14907오랜만에 풀어본 위상 정렬 + 파싱 문제, 재미있었다. 전역 변수cnt : 자신에게 들어오는 간선의 개수를 저장할 해시맵weights : 자신의 가중치를 저장할 해시맵pre_sum : 자신에게 누적된 가중치의 최대값을 저장할 해시맵edges : 자신으로 부터 갈 수 있는 노드를 저장한 인접 리스트 해시맵 함수1. Splitvector Split(const string& s){ stringstream ss( s ); vector args; string temp = ""; while ( getline( ss, temp, ' ' ) ) args.push_back( temp ); return args;} 개행문자를 기준으로 문자열을 입..

리뷰 https://www.acmicpc.net/problem/30470스택 문제를 푸려고 들어왔는데 시간초과를 맞고 빨리 풀기 위해 Map으로 돌렸다. 전역 변수n : 쿼리의 개수를 저장할 변수dic : 현재 통나무의 길이별 개수를 저장할 map 함수없음 문제풀이n값을 입력 받고, n번의 쿼리를 수행한다.매 쿼리마다 변수 op, v에 쿼리 정보를 입력 받는다.op가 1인 경우 dic[v]를 1만큼 증가시킨다.op가 2인 경우 dic이 빈 상태라면 continue처리한다.변수 b에 dic에서 가장 큰 key값을 저장한다.변수 t를 b-v와 0중 더 큰 값으로 저장한다.만약 t가 0인경우 dic을 clear처리하고, continue처리한다.변수 it에 dic에서 t를 기준으로 upper_bound한 이..

리뷰 https://www.acmicpc.net/problem/30702국기 A의 인접한 색을 모두 새로운색으로 칠해 국기 B와 동일하게 만들 수 있는지 여부를 구하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n, m : 국기의 세로/가로 크기를 저장할 변수A, B : 국기 A, B의 색 정보를 저장할 2차원 배열v : 국기 A의 방문 여부를 저장할 2차원 배열dx, dy : 4방향 탐색을 위한 방향 배열Pos : 현재 위치 정보를 정의할 구조체 함수1. Inputvoid Input(){ cin >> n >> m; for ( int i = 0; i > A[ i ][ j ]; } } for ( int i = 0; i > B[ i ][ j ]; } }} 모든 입력을 처리해 정의한 자료구..

리뷰 https://www.acmicpc.net/problem/6195회사에서 촉박하게 풀려니 잘 안풀렸다가 집에 오니 어떻게 풀어야 할지 생각이 났다. 전역 변수n : 만들어야 할 나무 판자의 개수를 저장할 변수pq : 만들어야 할 나무 판자의 길이를 저장할 우선순위 큐 함수없음 문제풀이n값을 입력 받고, n개의 만들어야 할 나무 판자의 길이를 입력 받아 pq에 push한다.변수 ans를 0으로 초기화한다.pq의 크기가 1보다 클 때를 조건으로 하는 while루프를 수행한다.변수 s1, s2에 pq의 top요소를 두개 뽑아 저장한다,변수 sum에 s1 + s2를 저장하고, ans에 sum을 더해준 뒤 pq에 sum을 삽입한다.while루프가 종료된 후 ans에 저장된 값을 출력한다. 트러블 슈팅pq..

리뷰 https://www.acmicpc.net/problem/25603회사 점심시간에 풀다가 틀렸는데 왜 자꾸 틀렸는지 고민했다가 집에 오자마자 맞췄다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 기업 의뢰의 비용의 개수를 저장할 변수k : 스킵할 수 있는 비용의 최대 개수를 저장할 변수 함수없음 문제풀이n, k값을 입력 받고, 변수 mn을 0으로 초기화한다.n개의 의뢰 비용을 입력 받아 arr배열을 초기화 하고, 그 중 최대값을 mn에 저장한다.변수 l을 1, r을 mn, ans를 mn으로 초기화한다.l이 r이하일 경우를 조건으로 하는 while루프를 수행한다.변수 mid를 (l+r)을 2로 나눈 몫으로 저장하고, cnt를 0으로 초기화한다.arr을 순회하며, 현재 값이 mid보다..

리뷰 https://www.acmicpc.net/problem/15918좀 더 예쁘게 풀 수 있었을 것 같은데 풀다보니 너무 지저분해졌다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 자연수의 개수를 저장할 변수x, y : 이미 주어진 같은 수여야 하는 두 인덱스를 저장할 변수uc : 사용한 자연수의 개수를 저장할 변수ans : 완성된 랭퍼드 수열의 개수를 저장할 변수used : 이미 사용한 자연수를 체크하기 위한 배열arr : 랭퍼드 수열 정보를 저장할 배열 함수1. btvoid bt( int level ){ if ( level > 2 * n ) return; for ( int i = 1; i 2 * n ) continue; if ( arr[ level + i + 1 ] ) ..

리뷰 https://www.acmicpc.net/problem/20924쉽게 보고 접근했던 문제인데 생각보다 처리해줘야 할 것이 많았다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수r : 루트 노드의 번호를 저장할 변수mn : 기가 노드 번호를 저장할 변수mpn : 기가 노드의 부모 노드 번호를 저장할 변수r_to_m : 루트부터 기가 노드까지의 거리를 저장할 변수mx_dist : 기가 노드로부터 리프 노드까지의 거리 최대값을 저장할 변수edges : 간선 정보를 저장할 pii타입 벡터 배열 함수1. FindMiddleNodeAndDistvoid FindMiddleNodeAndDist( int cn, int pn, int dist ){ if ( edges[ c..

리뷰 https://www.acmicpc.net/problem/3803최근에 회사 내부 코드 컨벤션을 지키기 위해 노력하고 있다, 따라서 집에서도 로컬의 VS를 서식을 변경하였다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수nodes : 현재 노드가 속한 그룹의 번호를 저장하기 위한 배열n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체, 가중치를 기준으로 오름차순 정렬한다.edges : 간선 정보를 저장할 Edge타입 벡터 함수1. Findint Find( int a ){ if ( nodes[ a ] == a ) return a; return nodes[ a ] = Find( nodes[ a ] );} 현재 노드가 속한 그룹의 번호를 반환..

리뷰https://www.acmicpc.net/problem/13905최대값의 최소를 구하는 스패닝 트리 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수sn : 시작 노드의 번호를 저장할 변수en : 도착 노드의 번호를 저장할 변수Edge : 간선 정보를 정의할 구조체, 가중치를 기준으로 내림차순 정렬한다.edges : 간선 정보를 저장할 Edge타입 벡터nodes : 각 노드가 속한 그룹의 번호를 저장할 배열 함수1. Findint Find( int a ) { if (nodes[a] == a) return a; return nodes[a] = Find( nodes[a] );} 노드가 속한 그룹의 번호를 찾고, 경로 압축을 수행..

리뷰 https://www.acmicpc.net/problem/23843충전에 필요한 시간을 내림차순으로 정렬하고, m개의 0을 가진 pq를 오름차순으로 정렬하여 가장 큰 수를 구하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 전자기기의 개수를 저장할 변수m : 콘센트의 개수를 저장할 변수arr : 전자기기의 충전 시간을 저장할 1차원 정수 배열 함수없음 문제풀이n, m값을 입력 받고, n개의 전자제품의 충전에 필요한 시간을 입력 받아 arr배열을 초기화한다.sort함수를 통해 arr배열을 내림차순으로 정렬한다.최소힙의 성질을 가진 정수형 우선순위 큐 pq를 초기화하고, pq에 m개의 0을 push해준다.배열 arr을 순회하며 변수 d에 현재 전자기기의 충전 시간을 저장한다.변수..

리뷰 https://www.acmicpc.net/problem/1833엄청 오랜만에 풀어본 MST문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수arr : 간선 설치 비용을 저장할 2차원 정수 배열node : 집합 정보를 저장할 정수형 배열n : 노드의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체, 가중치를 기준으로 오름차순 정렬한다. 함수1. Findint Find(int a) { if (node[a] == a) return a; return node[a] = Find(node[a]);} 노드가 속한 그룹의 번호를 반환하고, 경로 압축을 수행하기 위한 함수 2. Unionbool Union(int a, int b) { int A = Find(a); int B = Find(b); ..

리뷰 https://www.acmicpc.net/problem/17952스택을 활용해 과제의 최고점을 구하는 문제 전역 변수n : 이번 학기가 몇 분인지를 저장할 변수stack : 스택으로 사용할 pair타입 벡터 함수없음 문제풀이n값을 입력 받고, 변수 sun을 0으로 초기화한다.n번의 for문을 개행하고, 매 루프마다 변수 op를 초기화 하고, 값을 입력 받는다.만약 op가 1이라면 변수 a, t를 초기화 하고, 값을 입력 받는다.만약 t가 1이라면 sum에 a를 더해준다, 아니라면 stack에 {a, --t}를 push한다.op가 0이라면 stack이 비지 않았고, stack의 back의 second를 전위감소 시켜준다.감소 후 stack의 back의 second가 0일 경우 sum에 stack..

리뷰 https://www.acmicpc.net/problem/14217그냥 BFS를 q번 돌렸더니 시간이 어마어마하게 나왔다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 정점의 개수를 저장할 변수m : 간선의 개수를 저장할 변수edges : 인접 리스트를 저장할 정수타입 unordered_set 배열Pos : 현재 노드 번호와 누적 거리를 정의할 구조체 함수1. bfsvoid bfs() { queue ps; ps.push({ 1, 0 }); vector dist(n + 1, -1); dist[1] = 0; while (!ps.empty()) { auto [cn, ct] = ps.front(); ps.pop(); for (int nn : edges[cn]) { if (dist[n..