O'bin and the Chocolate Factory

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 from collections import deque n, m = map(int, input().split()) maze = [list(map(int, input())) for _ in range(n)] def bfs(graph, x, y): q = deque([(0, 0)]) # 상하좌우 이동 값 d..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net sol 1) BFS(너비 우선 탐색) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 from collections import deque n = int(input()) def bfs(x): visited = [False] * (n + 1) # n + 1 크기의 방문 체크 배열 생성 q = deque([(x, 0)]) # 큐에 초기 값과 연산 횟수 추가 visited[x] = True # 초기 값 방문 체크 w..

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr sol 1) BFS(너비 우선 탐색) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from collections import deque def solution(numbers, target): answer = 0 q = deque() n = len(numbers) q.append([numbers[0], 0]) q.ap..

https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from collections import deque def solution(bridge_length, weight, truck_weights): time = 0 current_weight = 0 on_bridge = deque([0]..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 t = int(input()) for _ in range(t): n, m = map(int, input().split()) file = list(map(int, input().split())) answer = 1 while file: if file[0] 0 else len(file) - 1 print(an..

셸 정렬 단순 삽입 정렬의 장점 + 단점 보완한 더 빠른 정렬 알고리즘 단순 삽입 정렬 장점 : 이미 정렬을 마쳤거나 끝나가는 상태에서 매우 빠른 속도 단점 : 삽입할 위치가 멀면 이동 횟수가 많아짐 정렬횟수는 증가하나, 전체적으로 원소의 이동 횟수가 줄어 효율적 서로 h 만큼 떨어진 원소를 꺼내 그룹으로 만들고 그룹별로 정렬 = h-정렬 ex) 4-정렬 -> 2-정렬 -> 1-정렬 순으로 실행 1 2 3 4 5 6 7 8 9 10 11 12 def shell_sort(a: MutableSequence) -> None: n = len(a) h = n // 2 while h > 0: for i in range(h, n): j = i - h tmp = a[i] while j >= 0 and a[j] > tm..

~ 목차 ~ 정렬 알고리즘 버블 정렬 버블 정렬 버블 정렬 개선 1 - 교환 발생하지 않는 경우 정렬 중단 버블 정렬 개선 2 - 이미 정렬된 원소는 비교/교환 범위에서 제외 버블 정렬 개선 3 - shaker sort 단순 선택 정렬 단순 삽입 정렬 정렬 알고리즘 - 안정적인 정렬 알고리즘 vs 안정적이지 않은 정렬 알고리즘 값이 같은 원소의 순서가 정렬 후에도 유지되는지 여부에 따라 결정 -> 유지 : 안정적 -> 유지 보장 x : 안정적 x - 내부 정렬 vs 외부 정렬 정렬할 데이터를 하나의 배열에 저장할 수 있는지 여부에 따라 결정 -> 가능 : 내부 정렬 -> 불가능 : 외부 정렬 - 버블, 단순 선택, 단순 삽입 정렬 시간복잡도 모두 O(n^2)로 프로그램 효율 좋지 X 버블 정렬(bubbl..

~ 목차 ~ 해시법 해시 충돌 체인법 오픈 주소법 정렬된 배열에서 원소 추가/삭제 시, 추가/삭제 위치 뒤/앞의 원소들 한칸씩 뒤/앞으로 밀어야 한다 = 복잡도 O(n) 해시법 검색과 데이터 추가/삭제도 효율적으로 수행할 수 있는 방법 해시 값(hash value) : 배열의 키(= 원소의 값) %원소의 개수 해시 함수(hash function) : 키->해시값 과정 해시 테이블(hash table) : 해시값을 인덱스로 하여 원소를 새로 저장한 배열 버킷(bucket) : 해시 테이블에서 만들어진 원소 해시 충돌 키와 해시값은 일반적으로 n:1 관계 해시 충돌 : 저장할 버킷이 중복되는 현상 해시 충돌 대처법 체인법 : 해시값이 같은 원소 연결리스트로 관리 오픈 주소법 : 빈 버킷을 찾을때까지 해시 반..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import sys from collections import Counter # input()으로 입력 받으면 시간초과 발생 input = sys.stdin.readline n = int(input()) nums = [int(input()) for _ in range(n)]..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net sol1) m부터 n 사이의 숫자들이 약수인지 여부를 특정 숫자의 제곱근까지만 확인하여 판별 1 2 3 4 5 6 7 8 9 10 11 m, n = map(int, input().split()) for i in range(m, n+1): if i == 1: continue # i의 제곱근까지만 검사 for j in range(2, int(i ** 0.5) + 1): if i % j == 0: break else: print(i)..