개발 노트

문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 아이디어 1) 조합을 이용하여 7개의 좌표 선택 2) BFS를 이용하여, 선택한 좌표가 서로 연결되어 있는지 확인 3) 만약 연결되어 있을 시에는, 연결된 좌표들의 'S'의 개수와 'Y'의 개수 비교 처음에는 1)과 같이 조합을 이용하지 않고 백트래킹을 이용하여, 영역을 넓혀 나가며 좌표를 선택하다가 7개 모두 선택 시 2)와 3)의 과정을 수행하였다. 그러나 백트래킹으로는 십자 모양과 같이 두..

처음으로 시뮬레이션 문제를 풀었다. 처음에는 막막했지만 하나하나 생각해본 대로 구현해보는 과정이 재밌기도 했고, 문제를 풀고 난 뒤 다른 풀이를 알아보고 코드를 최적화하는 과정에서 여럿 깨달은 점이 있어 이를 정리해보았다. (여러 삽질 과정도 함께) 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 아이디어 - 1 최대 8개까지 존재할 수 있는 cctv는 4가지 방향을 가지기 때문에, 모든 경우의 수를 계산한 후 사각지대의 최솟값..

최근 map, pair, unique와 erase, 그리고 사용자 지정 정렬에 대해 배웠다. 이번 18870번 : 좌표 압축 문제가 해당 개념들을 활용하기 좋은 문제 같아, 해당 개념 및 문제에서의 활용법을 정리해보고자 한다. 문제 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 아이디어 1 : map 일단 map 형태가 가장 먼저 떠올랐다. key - value 형태로 이루어져 있는 map 형..