본문 바로가기
[백준 4963번 섬의 개수(DFS)/ C++] www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 훟 예전 같았으면 이문제를 bfs로 풀었겠지만...! 더이상 예전의 내가 아니양!🥳 난 dfs로 문제를 풀어낼 수 이찌 응켘엨엥 이 문제는 영역 개수를 세는 다른 문제들과 크게 다를 것은 없었당 하지만 하나 꼽자면 가로, 세로 뿐만 아니라 대각선에 있는 "1"까지 동일한 영역으로 간주하였기 때문에 그 부분을 dx, dy에 포함시켜주는것 만 포함했다면 완뵥!✨ #include #include using na.. 2021. 1. 26.
[백준 10451번 순열 사이클(DFS)/ C++] www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 어떻게 보면 혼란스러울 수 있는데! 사실 연결돼 있는 노드 집합의 개수를 찾는 방식과 똑같다 ㅎㅎ 2021/01/22 - [Studying 📖/알고리듬(thm) 공부 🌱] - [백준 11724번 연결 요소의 개수(BFS, DFS)/ C++] [백준 11724번 연결 요소의 개수(BFS, DFS)/ C++] www.acmicpc.net/pr.. 2021. 1. 22.
[백준 1707번 이분 그래프(DFS)/ C++] www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 처음에는 이분그래프가뭐지!!!! 무슨 말이 저렇게 어렵지!!!하고 있었는데 Prof.google을 통해 알게 되었다.. 정말 어렵게 설명돼 있지만 결국 서로 연결돼 있는 노드끼리 다른 그룹에 속하는 그래프를 의미한다! 더 쉽게 시각적으로 이해한다면 다음과 같다! ㅎㅎ 다음 그림을 보면 서로 연결된 노드는 다른 색을 가지고 있다 ㅎㅎ! 그럼 dfs를 통해서 한 노드에 들어갈 때마다 색깔을 이전에 노드.. 2021. 1. 22.
[백준 11724번 연결 요소의 개수(BFS, DFS)/ C++] www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 예전엔 bfs가 편해서 bfs로만 풀었었는데,,, ㅎㅅㅎ 나의 dfs 도전기... 앞으로 두가지 방식 모두로 풀어볼란다 후후 나! 다짐했어 (두둥) 오늘부터 dfs 마스터가 될꺼야!!!!! 응캬캬캬 🐮 두 방식다 11724 문제에서는 같은 성격을 띠고 있지요 ㅎㅎ dfs도 그렇고 bfs도 그렇고 한 노드에서 시작해서 이제 더이상 연결 되어 있지 않았.. 2021. 1. 22.
[백준 2745번 진법 변환 / C++] ‼️만약 진법이 36이라면 한자리당 36만큼의 수, 그리고 그 다음수는 36의 제곱이 담긴 수가 합쳐져서 나오는 것. 진법이라는 것은 어떠한 숫자를 어떻게 표현하는지에 대한 방법을 지칭하며 36진법이란 36개의 숫자를 이용해서 표현한다는 것이다. (0~35) for (int i = s.size() - 1; i >= 0; i--) "ZZZZZ"가 있을 때 가장 오른쪽부터 각 자리수는 36^4,36^3,36^2,36^1,36^0으로 카운트 된다. 그렇기 때문에 s.size()-1부터 0 까지 for문을 돌리며 각 자리수를 맞춰주는 것! 알파벳이 "A"이상인 경우 다음과 같이 알파벳 대문자를 사용한다. if (s[i] >= 'A') ret += (int)pow(n, cnt) * ((int)s[i] - 'A' .. 2021. 1. 21.
[백준 11053번 가장 긴 증가하는 부분 수열 / C++] www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 코드를 짜야한다! 10 20 10 30 20 50 1 2 1 3 2 4 방식은 우선 수열을 for문을 돈다. 그리고 맨 처음부터 해당 수까지 for문을 돌면서 자신보다 작은 아이가 있다면! 해당 dp의 수에 +1을 한 것과 현재 dp의 수를 비교하여 더 큰 값을 저장해준다. .. 2021. 1. 8.
[백준 2193번 이친수/ C++] www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 0 1 2 3 4 5 6 7 8 9 0 1 1 2 3 5 8 13 21 34 각 자리수 마다 만들어지는 이진수의 개수는 위의 표와 같다! 명확히 식이 들어나는 문제이다...ㅎㅅㅎ!!!👍🏻 dp[i] = dp[i-1] + dp[i-2]인 것을 확인할 수 있다. #include using namespace std; long long dp[91]; int main() { dp[1] = 1; dp[2] = .. 2021. 1. 7.
[백준 11057번 오르막 수/ C++] www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net ㅎㅅㅎ 쉬운 계단 수를 풀고 바로 풀어본 문제! 한번 이해하고 나니 ㅎㅅㅎ 뭔가 훨씬 접근 방법이 편했따 ✅ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-10844%EB%B2%88-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98-CDP [백준 10844번 쉬운 계단 수/ C++](DP) www.acmicpc.. 2021. 1. 7.
[백준 10844번 쉬운 계단 수/ C++](DP) www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉬운 계단 수는 예전에 스터디할 때도 풀었던 문제다..ㅎㅅㅎ 하지만 사실 완벽히 이해하지 못한게 사실이다...🙈 그래서 다시 풀었지 ㅎㅎ 아웅>_> n; for (int i = 1; i < 10; i++) { dp[1][i] = 1; } for (int i = 2; i 2021. 1. 7.
반응형

티스토리툴바