개발 노트

SW마에스트로 합격을 위해 최근 열심히 코딩 테스트를 준비하고 있다. 열심히 코테를 위한 뇌를 깨우고 있던 중, 첫 번째 난관에 봉착했다. 꽤나 오랜 시간을 투자한 만큼 더이상 삽질하지 말자는 의미에서, 기존 내가 설계했던 방식에 대한 짧은 소개와 문제점, 그리고 올바른 풀이를 설명하고자 한다. 이번 문제에서는 아이디어만큼 내가 여기서 겪었던 실패와 성공의 경험 역시 중요하다고 생각해 전반적인 흐름을 작성하였으니, 하나의 이야기를 보는 느낌으로 편하게 봐 주시면 될 것 같다. 문제 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호..

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

next_permutation은 C++ STL의 헤더에서 제공하며 순열과 조합을 구할 때 유용하게 사용 가능한 함수이다. 순열과 조합 순열 : 서로 다른 n개의 원소에서 r개를 선택한 후, 이를 나열하는 모든 경우의 수. 기호로는 n​Pr 이라고 나타내며, 이 때의 P는 영어 permutation의 약자이다. 특정 원소를 ​뽑은 후 이를 '나열'하는 경우의 수이기 때문에, 뽑힌 원소의 순서까지도 고려가 된다. 예를 들어 {1, 2}와 {2, 1}은 같은 원소를 선택하였으나 순서가 다르기에, 둘은 다른 순열이 된다. {1, 2, 3}으로 만들 수 있는 순열은 다음과 같다. {1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1} 총 6개의 경우의 수가 존재..

기존 백트래킹으로 풀었던 문제를 C++의 STL 중 하나인 next_permutation을 이용해 풀이해 보았다. 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이에 사용되는 next_permutation에 대해 정리한 링크이다. https://taehun0933.tistory.com/18 [알고리즘] next_permutation - 순열과 조합 / C++ next_permutation은 C++ STL의 헤더에서 제공하며 순열과 조..

처음으로 시뮬레이션 문제를 풀었다. 처음에는 막막했지만 하나하나 생각해본 대로 구현해보는 과정이 재밌기도 했고, 문제를 풀고 난 뒤 다른 풀이를 알아보고 코드를 최적화하는 과정에서 여럿 깨달은 점이 있어 이를 정리해보았다. (여러 삽질 과정도 함께) 문제 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 형..