[Python Algorithm] 완전탐색(DFS) - 바둑이 승차 > 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 📖 문제 : 바둑이 승차 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. 입력설명 첫 번째 줄에 자연수 C(1 Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.31
[Python Algorithm] 완전탐색(DFS) - 합이 같은 부분집합(DFS : 아마존 인터뷰) > 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 📖 문제 : 합이 같은 부분 집합 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력설명 첫 번째 줄에 자연수 N(1 Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.29
[Python Algorithm] 완전탐색(DFS) - 부분집합 구하기 > 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 📖 문제 : 부분집합 구하기(DFS) 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 입력설명 첫 번째 줄에 자연수 N(1 Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.29
[Python Algorithm] 완전탐색(DFS) - 이진트리 순회 > 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 이진트리의 전위순회와 후위순회 연습하기 (재귀를 통해 DFS 배우기) 아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요. 전위순회 출력 : 1 2 4 5 3 6 7 중위순회 출력 : 4 2 5 1 6 3 7 후위순회 출력 : 4 5 2 6 7 3 1 import sys def DFS(n): if n>7: return else: print(n, end=" ")# ** #(1) DFS(n*2)# 왼쪽 자식 노드 #(2) DFS(n*2+1)# 오른쪽 자식 노드 #(3) DFS(1) ⭐️ Point ! ⭐️ 전위순회는 자주 쓰임. 쓰임 빈도: 전위 > 후위 > 중위 print(n, end=" ") 의 위치에 따라 - 전위순회 : .. Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.29
[Python Algorithm] 완전탐색 - 재귀함수를 이용한 이진수 출력 > 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 📖 문제 : 재귀함수를 이용한 이진수 출력 10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다. 입력설명 첫 번째 줄에 10진수 N(1 Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.29
[Python Algorithm] 자료구조(힙) - 최대힙 > 자료구조 활용 - 스택, 큐, 해쉬, 힙 (힙 편) 최대힙은 부모가 두 자식보다 값이 크다 ! 📖 문제 : 최대 힙 최대힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드값이 왼쪽자식과 오른 쪽 자식노드의 값보다 크게 트리를 구성하는 것입니다. 그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 큰 값이 저장되어 있습니다. 예를 들어 5 3 2 1 4 6 7순으로 입력되면 최대힙 트리는 아래와 같이 구성됩니다. 최대힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램을 작성하세요. 1) 자연수가 입력되면 최대힙에 입력한다. 2) 숫자 0 이 입력되면 최대힙에서 최댓값을 꺼내어 출력한다. (출력할 자료가 없으면 -1를 출력한다.) 3) -1이 입력되면 프로그램 종료한다. 입력설명.. Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.28
[Python Algorithm] 자료구조(힙) - 최소힙 > 자료구조 활용 - 스택, 큐, 해쉬, 힙 (힙 편) 힙구조 최소힙은 부모가 자식들보다 무조건 작아야 함. 최소힙에서 pop하면 root값이 pop되고, 제일 오른쪽 밑(가장 밑의 레벨을 다 없애고 그 위의 레벨을 없애는 순서로) 의 값이 root로 올라가서 최소힙으로 다시 만든다 (다운-힙) (다운-힙) 은 왼쪽 자식과 오른쪽 자식중에 더 작은 값과 부모와 비교해가며 swap하며 최소힙을 만든다. 📖 문제 : 최소힙 최소힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드값이 왼쪽자식과 오른 쪽 자식노드의 값보다 작게 트리를 구성하는 것입니다. 그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 작은 값이 저장되어 있습니다. 예를 들어 5 3 2 1 4 6 7순으로 입력되 면 최.. Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.28
[Python Algorithm] 자료구조(리스트 해쉬) - 아나그램 > 자료구조 활용 - 스택, 큐, 해쉬, 힙 (해쉬 편) 📖 문제 : 아나그램 Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아 나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세 요. 아나그램 판별시 대소문자가 구분됩니다. 입력설명 첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을.. Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.28
[Python Algorithm] 자료구조(딕셔너리 해쉬) - 아나그램 > 자료구조 활용 - 스택, 큐, 해쉬, 힙 (해쉬 편) 📖 문제 : 아나그램 Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아 나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세 요. 아나그램 판별시 대소문자가 구분됩니다. 입력설명 첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을.. Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.28
[Python Algorithm] 자료구조(해쉬) - 단어찾기 > 자료구조 활용 - 스택, 큐, 해쉬, 힙 (해쉬 편) 📖 문제 : 단어찾기 현수는 영어로 시를 쓰는 것을 좋아합니다. 현수는 시를 쓰기 전에 시에 쓰일 단어를 미리 노트에 적어둡니다. 이번에는 N개의 단어를 노트에 적었는데 시에 쓰지 않은 단어가 하나 있다고 합니다. 여러분이 찾아 주세요. 입력설명 첫 번째 줄에 자연수 N(3 Algorithm (Python, Java, SQL)/Inflearn Study 2023.03.28