꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/3045 3045번: 이중 연결 리스트 문제 창영이는 1학년 때 숙제로 했던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 드디어 자신이 원하던 기능이 있는 소스를 받게 되어서 매우 기뻤다. 상근이는 하�� www.acmicpc.net 블로그 방문하셨던 분이 질문주셨던 문제여서 풀어보기 시작했던 문제였습니다. 처음에는 제목만 보고 이중 연결 리스트만 구현하면 되는줄 알았는데 생각보다 많은 부분을 고려해야 풀 수 있었던 문제였습니다. 우선, 이중 연결 리스트가 어떤 식으로 삽입 삭제되는지 A 1 4 연산을 예시로 그림과 함께 설명드리겠습니다. 1. 1번 노드를 떼어내야하기 때문에 1번 노드의 다음 노드인 2번..

문제 링크입니다: https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 다리의 방향도 고려해야하기 때문에 생각보다 까다로운 시뮬레이션 문제였습니다. 코드를 깔끔하게 짠다고 노력했는데도 불구하고 상당히 지저분하기 때문에 주석을 최대한 꼼꼼하게 달았습니다. 알고리즘은 아래와 같습니다. 1. 섬으로 표기된 지역 즉, 1로 표시된 좌표를 모두 islands 벡터에 추가해줍니다. 2. islands 벡터에 있는 좌표를 순차적으로 확인하며..

문제 링크입니다: https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net N이 최대 10이고 팀을 구역별로 할당할 수 있는 선거구의 수는 최소 1개이기 때문에 최대 8 * 10! 의 경우의 수를 고려하면 되는 문제였습니다. (사실, 구역을 2분할하기 때문에 10! 보다 훨씬 적은 경우의 수를 고려합니다.) 같은 구역으로 할당된 선거구가 모두 연결되었는지 판단하기 위해 algorithm 헤더의 find 함수를 사용했으며 코드가 비교적 간단하기 때문에 나머지 설명은 생략하겠습..

문제 링크입니다: https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 난이도가 쉬운 시뮬레이션 문제였습니다. State 구조체를 선언하여 회전 연산의 정보를 저장하였고, 각 연산 정보에 인덱스를 부여하여 next_permutation을 사용하여 모든 경우의 수를 시뮬레이션 돌렸습니다. 각 인덱스에 담긴 정보는 map 자료구조를 사용하여 인덱스를 key, 연산 정보를 value로 저장하였고, 회전 연산은 이중 for문을..

문제 링크입니다: https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 쉬운 시뮬레이션 문제였습니다. 알고리즘은 아래와 같습니다. 1. Fish 구조체를 선언한 뒤 fishes 배열에 물고기 번호, 방향, 좌표를 입력합니다. 1.1 이 때, {0, 0} 좌표에 있는 물고기는 입력받지 않고 바로 상어로 변경해줍니다. 2. fishTank 배열 같은 경우 좌표를 통해 물고기 번호를 구하기 위해 선언한 배열입니다. 3. func 재귀함수..

문제 링크입니다: https://www.acmicpc.net/problem/19235 언제나처럼 삼성 코딩테스트는 수준 높은 독해력을 요구하는 시뮬레이션 문제를 출제하는 것 같습니다. 저는 초록색 칸과 파란색 칸을 각각 이차원 배열 green[6][4], blue[4][6]으로 선언하여 문제를 풀었습니다. 알고리즘은 아래와 같습니다. 1. 블록 타입과 좌표를 입력 받고 green과 blue 배열에 블록이 쌓인 칸을 표시해줍니다. 1.1 이 때, 타입마다 다르게 표시해줘야 합니다. ex) t=2 일 경우 배열에도 2라고 표시 2. 초록색 칸과 파란색 칸에 대해 시뮬레이션을 돌립니다. 2.1 초록색 칸에서 행, 파란색 칸에서 열이 가득 채워질 경우 블록을 만나거나 경계선에 맞닿을 때까지 옮겨주는 작업을 진행..

문제 링크입니다: https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 �� www.acmicpc.net 세그먼트 트리와 좌표압축을 활용해야하는 문제였습니다. 각 선수의 실력의 범위는 1 ~ 1,000,000,000 까지이지만 N이 최대 500,000이기 때문에 아래와 같은 알고리즘이 적용 가능합니다. 1. 구조체 벡터를 선언해 ability에는 실력, idx에는 인덱스를 저장해줍니다. 2. 실력 오름차순 정렬을 진행한 뒤, 실력을 [0, N-1) 로 압축해줍니다. 3. ..

문제 링크입니다: https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종� www.acmicpc.net 가장 많은 득점을 하는 타순을 찾기 위해 1번 선수부터 9번 선수까지의 모든 순열에 대해 시뮬레이션을 돌려야하는 문제였습니다. 문제 조건으로 1번 선수가 4번 타자가 되어야 하기 때문에 순열의 네 번째 인덱스가 0인지 확인한 뒤 시뮬레이션을 돌렸습니다. (v[0] == 3) 타순은 이닝이 변경되어도 순서를 유지해야하기 때문에 덱을 사용하여 현재 타석에 선 타자를 push_back 메..

문제 링크입니다: https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루� www.acmicpc.net DFS가 진행될 때 형제 노드들이 정렬이 되지 않은 상태에서 진행되므로 DFS 진행 순서를 기록하는 것이 중요합니다. 이후에는 각 노드에 연결된 노드들을 DFS 진행 순서를 기준으로 정렬을 한 뒤 DFS를 진행했을 때 순서가 같은지 여부를 판단해주면 되는 문제였습니다. 순서가 다를 경우 바로 프로그램을 종료하기 위해 exit(0) 문법을 사용..

문제 링크입니다: https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작�� www.acmicpc.net T 자 모양 같이 단순 DFS, BFS 알고리즘을 통해서는 도출해낼 수 없는 경우의 수가 있기 때문에 모든 경우의 수를 도출해낸 후 조건을 충족하는지 확인해야하는 문제였습니다. 5 * 5의 정사각형 격자 형태로 자리가 배치되어있고 여기서 7명을 뽑아야하므로 25C7 가지 즉, 480,700 가지의 경우의 수를 고려해보면 된다는 것을 알 수 있습니다. 따라서, 모든 경우의 수를 고..