분류 전체보기

[ 백준 11399 ] ( python ) ATM

📚 ATM 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필..

[ 백준 2839 ] ( python ) 설탕 배달

📚 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한..

[ 22.04.26 ] 오늘의 회고

⏳ 돌아보기 1. 알고리즘 알고리즘 코딩 테스트에 자주 빈출된다는 유형들을 정리하고 하나씩 풀어나가고 있다. 동시에 기본기를 다지기 위해서 강의도 열심히 들었다. 복습과 오답을 꼼꼼하게 하는 것이 더 중요할 것 같다 [ 이코테 강의 ] 다이나믹 프로그래밍 [ 이코테 강의 ] 최단 경로 알고리즘 회고글이 반토막보다 더 짧아진 것 같은 느낌이라면... 반토막보다..더? 회고글 문제는 이분탐색으로 풀 수 있겠다. 아무튼 이 현상은 하루종일 알고리즘과 코딩테스트만 공부하느라 회고라고 할 만한 것들이 없기 때문이다. 기왕 코딩테스트를 준비하니 이 몇 주 동안 실력을 열심히 향상시켜 어떤 문제를 보더라도 후다닥 풀어버릴 수 있는 알고리즘 실력을 가지게 되었으면 좋겠다. 오늘도 화이팅!

[ 이코테 강의 ] 최단 경로 알고리즘

최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미 문제 상황 한 지점에서 다른 한 지점가지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상작동 형실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복 동작 과정 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않..

[ 이코테 강의 ] 다이나믹 프로그래밍

다이나믹 프로그래빙 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운 / 보텀업) 으로 구성된다 (하향식 / 상향식) 동적 계획법이라고도 부름 자료구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 다이나믹 프로그래밍에서 다이나믹은 별다른 의미 없이 사용됨 조건 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 중복되는 부분 문제(Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다 피보나치 수열..

[ 22.04.25 ] 오늘의 회고

⏳ 돌아보기 1. 알고리즘을 정말 잘하고 싶다 알고리즘을 정말 잘하고 싶다 뭐든 못하고 싶은 것 없이 열정만 넘치는 취준생이지만 알고리즘 문제는 정말 잘 풀고 싶다 [ 이코테 강의 ] 정렬 알고리즘 [ 이코테 강의 ] 이진 탐색 [ 백준 2309 ] ( python ) 일곱 난쟁이 오늘도 열심히 백준 문제를 풀고, 인프런 강의를 듣고, 유투브로 강의를 들었지만 눈에 띄는 성장은 없다. 하지만 눈에 보이지 않는 곳에서 열심히 성장하고 있다고 믿는다. 고등학교 때 수학이 그랬듯이 열심히 붙잡고 늘어지다 보면 어느 순간 뭔가 손에 잡힐 것이다. 그 날이 최대한 빨리 왔으면 좋겠다. 첫 코딩테스트를 목전에 둔 지금이 코딩테스트에 온 시간을 바칠 적기인 것 같다. 따라서 이 후 약 2주간의 회고 글은 알고리즘 관..

[ 백준 2309 ] ( python ) 일곱 난쟁이

📚 일곱 난쟁이 문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 출력 일곱 난쟁이의 키를 오름차순으로 출력한다. 일..

[ 이코테 강의 ] 이진 탐색

이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log(작은2)N에 비례한다. 시간 복잡도는 O(logN)을 보장 소스코드 (재귀적 구현) def binary_search(array, target, start, end): if start > end: return None mid = (start + end )// 2 if array[mid] ==target: return mid elif array[mid] >..