🌻 algorithm

창의력(=최소한의 아이디어 떠올림)판단력(=현재 상황에서 가장 좋아보이는것을 선택해도 문제를 풀 수 있는 것을 보장하는가) 를 요구한다.거스름돈 문제가 그리디로 해결 가능한 이유는가지고 있는 동전 중에서 큰 단위 = 항상 작은 단위의 배수.그러므로 작은 단위의 동전들을

핵심) 배열의 원소를 N번 더하여 갖아 큰 수 만들기특정 원소는 k번 초과하여 더해질 수 없음서로 다른 인덱스의 수가 같을 때 = 서로 다른 것으로 간주k는 M보다 항상 작거나 같다배열의 크기 N, 숫자 더해지는 횟수 M, 제한 K일때 위 법칙에 따라 더해진 값을 출력

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'풀이는 떠올리기 쉽지만 소스코드로 옮기기 까다로운 문제' 등이 구현문제이다모든 경우의 수를 주저없이 다 계산하는 해결방법문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행해야하는 문제파이썬과 함께라면 C/C++보다는

뭔가 BFS, DFS 도 그렇고n \* m 판에서 움직이는 경우가 코드로 구현했을때 거의 틀이 있는 것 같다. 입력예시)5R R R U D D출력예시 )3 4대충 정리하면이렇게 움직였을때 바둑판 어디에 위치하는지 출력해야한다.바둑판 범위를 벗어나서는 안된다코드거의 이

결론) 캐릭터가 방문한 칸의 수 출력움직임 메뉴얼 1) 현재 위치에서 현재 방향 기준으로 왼쪽방향부터 차례대로 갈 곳 정함 2) 캐릭터의 바로 왼쪽에 가보지 않은 칸이 존재하면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진. 왼쪽 방향에 가보지 않은 칸이 없

결론) 나이트의 위치가 주어졌을때, 나이트가 이동할 수 있는 경우의 수는?8\*8 체스판임이동은 두가지 중 하나 1) 수평 2칸 -> 수직 1칸 2) 수직 2칸 -> 수평 1칸범위에서 벗어나는지 체크하는게 중요하겠군오~ 맞았다\~~

처음부터 끝까지 찾을때까지 순서대로 조회당연히 최악의 시간복잡도는 O(N)조건 : 데이터는 이미 정렬되어있어야한다. ➡️ 이진탐색트리와의 연관필요 : 시작점, 끝점, 중간점찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터 찾기시간복잡도 :

핵심) 손님이 요청한 부품번호가 리스트에 있으면 yes, 없으면 noinput ex)내가 가지고 있는 것N = 58,3,7,9,2손님이 찾는 것M = 35,7,9input 조건)정수 1<=N<=1,000,000정수 1<=M<=1,000,000다량의

핵심) 절단기에 설정할 수 있는 높이의 최댓값을 구하시오 적어도 합쳐서 M만큼의 썰린 떡을 얻어야한다.첫줄에 떡의 갯수 N과 요청한 떡의 길이 M이 주어진다 (1<=N<=1,000,000 1<=M<=2,000,000,000)둘째줄에 떡의 개별

다익스트라사용 : 특정노드에서 다른 모든 노드로의 최단 경로를 구함전제조건 : weight가 음수일 수 없음시간복잡도 : 플로이드워셜사용 : 전제조건 : 시간복잡도 : 동작원리1\. 출발노드 설정2\. 최단거리 테이블 초기화3\. 방문하지 않은 노드 중 최단거리가 가장

플로이드워셜사용 : 모든 지점에서 다른 모든지점까지의 최단경로 모두 구하는 경우전제조건 : 시간복잡도 : O($$N^3$$)구현개념 : \|$$D{ab}=min(D{ab}, D{ak}+D{kb})$$= min(A에서 B로가는 최소비용, A에서 K를 거쳐 B로가는 최소비

점화식 : $$a{n+2}=f(a{n+1}, an) = a{n+1}+a_n$$실제 구하는 과정코드이때의 시간 복잡도 : $$O(2^N)$$동일한 함수가 반복적으로 호출되기 때문이다!예시 ) fibo(6) 호출시 \-> 낭비. 비효율적.재귀함수를 사용해서 만드는게 끝이

1로 만들기 이코테 책 217p 문제 시간제한 1초 입력 정수 X (1<=X<=30,000) 출력 연산을 하는 횟수의 최솟값 문제 요약 주어지는 정수 X에게 사용 가능한 연산은 4가지 X가 5로 나누어떨어지면, 5로 나눔 X가 3로 나누어

정렬 데이터를 특정한 기준에 따라서 순서대로 나열하는 것데이터를 정렬해두면 이진탐색이 가능해진다.대표적으로선택정렬삽입정렬퀵정렬계수정렬선택정렬가장 작은 데이터를 선택해, 맨 앞에 있는 데이터와 바꾸고그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복

제한시간 : 1초 메모리 : 128MB입력첫째줄에 수열에 속해있는 수의 갯수 N (1&lt;=N&lt;=500)둘째줄부터 N+1번째 줄까지 N개의 수 입력. (1&lt;=수&lt;=100,000)출력입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출

그래프 이론 을 참고하자!그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘1\. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.2\. 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으

이코테 149p 제한1초 / 128MB입력얼음틀 세로길이 N, M (1&lt;=N, M&lt;=1,000)2줄~N+1줄까지 얼음틀 형태 주어짐 (0=구멍, 1=그렇지 않음)출력한번에 만들 수 있는 아이스크림의 갯수 출력예시N \* M 크기의 얼음 틀이 있다.구멍이 뚫린

귀찮지만 dictionary로 구현하여 더 빠르게 돌리고싶었는데 오히려 더 느리게 나왔다.사용 알고리즘 \- 나 : bfs모범 : dfs사용 자료구조 \- grpah 정보를 기록 \- 나 : dictionary ( 더 빠를줄....)모범 : 2차원 list시간