본문 바로가기
728x90

그 땐 Algorithm했지

 (56)
[BAEKJOON/Python] no.16401 과자 나눠주기 | 이진 탐색 문제 https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 1차 풀이 : 구글링ㅎ 👉🏻도대체가 어떻게 풀어야 하는지 모르겠어서 1시간 고민하고 구글링을 해보았다..ㅎㅎ from sys import stdin input = stdin.readline children_count, snack_count = map(int, input().split()) snacks = list(m..
[BAEKJOON/Python] no.10815 숫자 카드 | 정렬 문제 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1차 풀이 my_card_count = int(input()) card_list = list(map(int, input().split())) number_count = int(input()) find_number = list(map(int, input().split())) for number in find_number: if number in card_list:..
[BAEKJOON/Python] no.2606 바이러스 | DFS/BFS 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1차 풀이 computer_count = int(input()) network_count = int(input()) graph = [[] for _ in range(computer_count + 1)] for i in range(network_count): from_com, to_com = map(int, input().split()) graph[from_com].append(to_com) gra..
[TAVE/이코테] ch09 최단 경로 | 실전 문제 참고자료: 이것이 코딩테스트다 실전 - 미래 도시 INF = int(1e9) company_count, road_count = map(int, input().split) graph = [[INF] * (company_count + 1) for i in range(company_count + 1)] for i in range(1, company_count + 1): for j in range(1, company_count + 1): if i == j: graph[i][j] = 0 for _ in range(road_count): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 x, k = map(int, input.split()) for ..
[TAVE/이코테] ch09 최단 경로 | 개념 정리 참고자료: 이것이 코딩테스트다 가장 빠르게 도달하는 방법 📌최단경로: 가장 짧은 경로를 찾는 알고리즘 👉🏻보통 그래프를 이용해 표현한다. 각 지점은 그래프에서 '노드'로 표현되고 지점간 연결된 도로는 그래프에서 '간선으로'표현된다. 최단경로 알고리즘 종류는 다음과 같다. 다익스트라 알고리즘 플로이드 워셜 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘 📌그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구한다. '음의 간선'이 없을 때 정상적으로 동작하는데 이러한 특성으로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 👉🏻기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. 원리는 ..
[TAVE/파이썬 알고리즘 인터뷰] Ch13 | 최단 경로 문제 - 개념 정리 참고자료: 파이썬 알고리즘 인터뷰 최단 경로 문제 📌최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제다. 정점: 교차로 간선: 길 가중치: 거리나 시간과 같은 이동 비용 👉🏻그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재한다. 다익스트라 알고리즘 📌최단 경로 알고리즘 중 가장 유명하다. 네덜란드의 유명한 컴퓨터과학자 에츠허르 다익스트라가 대학원생 여자친구와 카페에 가서 20분 만에 고안한 알고리즘이다. 단순한 알고리즘이 가장 훌륭한 알고리즘이라는 것을 증명하는 대표적인 알고리즘이다. 1️⃣그리디 알고리즘 👉🏻구현하기 쉽지만 느리게 동작한다. 👉🏻다익스트라의 최초 구현에서는 시간 복잡도가 O(V제곱)였다. 왜냐하면 방문하지 않은..
[TAVE/파이썬 알고리즘 인터뷰] Ch11 | 해시 테이블 - 개념 정리 참고 자료: 파이썬 알고리즘 인터뷰 📌해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료이다. 👉🏻대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이다. 해시 📌해시 함수: 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수 📌해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 ABC → A1 1234BC → CB AF32B → D5 👉🏻위의 각각 3글자, 6글자. 5글자인 문자열을 모두 2바이트의 고정 크기 값으로 매핑했다. 여기서 화살표 역할을 하는 함수가 해시 함수이다. 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용한다. 생일 문제 더보기 💡 여러 사람이 모였을 때 생일이 같은 2명이 존재할..
[TAVE/이코테] ch08 다이나믹 프로그래밍 | 실전 문제 참고자료: 이것이 코딩테스트다 실전 - 1로 만들기 x = int(input()) d = [0] * 30001 for i in range(2, x + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) if i % 5 == 0: d[i] = min(d[i], d[i // 5] + 1) print(d[x]) 👉🏻d의 각 자리에 연산을 얼마나 했는지 저장해주는 것이 point다. 숫자를 for문 돌리면서 각 연산을 모두 시도해준다. if-else문이 아닌 3개의 if문을 쓴 건 모든 연산을 다 가능한지 확인하기 위함이다. d[i]의 이전값이 d[x-1..
728x90

티스토리툴바