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. 추가된 경로들을 가지고 최단거리를 구한다..

https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 이번글은 백준사이트의 중앙값 구하기에 대한 설명입니다. 먼저 평균값과 중앙값은 다릅니다. 1 2 3 4 5가 있을 때 평균은 1+2+3+4+5 / 5 가 평균값이고 중앙값은 말 그대로 1~5사이에 있는 딱 중앙에 있는 값을 의미합니다. 그리고 우선 시간제한이 1초라는점과 입력값의 최대치를 확인해줍니다. TC가 1000이고 하나의 TC에 대한 M의 입력이 9999입니다...

이번글은 Minimum cost Spanning Tree 줄여서 MST인 '최소 비용 신장 트리'에 대한 글입니다. 먼저 MST가 무엇인지 알아보기 전에 '경로(Path)'가 무엇인지 알아보도록 하겠습니다. 경로(path) ''경로(path)'란? 특정 그래프에서 정점과 정점을 잇는 간선을 순서대로 나열한 것을 의미합니다. 그리고 동일한 간선(edge)를 중복하여 포함하지 않는 경로를 '단순 경로(simple path)'라고합니다. 이런 그래프가 있을 때 정점 A에서 C까지 이르는 경로는 A-B-C. A-D-C, A-B-D-C, A-D-B-C 정도가 있겠군요. 단순경로가 아닌 경우에는 이를테면 A-D-B-A-B-C 같은 경우가 있습니다. 최소 비용 신장 트리 A-B-D-A의 경우에는 단순경로입니다. 위에..

이번글은 BFS에 대한 글입니다! 그래프와 BFS란? 그래프란 정점과 간선으로 이루어진 자료구조입니다. 실생활에서도 많이 쓰이기 때문에 그래프는 중요한 개념입니다. 종류로는 "무방향 그래프", "완전 그래프", "가중치 그래프" 등등 종류가 많습니다. 그래서 탐색하는 방법이 그래프 구현에 따라 달라집니다. 그럼에도 불구하고 그래프의 모든 정점을 탐색하는 그래프가 대표적으로 아래 두가지가 있습니다. - DFS : Depth First Search - BFS : Breadth First Search 이중에서도 BFS를 구현하는 방법을 알려드리도록 하겠습니다. 일단 그래프를 탐색하려면 그래프가 있어야겠죠? 그래프를 구현하는 대표적인 방법두가지를 알려드리도록 하겠습니다. - 인접 리스트를 통한 그래프 구현 =>..