고인물을 지양하는 블로그

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은, 섬들을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서 www.acmicpc.net 입력은 0과 1로 주어진다. 1은 섬을 나타내고 0은 바다를 나타낸다. 2중 for loop로 입력 배열(visited)를 탐색하다 ..

금요일부터 가볍게 BFS/DFS 기초 문제들을 풀어보았다. 정답률이 높은 순으로 100026 적록색약, 2583 영역 구하기, 1926 그림, 7562 나이트의 이동 문제를 풀었는데 사실 큰 틀은 거의 똑같고, 문제에 따라 연결 요소, 연결 요소의 개수 등.. 의 차이가 있었을 뿐으로 거의 같은 문제들이었다. 2583번 영역 구하기의 경우 왼쪽 아래를 원점으로 카테시안 좌표계로 문제의 입력이 주어지는데, 배열에서 사용하는 좌표계의 그것과는 달라 머릿속에서 바로 떠오르지 않아 꽤나 곤욕스러웠다. 7562번의 경우 위 문제들과 마찬가지로 BFS를 이용했는데, 최단거리 문제로 접근했다. BFS를 수행하며 도착하는 위치마다 이동에 필요한 횟수를 업데이트 하는 방법으로 문제를 해결했다. #include #incl..

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()( www.acmicpc.net 결론부터 말하자면 첫 알고리즘은 실패했다. #include #define Pair pair using namespace std; int m..