본문 바로가기

BOJ

8. DFS로 푼 그래프 문제 (백준 4963 파이썬) 정말 그래프 문제는 아마도 푸는 방법이 다양한 것 같은데 일단 DFS로 풀었다. 반복되는 걸 느끼는 순간 재귀 못놓아.. 그래서 이번에도 필연적으로 또 Recursion Error만났죠.. 하지만 생각해보니 BFS도 재귀하면 되는걸.. 다음에는 시도해보는걸로.. https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또.. 더보기
6. 기본정렬에 대하여- 버블정렬, 선택 정렬, 삽입 정렬(백준 2750 파이썬) 기본 오브 기본 정렬 문제도 풀어보았다. 내가 기억하는 애들은 기본적인 버블정렬, 선택정렬, 삽입정렬 그리고 대망의 퀵정렬이다. 아마도 앞의 정렬들은 직접 구현하기보다 파이썬의 sorted()나 .sort()를 써서 해결할 것 같고, 실제 구현을 하게 될 애는 시간복잡도 nlogn에 빛나는 퀵정렬이 아닐까 한다. 백준에 정렬 기본 문제는 2750(브론즈1)과 2751(실버5)가 있는데, 차이는 주어지는 수의 크기 차이로, 실버 문제는 일반 정렬로는 시간초과가 나오지 않을까 예상이 간다. 그래서 오늘은 2750번은 버블정렬, 선택정렬, 삽입정렬 3가지로 풀어보고, 다음 게시글에서 2751번은 퀵정렬을 구현하는 시간을 가져보겠다. https://www.acmicpc.net/problem/2750 2750번:.. 더보기
5. Tree 전위순회 중위순회 후위순회 (백준 1991 파이썬) 트리도 오랜만이다.. 실버 1인데 반해 정답률도 높고 어렵지 않은 문제이지만, 혼자 잘 풀어낸 기념으로 작성 문제에 사실상 개념이 다 적혀있지만 이진 트리 : 한 노드에 자식 노드가 최대 2개인 트리 전위 순회(preorder) : 루트 -> 왼쪽 자식 -> 오른쪽 자식 중위 순회(inorder) : 왼쪽 자식 -> 루트 -> 오른쪽 자식 후위 순회(postorder) : 왼쪽자식 -> 오른쪽자식 -> 루트 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.. 더보기
4. 브루트포스 그런데 최소공배수를 곁들인 (백준 6064 파이썬) (백준 1476 파이썬) 실버1인데 6064번 잘 풀려서 쓰는 글 맞습니다. 근데 lcm 함수를 곁들인.. 전에 아주 열심히 최대공약수, 최소공배수 구현했었는데, 물론 헛된건 아니지만 함수가 있었음에 꽤나 허무했던 기억이 있어서..^^ 이번에는 최소공배수 함수를 써버렸다..☆ import math 안에 최대공약수 : Greatest Common Divisor : math.gcd(A, B) 최소공배수 : Least Common Multiple : math.lcd(A, B) 여튼 문제는 아래와 같다. https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어.. 더보기
3. 이제는 친숙해진 DFS, BFS (백준 1260 파이썬) 처음 배웠을 때는 충격과 공포였는데, 이제는 오히려 안심이 되는(?) 친근해진 DFS, BFS다. 생각보다 개념은 단순하게, 트리모양을 보면 이해가 빨리 되고, 실제 문제를 풀 때 내가 가장 쉽게 이해한 방법은: DFS는 stack, 그리고 재귀는 결국 stack이므로 재귀로 풀 수 있음 BFS는 queue, 그래서 더 쉽긴한데 pop(0)이 좀 효율성이 안좋다 이외에 좀 주의해야 하는 부분은 입력 값을 어떻게 저장하는가 부분이다. 사실 그래프 유형과 DFS BFS 유형도 비슷한 것 같고,, 재귀로 푸는 문제들도 서로서로 비슷한 것 같고.. 약간 딱 나눠서 할 수 있나 싶은데 (백준에서도 브루트포스 재귀로 분리되어 있는 문제가 DP로 풀기도 하고..) 여튼 그래프 형식은 노드, 간선, 시작점 입력에 익숙.. 더보기
2. 이맛에 푼다 Brute Force (백준 3085 파이썬) feat. 반례 사실 3085번 내 풀이가 브루트포스 방식이 맞는지에 약간 확신은 없지만, 일단 백준 분류에서 브루트포스로 뜨기 때문에 그렇게 적었다. 알고리즘을 놓은지 어연 6개월..(사실 6개월 훨씬 넘은듯) 정말 흐릿해진 기억 저편에 남은 delta값 사용 방식을 가지고 혼자 이렇게 저렇게 몇시간을 시도한 끝에, 기대하지 않은 '맞았습니다!!' 를 보는 희열은 참.. 행복하네.. 2시간 넘게 걸렸지만 역시 이게 맛이구나 하는 생각이 든다. 정말 자신감 바닥이었는데 혼자 오래걸려도 해결하고 나니 다시 자신감 뿜뿜 의욕 뿜뿜 열심히 준비해서 꼭 패스하고 싶ㄷㅏ 물론 정말 잘 푼 사람들이 많겠지만 일단 성공했으니 또 적어본다. https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제.. 더보기
1. DP 이것은 무엇인가 (백준 1463 파이썬) DP : Dynamic Programming 내 머릿속에 일단 DP는 피보나치이다. 한 번 나왔던 값은 저장을 해서 다시 구하는 시간을 절약할 수 있다는 것이 핵심이다. Top-down(하향식) 방식 : 내려가며 재귀 Bottom-up(상향식) 방식 : 올라가며 반복문 나는 재귀를 처음 이해한 후에 재귀에 빠져서 하향식을 더 선호했는데, 사실 이제 다 잊어버리기도 했고(...) 문제마다 어떤 방식이 더 좋은지가 애초에 달라질 수 있는 것 같다. 백준 1463번 풀이를 하며 이해해보도록 노력하겠다. https://www.acmicpc.net/problem/1463 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, .. 더보기

티스토리툴바