개인사

리뷰 처음엔 정수를 활용하여 풀려고 했으나 로직짜는게 너무 더러워 질 것 같아서 문자열을 택했다.https://www.acmicpc.net/problem/1327 문제 풀이전역 변수n, k : 정수형 변수이다. 수열의 길이 n, 뒤집는 개수 kinput, s, e : 문자열 변수이다. 수열을 입력 받을 input, 최초 수열의 상태 s, 목표 수열의 상태 ev : 해시를 통한 방문처리를 진행할 unordered_map, 타입으로 초기화 해주었다.Now : BFS를 돌릴때 사용할 구조체, 현재 수열을 나타낼 문자열 cur과 뒤집은 횟수 정수t로 이루어져 있다. 함수1. Reversestring Reverse(string num, int index) 현재 문자열을 입력 받고, index부터 index + ..

리뷰 느리게 갱신되는 세그먼트 트리의 기초 문제, 쿼리가 구간합이 아닌 특정 인덱스를 출력하는 문제이다.https://www.acmicpc.net/problem/16975 문제 풀이전역 변수MAX_N : 노드의 최대 개수를 지정할 상수 변수, 10만으로 초기화 한다.nodes : 수열의 정보를 저장할 배열, 크기는 MAX_N으로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4로 초기화 한다.lazy : 느린 업데이트 정보를 저장할 배열, 크기는 MAX_N * 4로 초기화 한다.n, m : 수열의 크기 n, 쿼리의 개수 m을 저장할 변수 함수1. buildvoid build(ll node, ll start, ll end) nodes 수열을 갖고 tree배열에 세그먼트 ..

리뷰 lazy propagate를 배우고 처음으로 문제에 접목해 봤다, 함수 구현보단 정수형 타입때문에 애를 좀 먹었다.https://www.acmicpc.net/problem/10999 문제 풀이전역변수MAX_N : 배열의 크기를 초기화 할 상수형 long long타입 변수nodes : 수열의 정보를 받아 저장할 배열 크기는 MAX_N으로 초기화tree : 세그먼트 트리 정보를 저장할 배열 크기는 MAX_N * 4로 초기화lazy : 업데이트 갱신용 트리 정보, tree와 같은 구조를 가진다.n, m, k : 수열의 길이를 나타낼 n, 업데이트 쿼리의 개수 m, 구간합 출력 쿼리의 개수 k함수1. buildvoid build(ll node, ll start, ll end) 세그먼트 트리를 빌드해 준다...

리뷰 세그먼트 트리를 통해 수열의 특정 구간의 첫번째 최대값과 두번째 최대값을 구하고 그 합을 구해 출력하는 문제https://www.acmicpc.net/problem/17408 문제 풀이전역 변수MAX_N : 노드의 최대 개수 10만을 상수형 정수타입으로 설정해 준다.nodes : 수열의 정보를 담을 배열, 크기는 MAX_N으로 설정한다.tree : 최대값과 인덱스를 담을 정수형 pair 배열, 크기는 MAX_N * 4로 설정한다.n, m : 노드의 개수 및 쿼리의 개수 정보를 담을 변수 함수1. 최대값을 갖는 세그먼트 트리를 만드는 함수 void build(int node, int start, int end) 리프 노드 도달 시 배열의 값과 인덱스를 저장해 준다.이후 탐색을 통해 위로 올려주며 각 ..

리뷰 2048게임을 구현하는 문제, 시뮬레이션만 잘 작성하면 쉽게 풀 수 있으나 문제를 잘 읽어보아야 할듯 하다.https://www.acmicpc.net/problem/12100 문제 풀이전역 변수n : 맵의 행, 열을 저장할 변수ans : 최대값을 저장하기 위한 변수map : 맵 정보를 입력받을 2차원 정수형 벡터 n값을 입력 받고 map을 n * n크기로 초기화 해준 뒤 맵의 정보을 입력 받아준다.dfs를 통해 상하좌우로 미는 작업을 완전 탐색으로 구현해 준다, 매개변수는 시도한 횟수 level과 맵을 참조한다.기저 조건으로 level이 5에 도달하면 5번 작업을 한 상태이므로 맵을 체크하여 최대 값을 갱신해 준다.4방향으로 탐색을 하며 상하좌우로 맵을 미는 작업을 한 후에 재귀를 실행해 준다.이때..

