https://www.acmicpc.net/problem/9663 백트레킹 문제이다.어렵고 까다롭지만 좋은 문제라서 따로 정리해두려고한다.더 좋은 풀이는 https://cryptosalamander.tistory.com/58 이분의 풀이를 추천드린다. 풀이 흐름해당문제는 일단 하나의 row에 하나의 퀸만 배치할 수 있다는 것을 전재로 두는게 좋다.탐색 자체는 현재 row(행)의 특정 col(열)에 퀸을 배치할 수 있는지 없는지를 판단할 것이다.현재 row라는 값이 필요하기 때문에 탐색할 때 param으로 현재 현재 ‘row’를 받아와야한다.row의 특정 col에 조건을 따져 배치할 수 있다면 배치하고 그렇지 않다면 되돌아 가준다.계속 배치를 하다가 row가 n과 같다면 한 row당 하나의 퀸을 배치한 것..

https://www.acmicpc.net/problem/1948 후기TopologySort + 탐색(DFS, BFS)가 같이 들어가 조금 어려웠던 문제 입니다.일단 문제를 읽고 위상정렬이라는 것 자체를 떠올리기가 힘들었고 역으로 1분도 쉬지 않고 달려야하는 경로를 찾는부분도 해맸던 문제입니다.해설먼저 문제의 조건에서 사이클이 없다는 것과 가장 마지막에 도착하는 사람이 있다는 것을 기반으로 위상정렬 아이디어를 떠올려서 가장 마지막에 도착하는 사람의 도착시간을 구해줍니다.(저는 스타크래프트 배럭과 벙커를 예시로 생각했습니다... 벙커를 지을려면 배럭을 먼저 지어야 하는 식의 예시)이후 도착점으로 부터 출발지 까지 역으로 DFS든 BFS로든 탐색을 해주는데'다음으로 갈 노드의 결과 값' == '현재 결과값 ..

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 후기 조금 어려웠던점 점은 원본 상태에 대한 상태를 변경해야한다는 부분을 어떻게 처리할 줄 몰랐었습니다. 기존의 조금 까다롭다고 생각되는 문제들은 2차원 배열을 탐색하는 것이 아니라 값 자체를 탐색하는것에 추가적으로 특정 상태를 기억한다음에 탐색을 이어 가는데 해당 문제는 이 두가지 가 모두 포함된 상태에서 탐색을 하는 대상자체와 방문 표시를 하는 부분에 대한 신경도 썻어야 하는 문제입니다. 풀이 "103425786"에 대한 상태를 문자열로 관리를 해줍니다. '0'이 있는 ..

https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 순열 + DP문제입니다. 순열은 nPr이고 n개 중에 r개를 뽑는데 순서를 고려하여 뽑는 경우를 뜻합니다.(사전순 정렬) 문제의 입력 최대값이 20이므로 O(20!)을 가지기에 next_permutation을 사용하면 무조건 시간초과로 틀리기 때문에 시간 복잡도를 줄이기 위해 고민이 필요한 문제인거 같습니다. 풀이순서 1. 먼저 입력조건에 따라 입력을 받는다. 2. ..

문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net BFS, DFS, MST 개념이 다 들어간 문제이고 단계적으로 풀이하여 문제에서 요구하는 바를 구현할 수 있는지가 중요한듯 합니다. 풀이순서 1. 입력으로 받은 데이터의 섬마다 번호를 매겨준다. (BFS 사용) 2. 상하좌우로 각 섬마다 연결될 수 있는 다리가 있는지 탐색하고 연결이 가능하면 경로에 추가한다. (DFS 사용) 3. 추가된 경로들을 가지고 최단거리를 구한다..

25206번: 너의 평점은 (acmicpc.net) 25206번: 너의 평점은 인하대학교 컴퓨터공학과를 졸업하기 위해서는, 전공평점이 3.3 이상이거나 졸업고사를 통과해야 한다. 그런데 아뿔싸, 치훈이는 깜빡하고 졸업고사를 응시하지 않았다는 사실을 깨달았다! 치 www.acmicpc.net 일단 문제를 잘 읽어야 한다는 것을 다시한번 느끼게 되었습니다. 현재 학교를 다니는데 학교 평점이 이렇게 계산되는지는 몰랐네요...;; 핵심은 "전공평점은 전공과목별 (학점 × 과목평점)의 합을 학점의 총합으로 나눈 값이다." 이부분인거같습니다. 저는 map 이진 탐색트리인 레드블랙트리를 통해서 학점에 따른 점수를 구할 수 있도록 하였습니다. P라면 continue 해주어야 겠지요. 또한 double타입으로 수를 더해..

https://www.acmicpc.net/problem/10811 10811번: 바구니 뒤집기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2 www.acmicpc.net 쉬운 문제이지만 reverse의 기능과 vector와 같은 container의 iterator가 무엇인지 모른다면 풀기가 어려워 보이는 문제입니다. 저도 처음에 조금 돌다가 풀었습니다. reverse()에는 vecotr와 같은 container객체의 iterator를 넣을 수 있습니다. iterator는 vector 객체의 주소를 가르켜주는 "도구"의 느낌으로 저는 생각하고있습니다. 따라서..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 후기 먼가 짝을 짓는거 같긴해서 stack을 잠깐 생각은 했지만 아닌거 같아서 pass... 이런식으로 표를 그려서 2시간정도 이리저리 생각을 해보았지만 아이디어가 떠오르지를 않았습니다. 물론 떠오른 아이디어는 있었습니다. 이중 for문으로 돌리면 가능하지만 시간복잡도상 사람수가 50만이라 50 * 50만이 되면 절대 풀 수 없다고 생각해서 - 구조체안에 이전 데이터를 넣어..