개인사

리뷰 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..

리뷰 다각형의 면적을 구하는 방법은 또 처음 알았다! 슈메르카우스키의 공식... 이세상엔 천재가 많다.덕분에 좌표 평면상에서의 다각형의 공식을 구하는 방법은 잊지 않을 것 같다!https://www.acmicpc.net/problem/2166 문제 풀이꼭지점의 개수 n과, 정답용 변수 ans, 좌표 구조체 Pos와 그의 배열 poses를 전역 변수로 세팅한다.n값을 입력 받고 n개의 꼭지점 좌표를 받아와 poses배열에 추가해 준다.n - 1번째 까지의 꼭지점을 탐색하며 xi*yi+1 - yi*xi+1 을 구해준 뒤 ans에 더해준다.최종적으로 0번째와 n - 1번째 인덱스의 꼭지점을 처리해 준 뒤 ans를 2로 나누어 준다.ans에 절댓값을 씌운 뒤 소숫점 1자리까지 반올림하여 출력해 주면 된다.  참..

리뷰경로 상에 신호등이 있어 기다렸다가 움직여야 하는 최단 경로 문제, 다른 문제와 다른점은 신호등의 방향이 정해져 있어 교차로에 진입하는 경우를 잘 분배해 주어야 했다.https://www.acmicpc.net/problem/1400 문제 풀이행 범위n, 열 범위 m, 시작 좌표 sx, sy 도착 좌표 ex, ey, 방향 배열, 맵 정보 lst배열을 전역 변수로 세팅한다.우선 순위 큐에서 사용할 Pos구조체를 정의하고, compare함수도 넣어준다.신호등 정보를 받을 구조체 Light를 정의하고, 신호등 배열 lights를 60크기로 설정해 준다.main함수에서 무한루프를 실행하고 input함수에서 n, m이 0, 0이라면 while루프를 종료해 준다.input함수를 통해 n, m값을 받고 만약 n과 ..

리뷰 구현이 생각보다 빡세서 많이 애먹었다.. 4달 전에도 못풀었지만 4달이 지난 후에도 애를 먹은 문제 ㅠㅠ대신 멀티셋이라는 새로운 STL을 접하게 된 계기가 되었다.https://www.acmicpc.net/problem/7662 문제 풀이각 테스트 케이스마다 쿼리의 개수 k를 입력받고, 정수형 멀티셋 dic을 초기화 해준다.각 쿼리마다 I또는 D값이 입력되므로 해당 값을 문자 타입 order 변수에 입력 받는다.추가로 order 뒤에는 항상 정수 값이 입력되므로 정수형 변수 n에 값을 입력 받는다.order가 I인 경우 dic에 n을 insert 해준다.order가 D인 경우 dic이 비어있으면 continue, 아니라면 최대 최소에 따라 dic의 end와 begin을 erase 해준다.모든 쿼리에..

리뷰 가수의 출연 순서를 구하는 위상 정렬 문제, 보조PD 라는 것에 의미를 부여하는 함정에 빠지면 안된다.https://www.acmicpc.net/problem/2623 문제 풀이가수의 개수n, 보조 PD의 개수m, 인접리스트용 벡터 path를 전역변수로 설정해 준다.n과 m값을 입력 받고, m크기만큼의 루프를 돌려준다, 이후 가수의 개수 a와 가수 b를 입력 받아준다.가수의 개수를 전위 감소 연산을 통해 while루프를 돌려주고 그 이후의 가수 c를 입력 받아준다.b의 path에 c를 push_back을 해준 뒤 b를 c로 교체시켜 준다. 이후 계속 반복해 준다.위 작업을 통해 가수의 순서대로 우선 순위가 적용되어 가수간의 출연 순서가 만들어 진다.cnt벡터를 n + 1크기로, 값은 모두 0으로 초..