본문 바로가기

C++156

[백준] 9205번 - 맥주 마시면서 걸어가기 (C++) 문제 및 풀이 문제) 백준 - DFS - 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 좌표를 모두 입력받아 20*50을 넘는 점을 제외하고 graph에 인접 리스트 형태로 나타냅니다. DFS를 통해 탐색하면서 visited [N+1] 번째를 방문 여부에 따라 'happy' 또는 'sad'를 출력합니다. C++ 소스코드) Full code) https://github.com/Chocochip101/BOJ_Solution/blob.. 2021. 12. 26.
[백준] 2636번 - 치즈 (C++) 문제 및 풀이 문제) 백준 - BFS - 치즈 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net BFS로 board에서 치즈 개수를 탐색하며 0으로 바꿉니다. prevCheeze로 이전 치즈의 개수를 저장하고 cntCheeze가 0이면 break 합니다. C++ 풀이) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2636_%EC%B9%98%EC%A6%88.cpp GitHu.. 2021. 12. 23.
[백준] 5582번 - 공통 부분 문자열 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS랑 유사한 연속된 공통 문자열을 찾는 문제였습니다. LCS를 풀어봤다면 쉽게 풀 수 있는 문제입니다. C++ 소스코드) 2021. 12. 22.
[백준] 1213번 - 팰린드롬 만들기 (C++) 문제 및 풀이 문제) 백준 - 구현 - 팰린드롬 만들기 https://www.acmicpc.net/problem/1213 2021. 12. 20.
[백준] 1043번 - 거짓말 (C++) 문제 및 풀이 문제) 백준 - Union Find - 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net N이 50 이하이기 때문에 알고리즘 유형이 Union Find인 것을 직감하셨으면 쉽게 풀 수 있었던 문제입니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/1043_%EA%B1%B0%EC%A7%93%EB%A7%90.cpp GitHu.. 2021. 12. 16.
[백준] 13913번 숨바꼭질 4 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 통해 탐색하면서 동생의 위치를 찾는 문제였습니다. tr 배열을 이용해 방문했던 이전 점의 좌표를 저장했습니다. 그 후 반복문을 통해 이동한 자취를 출력했습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201.. 2021. 12. 14.
[백준] 1766번 - 문제집 (C++) 문제 및 풀이 문제) 백준 - 위상 정렬 - 문제집 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제를 세 개의 조건에 맞게 출력하는 문제였습니다. 조건 2(먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다)를 통해 위상 정렬을 사용해야됨을 알 수 있습니다. 조건 3(가능하면 쉬운 문제부터 풀어야 한다)을 통해 위상 정렬 Queue 내부에서 정렬이 필요함을 알 수 있는데 이 정렬.. 2021. 12. 13.
[백준] 4386번 - 별자리 만들기 (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리 - 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별자리를 이어 최소 비용으로 모두를 연결되게 만드는 문제였습니다. 모두가 연결되어야하고 최소 비용을 사용해야되므로 최소 스패닝 알고리즘으로 쉽게 해결할 수 있었습니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/4386.. 2021. 12. 12.
[백준] 9019번 - DSLR (Python) 문제 및 풀이 문제) 백준 - BFS - DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 만들 수 있는 수 중에서 최소 명령을 사용하는 것을 탐색하는 문제였습니다. BFS로 탐색하면서 queue에 (숫자, 명령어)를 넣고 명령어를 만들 수 있는 모든 경우의 수(D, S, L, R)를 탐색했습니다. 파이썬 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Pr.. 2021. 12. 10.
반응형

티스토리툴바