문제요약 (11047. 동전 0) 원하는 돈의 가치를 만들기 위해 필요한 동전의 최소 갯수를 구해 출력하라 다양한 경우의 수가 있지만 최소 갯수를 구해야한다. 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이를 위한 개념 그리디에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다. [코테 알고리즘] DFS, BFS / 관련 문제 본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련..

문제요약 ( 1920.수 찾기 ) 주어진 리스트에 원하는 값이 있는지 찾아 출력한다.. 풀이를 위한 부연 설명 정렬 알고리즘은 O(nlogn)의 시간 복잡도를 가진다. 이분탐색의 경우 O(nlogn)의 시간 복잡도를 가진다. 이분 탐색은 정렬된 데이터에 대해 실행할 수 있으므로 미리 sort()해야한다. 코드 import sys input = sys.stdin.readline num = int(input()) nums = list(map(int, input().split())) nums.sort() find = int(input()) finds = list(map(int, input().split())) for target in finds: first = 0 last = num - 1 isFind = F..

문제 요약 (2178. 미로 탐색) n * m 크기의 배열로 표현되는 미로가 주어질 때, (1, 1) 부터 (n, m)으로 이동하기 위해 지나가야하는 칸 수의 최솟값을 구해 출력한다. 배열의 n, m 모두 100 이하이기 때문에 시간 복잡도는 걱정할 필요는 없다. 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이를 위한 부연 설명 길찾기를 위한 표의 경우 45도 꺽어서 보면 그래프로 표현할 수 있다. 그래프의 문제의 경우 DFS와 BFS를 이용한 풀이 두 가지 모두 생각할 수 있다 그러나 해당 문제는 BFS를 통해 문제를 풀어야한다 완전..

문제요약 (2023. 신기한 소수) 소수 중에서 각 자리수 별로 나눠도 모두 소수라는 성질을 유지하는 소수를 찾아 출력한다. ex. 7331 -> 7331, 733, 73, 7 모두 소수 -> 우리가 구하고자 하는 수 정수를 입력 받고, 입력받은 정수 값의 자리 수만을 출력한다. 2부터 증가하면서 소수를 찾으면 시간초과에 걸릴 것이다. 다른 방법을 생각해봐야한다. 또한 뒷 자리수부터 숫자가 제거된다는 사실도 문제 해결의 키로 작용할 것이다. 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이를 위..

문제 요약 (11724. 연결 요소의 개수) 방향이 없는 그래프(양방향 그래프)의 노드와 간선이 주어졌을 때 연결 요소의 개수를 구하는 것이다. 연결 요소는 연결된 노드들의 뭉텅이라고 생각하면 문제를 풀기 편하다. ex. 1-5-2, 3-4, 6 이렇게 연결되어 있다면 연결 요소의 개수는 3이다. 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 풀이를 위한 부연 설명 입력되는 값들을 받아 그래프를 완성한다. 그래프 내에서 연결 요소를 찾아야하므로 ..

복잡도 시간 복잡도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 빅오 표기법 알고리즘의 로직이 얼마나 시간이 걸리는지(시간 복잡도)를 표현할 때 사용 입력 범위 n을 기준으로 로직의 반복 정도를 표시 가장 영향을 많이 미치는(=가장 큰) 항만 남김 시간 복잡도의 필요성 효율적인 코드 개선을 위해 필요 시간 복잡도의 속도 비교 공간 복잡도 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양 정적 변수와 동적 변수(재귀적 정의)를 모두 포함 자료구조에서의 시간 복잡도 [자료 구조의 평균 시간 복잡도] 자료구조 접근 탐색 삽입 삭제 배열 (Array) O(1) O(n) O(n) O(n) 스택 (Stack) O(n) O(n) O(1) O(1) 큐 (Queue) O(n) O(n) O(1) O(1) 이중 ..

📌 재귀 알고리즘의 기본 📚 재귀(recursive) 알아보기 어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀를 효과적으로 사용하면 프로그램을 간결하고 효율성 있게 작성 📚 팩토리얼 = 순차 곱셈 팩토리얼 : 양의 정수를 순서대로 곱한다는 의미 팩토리얼 n! 의 정의 (n은 양의 정수) 0! = 1 n > 0이면 n! = n * (n - 1)! # 양의 정수 n의 팩토리얼 구하기 def factorial(n: int) -> int: """양의 정수 n의 팩토리얼 값을 재귀적으로 구함""" if n > 0: return n * factorial(n - 1) else: return 1 if __name__ == '__main__': n = int(input('출력할 팩토리..

📌 스택이란? 📚 스택 알아보기 📃 스택 (stack) 데이터를 임시 저장할 때 사용하는 자료구조 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식 푸시(push) : 스택에 데이터를 넣는 작업 팝(pop) : 스택에서 데이터를 거내는 작업 겹쳐쌓은 접시처럼 데이터를 넣고 꺼내는 작업을 맨위부터 진행 푸시하고 팝하는 윗부분을 꼭대기(top), 아랫 부분을 바닥(bottom) 📚 스택 구현하기 📃 스택을 구현하는데 필요한 데이터 스택 배열 : stk 푸시한 데이터를 저장하는 스택 본체인 list 배열 인덱스가 0인 원소가 스택의 바닥 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0] 스택 크기 : capacity 스택의 최대 크기를 저장하는 정수 = len(stk) 스택 포인터 : ptr 스택에 ..

📌 검색 알고리즘이란? 📚 검색의 종류 배열 검색 (선형 검색) 연결 리스트 검색 이진 검색 트리 검색 📚 배열 검색 중에 배울 내용 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행 해시법 : 추가·삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법 📌 선형 검색 📚 선형 검색 (linear search) / 순차 검색 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우 사용 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘 배열의 개수가 n이라..

이 포스트는 [Do it! 자료 구조와 함께 배우는 알고리즘 입문 - 파이썬 편]을 보며 제가 알아야할 내용들을 정리한 포스트입니다. 개인 공부용이므로 자세한 설명이나 정보 설명을 위한 포스트는 아님을 미리 말씀드립니다. 📌 자료구조와 배열 📚 리스트의 기초 리스트의 원소를 변경할 수 있는 뮤터블(mutable) list 형 객체 파이썬 내장 함수인 list( )를 사용하여 다양한 자료형의 원소를 가진 객체 생성 가능 None을 통해 원솟값을 정하지 않은채로 개수 사용 가능 📚 튜플의 기초 튜플은 원소에 순서를 매겨 결합한 것으로 원소를 변경할 수 없는 이뮤터블(imutable) 자료형 tuple( ) 을 사용하면 문자열이나 리스트 등 여러가지 자료형 객체를 원소로 하는 튜플 생성 가능 📚 뮤터블과 이뮤..