본문 바로가기

분류 전체보기

 (236)
C++[백준]16724번 피리부는 사나이 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 솔루션 나는 DFS로 해결을 했다. 1) 각 방문 배열에 엄청 큰 값을 넣어주고, 2) 방문한 적이 없다면 특정 번호를 이용해 dfs를 수행한다. - 해당 인덱스에서 갈 수 있는 방향으로 계속해서 나아간다. - 만약 이미 방문한 배열이 나온다면 해당 값으로 바꿔준다. (방문배열이 이미 채워져 있다는 것은 무조건 특정 번호보다 낮은 값이다.) - 만약 더이상 진행..
C++[백준]2162번 선분 그룹 https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 솔루션 선분교차 판정 + 분리집합 으로 해결을 했다. 함수를 구현 할 것이 많아 귀찮은 문제. 1) for i 0 to N-1, for j i+1 to N 으로 이중 반복문을 통해서 i번째 입력으로 들어온 선분과 j번째 들어오는 선분이 교차하는지 판별한다. - 선분 교차 판정 알고리즘을 이용해 선분이 교차하는지 판단 (선분 교차 2를 참고) 2) 선분이 교차한다면..
C++[백준]3878번 점 분리 https://www.acmicpc.net/problem/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 솔루션 문제는 아주 직관적이여서 이해하기는 쉬웠으나, 구현에서 엄청난 시간을 잡았다. 아직 기하학은 너무 어렵다. 먼저 검은 점을 이용해여 볼록 껍질을 만들고, 흰 점을 이용해 볼록 껍질을 만든다. 그리고 다음과 같은 경우로 나눌 수 있다. 1. 둘 다 볼록 껍질을 이룰 경우 2. 하나만 볼록 껍질을 이루고 - 다른 하나는 선분 3. 하나만 볼록 껍질을 이루고 - 다른 하나는 점 4. 둘 다 선분을..
C++[백준]14750번 Jerry and Tom https://www.acmicpc.net/problem/14750 14750번: Jerry and Tom Your program is to read from standard input. The input starts with a line containing four integers, n, k, h, and m, where n(1 ≤ n ≤ 1,000) is the number of the corner points of a house, k(1 ≤ k ≤ 5) the maximum number of mice each hole can afford, www.acmicpc.net 솔루션 첫 시도가 7달 전이고, 최근에 들어서 다시 문제에 도전해서 맞췄다. 나는 이분 매칭 + 선분교차 판정으로 풀었다. 7달 전에..
RBT - (Red Black Tree) C++ 오랜만의 글... 요즘 백준도 못 풀고 정신 없이 지내는 중이다. 대학교 4학년이 되어서 '문제해결기법'을 듣는데, 과제로 RBT 구현이 나왔다. 일전에 백준에 functionx를 푸는 데 RBT를 쓰면 구현이 가능 할 것 같아 Insert만 구현 해 봤는데, 널 포인터를 참조하게 되어서 포기했다가 과제 때문에 RBT를 다 구현 해 보았다. 처음에 https://gowoonsori.com/data-structure/tree/redblacktree/ 이 글을 참고 하였다가, 과제에서 원하는 정해가 나오지 않아서, 수업 pdf의 그림을 보며 다시 짰다. case를 나누는 것이 까다로웠지만, 차근차근하니 이게 되네? 였다. 코드 내부에 궁금한 점이 있으시면 댓글을 적어주시면 설명하겠습니다. 코드 더보기 #pr..
C++[백준]9328번 열쇠 https://www.acmicpc.net/problem/9328 솔루션 구현 문제.. 시간이 상당히 걸렸다. 입력을 다 받고 가지고 있는 열쇠를 입력을 받는다. 열쇠를 가지고 있을 때 열 수 있는 모든 문을 다 연다. (이건 문자 하나마다 문을 전위 탐색하여 풀도록 함수화 하였다). 그리고 가장자리에서 들어올 수 있는 모든 지점에서 들어온다. 그리고 BFS를 돌리는데, 위에서 진행한 일을 반복해서 적으니 함수화 하는 것이 좋아 보인다. 해당 칸이 문서이면 갯수를 증가 시켜주고, 해당 칸이 열쇠라면 (위에 적은 함수) 전위 탐색하여 문을 열어준다. (이 때, 문이 새로 열렸으므로, 방문 배열 초기화 + 가장자리에서 들어오는 함수를 같이 실행 시켜준다.) 그리고 위, 아래, 좌, 우 탐색을 해 주면 된다...
C++[백준]16946번 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 솔루션 그래프 탐색으로 풀 수 있었다. 먼저 배열을 입력을 받고 전위 탐색을 통해 0을 만났을 때, 그 방의 번호를 메겨주었다. (0이 이루는 영역에 같은 번호를 부여) 그리고 영역의 총 개수를 리턴해 주고, 해당 방 번호에 다 같은 개수를 넣어주었다. (즉, bfs 2번 돌렸다.) 그리고 출력을 할 때, 1을 만나면, 4방위로 방 번호가 매겨진 것을 찾는다. 방번호를 알았으..
C++[백준]1509번 팰린드롬 분할 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 솔루션 다이나믹 프로그래밍 방식으로 접근 했다. (알고리즘 태그 본 건 비밀..) 다이나믹 프로그래밍이라는 것을 보니 해법이 떠올랐다. 문자열이 0~N까지 있다면, 0 - X, X+1 - N 까지의 합이 최소인 걸 리턴하면 된다. (이렇게 적으니 매우 간단해 보인다..) 먼저 구간 0 -N 을 함수에 던져 준다. 그리고 for문을..

티스토리툴바