리뷰 알고리즘 분류에 다이나믹 프로그래밍이 있어 혼란이 왔었는데 DFS로도 충분히 AC가 가능한 문제였다.https://www.acmicpc.net/problem/15681 문제 풀이전역 변수n, r, q : 노드의 개수 n, 루트 노드 r, 쿼리의 개수qdp : 각 노드가 루트인 서브트리에서의 하위 노드의 개수(자신을 포함한다.)v : DFS 내부에서 사용할 방문처리 배열, 최대 노드의 개수보다 크게 설정해 준다.path : 인접 리스트를 저장할 정수형 벡터 배열, 최대 노드의 개수보다 크게 설정해 준다. n, r, q를 각각 입력 받아주고, dp를 n + 1크기로, 기본값은 자기 자신을 포함하기 위해 1로 세팅해 준다.n - 1개의 간선 정보를 입력 받아 양방향 인접 리스트를 생성해 준다.루트를 방문..

리뷰 문제를 제대로 읽지 않아 대각선까지 일치해야 하는줄 알았다.처음엔 해쉬 + Find를 통해 풀어야 하나 고민했는데 깊게 생각하지 않고 열, 행, 그룹으로 방문처리 하며 재귀를 사용하면 된다. 너무 어렵게 생각하지 말자https://www.acmicpc.net/problem/2239 문제 풀이전역 변수lst : 맵 정보를 나타낼 정수형 2차 배열cnt : 맵에 남아있는 0의 개수를 체크할 변수flag : 스도쿠 퍼즐이 완성되었는지 체크할 변수cols : 현재 행 기준 모든 열의 방문처리를 체크할 정수형 2차 배열rows : 현재 열 기준 모든 행의 방문처리를 체크할 정수형 2차 배열groups : 3*3 크기의 그룹 내의 방문처리를 체크할 정수형 3차 배열 9 * 9 크기의 for문을 개행해 준다 처..

리뷰 다른 MST 문제와는 다르게 모든 간선을 구하는 것이 아닌 필요한 간선만 구해 MST를 구하는 문제기존의 모든 간선을 구하는 방식을 사용했더니 바로 메모리 초과가 출력되었다.https://www.acmicpc.net/problem/2887 문제 풀이전역 변수n : 행성의 개수를 저장할 변수nodes : Union-Find를 통해 MST를 구할 노드의 배열, 노드의 최대 크기인 10만보다 1크게 설정해 준다.Pos : 행성의 각 축 좌표 위치 정보를 나타낼 구조체, sort가 필요하므로 compare함수를 작성해 준다.Edge : 행성간 간선의 정보를 나타낼 구조체, 마찬가지로 sort가 필요하다.PI : x, y, z축과 행성의 번호를 저장할 Pos타입 벡터n값을 입력 받고, 1 ~ n까지 행성 정..

리뷰 설계를 하지 않고 무작정 덤볐다가 호되게 당한 문제, 구현과 시뮬레이션은 둘째치고 생각 못하고 있던 조건들이 많아서 애를 먹었다, 해당 문제를 풀기 전에 문제에 대한 조건을 한번 쭉 정리하는걸 추천한다.https://www.acmicpc.net/problem/13460 문제 풀이전역변수n, m : 2차원 맵 상 행과 열의 크기를 저장할 변수sx1, sy1, sx2, sy2 : 빨간색 구슬과 파란색 구슬의 x, y좌표를 저장할 변수lst : 맵 정보를 저장할 문자열 배열, 최대 크기가 10이므로 10만큼의 크기를 지정해 주었다.v : 방문 처리를 할 4차원 정수 배열, 각각의 요소에 sx1, sy1, sx2, sy2의 위치 저장, 맵의 크가보다 1크게 초기화dx, dy : 4방향 탐색을 위한 방향 배..

리뷰 일반적인 BFS를 사용하니 바로 시간 초과가 출력되었다!!벽을 의미하는 1을 보기 보단, 0부터 본 후에 1을 체크하는 방식이 효율적인 문제였다. 위에서부터 차례대로 group정보를 배열, 벡터, unordered_map을 사용하여 관리한 정보이다.배열이 시간은 가장 빠르고 벡터가 메모리 낭비가 덜 심하고 해시는 그닥 효율이 좋지 못했다.따라서 해당 문제는 벡터를 활용한 방법으로 설명하겠다.https://www.acmicpc.net/problem/16946 문제 풀이전역변수lst : 맵을 저장할 문자열 벡터group : 그룹의 면적을 저장할 벡터, 인덱싱을 위해 크기를 1을 가진 상태로 시작한다.groups : 그룹의 면적을 2D맵에 나타내기 위한 배열v : 방문을 체크하기 위한 배열, 사실상 gr..