목록공부/알고리즘(파이썬) (64)
컴퓨터는 잘못이 없다..
[알고리즘]BOJ_1946_신입 사원(파이썬 리스트안에 리스트로 입력받으면서 동시에 오름차순까지 하는 방법)
#문제 링크 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net #문제 https://www.acmicpc.net/problem/1946 신입 사원 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초256 MB242307665558031.806% 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 ..
[알고리즘]BOJ_11047_동전 0
#문제 링크 11047번: 동전 0 (acmicpc.net) 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 #문제 동전 0 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초256 MB52511279192191352.688% 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째..
[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(5) - BFS, BFS와 DFS의 특징 및 정리
#책 페이지 p.143 #탐색 알고리즘 BFS에서 사용하는 자료구조 큐 자료구조 #BFS는 어떻게 동작할까? 👉BFS는 '너비 우선 탐색 알고리즘' 이다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색한다면 BFS는 반대이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 👉BFS는 큐 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. ① 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. ② 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다...
[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(5) - DFS
#책 페이지 p.137 #탐색 알고리즘 DFS에서 사용하는 자료구조 스택 자료구조 #DFS는 어떻게 동작할까? 👉DFS는 '깊이 우선 탐색 알고리즘' 이다. 이 알고리즘은 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 👉DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. ①탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. ②스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. ①,②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. ⭐방문처리? 스택에 한 번 삽입되어 처리된 노드가 다..
[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(3)_DFS,BFS에 필요한 자료구조 - 재귀 함수
#재귀 함수 재귀 함수란 : 자기 자신을 다시 호출하는 함수를 의미한다. #간단한 재귀 함수 예 def recursive_function() : print('재귀 함수를 호출합니다.') #재귀함수 호출 recursive_function() #재귀함수 호출 recursive_function() ▲설명 이 코드를 실행하면 '재귀 함수를 호출합니다.' 라는 문자열을 무한히 출력한다. 여기서 정의한 recursive_functino()이 자기 자신을 계속해서 추가로 불러오기 때문이다. 물론 어느 정도 출력하다가 다음과 같은 오류 메시지를 출력하고 멈출 것이다. RecursionError: maximum recursion depth exceeded while pickling an object 이 오류 메시지는 재..
[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(2)_DFS,BFS에 필요한 자료구조 - 스택, 큐
#스택 스택 : 박스 쌓기에 비유할 수 있음. 박스는 아래에서부터 위로 차곡차곡 쌓고 아래에 있는 박스를 치우기 위해서는 위에있는 박스를 먼저 내려야함. 이러한 구조를 선입후출(FILO) 구조 또는 후입선출(LIFO) 구조 라고 함 #파이썬의 스택 구현 리스트(stack=[])로 구현하며 push, pop은 아래와 같은 함수로 구현한다. i를 push : stack.append(i) 최상단 원소를 pop : stack.pop() #스택 예제 stack=[] stack.append(5) #5를 스택에 push stack.append(2) stack.append(3) stack.append(7) stack.pop() #최상단 원소를 pop stack.append(1) stack.append(4) stack...
