최적의 솔루션을 도출하는 두 가지 알고리즘-Greedy, DP-에 대해서 차이점을 중심으로 알아본다. 스스로 헷갈려서 차이점을 명확히 구분하고 공부하기 위해 적는 포스팅이다. Greedy AlgorithmGreedy Algorithms: These algorithms make a series of choices, one after another, selecting the best option available at each step without reconsidering previous decisions. Each decision is final, meaning that once a choice is made, the algorithm does not go back to revisit or alter i..
>> 공통점 : visited check Depth-First Search (DFS)DFS explores as far as possible along each branch before backing up. It typically uses a stack data structure (either explicitly or via recursion) to keep track of the nodes to be visited. Here’s how it works:Start at the selected node (typically the root in a tree).Mark the node as visited and push it onto the stack.Go to an adjacent unvisited nod..
문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr TIL경우의 수가 너무 많아서 시간복잡도 및 공간복잡도가 좋지 않을 것으로 생각했지만, DP의 경우 어쩔 수 없는 느낌O(n^2)까지는 그냥 가자문제에서 8이상이면 모두 -1 처리를 하라고 했기 때문에 복잡도를 생각하지 않아도 됐음이런 식으로 피보나치 느낌의 문제들은 DP 먼저 생각하기 !! # dp-tabulation def solution(N, number): tabu = [-1 for i in range(number)] ..
문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr TIL순서가 유지되어야하는 경우, 스택/큐 사용어차피 큰 수를 결정하는 데 가장 앞 숫자가 제일 중요하기 때문에 앞에서부터 없애도 괜찮음숫자를 이용해 큰 수 혹은 작은 수를 만드는 경우, 스택을 사용한 그리디 풀이 외우기앞에서 pop한 작은 수가 뒤에서 다시 push 될 수 없음 (그럼 가장 큰 수가 될 수 없음) > Greedy Codedef solution(number, k): answer = [] # 결과로 반환할 숫자..
문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr TIL여러 개 항목을 신경써야하는 경우, 독립적으로 계산하기 (커서 이동 횟수, 알파벳 변경 횟수 각각 따로)동적으로 최솟값을 찾아야 하는 경우, 기준을 생각해보기단어의 길이에 따라 다른 경우, 중간을 기준으로 각각 Min값 처리가 달라질 수 있음한 번 선택한 경우 or 순서대로 처리하는 경우, 다시 고려하지 않아도 됨 > Greedy한 번 지나간 문자의 경우, 다시 되돌아가지 않아도 됨 (어차피 왼-오 순서로 처리 + 각 문자별..
⭐️ 나중에 잊을 때쯤 다시 풀어볼 문제 ⭐️ 초기 접근 방법 ❗️처음에 생각한 방향 스택을 사용하는 것이 가장 적합하다고 판단되어 stack array를 따로 만들고 해당 stack[sp]와 주어진 배열 asteroids[i]의 비교를 통해서 구현하려고 함 [ 처음 코드 ] int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){ int top=-1; int* stack = (int*)malloc(asteroidsSize*sizeof(int)); stack[++top] = asteroids[0]; for(int i=1; i
