알고리즘

탐욕알고리즘(Greedy)

탐욕알고리즘이란? - 최적의 해에 가까운 값을 구하기 위해 사용됨 - 여거 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 ,최종적인 값을 구하는 방식 탐욕 알고리즘의 예 문제1 : 동전문제 지불해야한느 값이 4720원 일 때 1원 50원 100원 500원 동전으로 동전의 수가 가장 적게 지불하기오. - 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식으로 구현가능 - 탐욕알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 해결방법 coin_list = [500, 100, 50, 1] def main_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sor..

[python] 프로그래머스 > 스택/큐 > 주식가격

1) 첫번째 시도 : pop을 사용하였고, for문 안에 모든 경우의 수를 일일이 적어주었다. -> 시간초과 2) 두번째 시도 : collections의 deque를 사용하였다. for문 안에 조건을 조금 줄였다. --> 시간초과 3) 세번째 시도 : append()를 쓰면 느리다는 글을 보고 수정 --> 시간초과 4) 네번째 시도 : 도저히 모르겠어서 구글에 찾아본 결과 pop() 또는 deque()를 사용하면 더 느리다는 글을 보고 변경 --> 시간초과 4) 이게 진짜 답!!! : break를 하기 전 이미 1을 더한 상태이므로 answer[i]가 1임을 굳이 명시해주지 않아도 됨을 깨닳음 -> 삭제 -> 성공 왜 큐/스택문제라고 굳이 해놨는지 잘 모르겠다... 당연히 pop()을 사용해야할 줄 알았다.

[python] 프로그래머스 > 멀쩡한 사각형

문제 설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solutio..

DP- 1로 만들기

- 정수X에 사용할 수 있는 연산은 다음과 같이 세 가지 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. - 어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 구하는 문제 [Top-Down 방식] int go (int n){ if(n==1) return 0; if(d[n] > 0) return d[n]; d[n] = go(n-1) + 1; if(n%2 == 0){ int temp = go(n/2) + 1; if(d[n] > temp) d[n] = temp; } if(n%3 == 0){ int temp = go(n/3) + 1; if(d[n] > temp) d[n] = temp; } retu..

다이나믹 프로그래밍

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 - 문제에는 크기가 있어야함 - 각각의 작은 문제를 풀고 원래대로 합친다. - Dynamic에 대한 어떠한 의미도 없음 -> 헷갈리지마셈 ㅎㅅㅎ - 다이나믹 알고리즘 : 작은 문제가 중복가능 - 분할정복 알고리즘 : 작은 문제가 중복되지 않음 1. Overlapping Subproblem : 부분문제 겹친다. 2. Optimal Substructure : 최적 부분 구조 * 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. * 문제의 정답을 작은 문제의 정답에서 구할 수 있다. * 문제를 작은 문제로 쪼갤 수 있다. * 예시(피보나치 수) - 문제 : N번째 피보나치 수를 구하는 문제 - 작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피..

그래프의 탐색(DFS, BFS)

그래프 탐색의 목적 : 임의의 시작점 x에서 시작해서 모든 정점을 한번씩 반복하는 것 1. DFS(깊이우선탐색) - 한 시작점에서 갈 수 있을때 까지 계속진행하다 뒤도돌아오고 다시 갈수있는데 까지 감 - 스택사용해서 갈 수 있는 만큼 최대한 많이가고 - 갈 수 없으면 이전 정점으로 돌아간다. - 재귀호출을 이용해서 구현할 수 있다. // dfs(x) : x에 방문했다는 의미 // 인접 행렬 void dfs(int x){ check[x] = true; printf("%d",x); for(int i=1; i

그래프와 BFS

- 정점 : (Node, Vertex) - 간선(Edge) : 정점간의 관계를 나타낸다. - 그래프 : 정점과 간선이 있는것 - 경로 : 간선의 연속(시작점 ~ 도착점 까지 정점을 거쳐 감) - 최단경로 : 그래프의 경로 중 가장 짧은 것 - 사이클 : 경로인데, 시작점과 도착점이 같은 것 - 단순 경로/사이클 : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클 (특별한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말한다.) - 간선은 방향이 있을 수도 있고, 없을 수도 있다. - 방향이 없는 그래프 : 양방향 그래프 (서로 오갈 수 있음) - 방향이 없는 그래프는 저장을 할 수 없기 때문에 각 방향당 하나씩 총 두개 저장해 줘야 한다. - 간선이 여러개일 수..

[python] 프로그래머스 > level1 > 자연수 뒤집어 배열로 만들기

map(int,값)을 주면 값이 int로 변환되는 것을 알게되었다. 그리고 return에 한번에 주니 확실히 깔끔해 보이는것 같다. map과 list는 파이썬에서 자유자재로 바뀌어서 편리한 것 같다.