알고리즘14 DFS / BFS 차이 두가지 모두 그래프를 탐색하는 방법이다. DFS 가장 깊은 곳까지 탐색을 마치고 돌아와서 탐색하는 방법. 예를들면 미로찾기를 할 때 한 방향으로 쭉 가고, 막다른 길이 나오면 다시 가장 가까운 갈림길로 돌아와서 다시 그 방향으로 쭉 가는 방법. 특징) DFS는 모든 노드를 방문해야할 때 사용하면 좋다.★★★ (다만, 모든 정점을 방문할 땐 DFS나 BFS나 편한걸 사용하면 되지만 DFS의 코드가 더 짧아서 보통 DFS를 추천하고, 속도는 BFS가 더 빨라서 제한시간이 빡세게 잡혀있다면 BFS를 사용하는게 좋은 경우도 있다.) DFS는 Stack 또는 재귀함수를 사용하는데 보통은 스택을 사용하길 권장한다.★ 경로마다 특징이 있는 경우 DFS를 사용해야한다. 탐색할 그래프가 엄청 크다면 DFS를 사용한다. .. 2023. 2. 4. 12/27 스터디 1300 K번째 수 n=10 , k=20이면 숫자가 크다보니 규칙을 찾아야함 A 행렬 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 12 14 16 18 20 3 6 9 12 15 18 21 24 27 30 4 8 12 16 20 24 28 32 36 40 ... 10 20 30 40 50 60 70 80 90 100 B[20] 이중에서 20보다 작거나 같은 값이 몇개인지 세면 됨 => 각 행이 구구단임 ? k=20 i*j가 20 안에 몇개인지 세면 되는데 1행은 10개 10까지 2행은 10개 20까지 3행은 6개 18까지 4행은 5개 20까지 5행은 4개 20까지 6행은 3개 18까지 7행은 2개 14까지 8행은 2개 16까지 9행은 2개 18까지 10행은 2개 20까지 k // i => 2.. 2022. 12. 28. 12/23 스터디 어떤 블로그에서 봤는데, 이분탐색은 숫자 맞추는 up down 게임이라고 하더라... 좋은 예시인 것 같다.. 2110 공유기 설치 ㅇ 9663 N-Queen python으로는 실패하고... 동일 코드로 pypy로는 통과하는 문제인데 간혹 이런 문제가 나오는데 로직이 문제인지 잘 모르겠다... pypy로만 통과되는 문제면 그만큼 시간관리가 엄격하다는 건데, 그래서 그런지 검색해서 나오는 코드마다 모두 일차원 배열로 풀었다. 이차원 배열은 시간이 더 많이 걸려서 그런가보다 ... 일차원 배열 board를 선언했는데 이것의 의미는 board[ i ] = j 일 때 [ i, j ]에 퀸을 놓겠다는 의미이다. 이것을 잘 기억해두어야 한다. 우리가 문제를 풀 때 사용하는 함수는 2가지이다. 퀸을 놓을 수 있는지 .. 2022. 12. 23. 12/20 스터디 15651 N과 M(3) N과 M(1) 문제와 매우 비슷한 문제였다. 애당초 N과 M 문제들 자체가 순열 조합 문제라서, 순열 조합 중복순열 중복조합으로 이해하고 접근하면 바로 풀 수 있었다. 이 문제는 순열과 똑같은 맥락에, 중복을 추가한 문제였기 때문에 순열 코드에서 중복을 제거하는 부분만 없애주면 중복을 추가해줄 수 있게 되고 그러면 중복순열을 구현할 수 있었다. 따라서 for문 안에 if i not in s부분을 지워주면 된다. 나머지 코드는 15649 N과 M(1) 문제의 코드와 동일하다. n, m = list(map(int, input().split())) s = [] def dfs(): if len(s) == m: print(' '.join(map(str, s))) return for i i.. 2022. 12. 20. 12/14 스터디 15650 N과 M(2) 앞서 풀었던 15649 문제 N과 M(1)이 순열 문제였다면, 이 문제는 조합 문제였다. 마찬가지로 combination을 쓰면 금방 풀 수 있지만 이것도 백트래킹을 활용해 풀어야한다. 순열과 조합 자체가 유사한데 한가지 다른 점은 순열은 [1,2]와 [2,1]이 다르지만 조합은 서로 같다. 이 점을 이용해서 15649 코드를 조금 변형하면 된다. n, m = list(map(int, input().split())) s = [] def dfs(start): if len(s) == m: print(' '.join(map(str, s))) return for i in range(start, n + 1): if i not in s: s.append(i) dfs(i + 1) s.pop(.. 2022. 12. 15. 12/7 스터디 1920 수 찾기 전형적인 binary search 문제였고, 이분탐색을 위해 먼저 정렬을 해주었다. 정렬 후 각 숫자들에 대해 모두 binary search 알고리즘을 적용해주었다. 이때, 한가지 다른 점은 flag를 각 숫자마다 0으로 설정해놓고 숫자를 찾으면 flag = 1, 없으면 그대로 0으로 설정을 해서 마지막에 flag 값에 따라 숫자 유무를 검사해서 1 혹은 0을 출력해주는 형식으로 진행해주었다. binary search에 대해 간단히 설명하면, 반씩 쪼개서 탐색을 하는 알고리즘인데 탈출 조건은 start와 end가 서로 엇갈리는 순간이다. 즉, start 2022. 12. 9. 12/1 스터디 11054 가장 긴 바이토닉 부분 수열 쉽게 생각하면, 11053의 LIS를 두번 적용하는 것 뿐인 문제였다. 바이토닉 부분 수열이라는 것이, 특정 element를 기점으로 쭉 증가하다가 감소하는 형태를 보이는 수열인데, 이것은 가장 긴 증가하는 부분수열과 가장 긴 감소하는 부분수열의 합쳐진 형태였기 때문이다. 가장 긴 감소하는 부분수열 문제도 있었기에 그것을 그대로 인용해도 됐지만 가장 긴 감소하는 부분수열이라는 것이 다르게 생각하면 마지막에서부터 거꾸로 올라간다면 그것도 역시 거꾸로 가장 긴 증가하는 부분수열이었기 때문에 결국 LIS를 2번 적용하되 하나는 거꾸로 적용하면 되는 형태였다. 따라서 증가하는 부분수열 increase, 감소하는 부분수열 decrease를 선언해놓고 두개를 합칠 예정인 re.. 2022. 12. 1. 11/27 스터디 11053 가장 긴 증가하는 부분 수열 [ tip ] input을 sys.stdin.readline 으로 선언해놓으면, 귀찮게 저렇게 다 안치고 input()으로만 쳐도 sys.stdin.readline을 친 것과 같은 효과를 볼 수 있다. 속설에 따름녀 sys.stdin.readline은 input보다 속도가 거의 2배 빠르다고 하므로 ... 저렇게 써서 하는 것이 좋아보인다. LIS 문제였는데, dp는 A[i]에서 가장 긴 부분수열의 길이를 넣어놓는다. 10 20 10 30 20 50 이라고 할 때 dp값은 다음과 같다. A 10 20 10 30 20 50 dp 1 2 1 3 2 4 생각보다 단순할 수 있는데, 처음에는 생각하기 어렵다. A[i]에서 자기 앞에 자기보다 작은 수가 몇개인지 세면 됐기 .. 2022. 12. 1. 11/23 스터디 10844 쉬운 계단 수 수정 예정 # 계단 수는 자리수를 하나씩 줄여도 그대로 계단 수 이어야 한다. # 즉, 자리수가 3개일 때 계단수인 수들은 자리수가 2개였어도 계단수이다. # ==>> 자리수 2개인 계단수들 중에서 하나씩 추가하는 매커니즘 # ex. 45656 => 4565 로 바뀌어도 계단수여야한다. n = int(input()) dp = [[0 for i in range(10)] for j in range(101)] # [자리수][비교 대상인 숫자] # 맨 마지막 숫자가 곧 비교대상이 되는 숫자 # 자리수 한개일 때 초기화 -->> 1~9 for i in range(1, 10): dp[1][i] = 1 # 자리수가 1일 때, 그리고 뒤에 숫자가 i인 경우에 계단수 개수가 dp값 # 자리수 2.. 2022. 11. 24. 이전 1 2 다음
