잡다로그

[15일차 미들러]문제: https://school.programmers.co.kr/learn/courses/30/lessons/150370Solution복잡한 조건을 따라 한줄한줄 구현하다보면, 날짜 계산 부분에서 급 따져볼 조건이 많아지는 것을 느끼게 된다. 12개월 이상이면 연도가 달라지고, 월도 수의 대소만으로 비교할 수 없다. 깔끔한 구현을 위해서는 조건문을 명료하게 작성해야 한다.function solution(today, terms, privacies) { const [cYear, cMonth, cDay] = today.split(".").map((v)=>+v); const termsMap = {}; terms.forEach((v)=>{ const [term, l..

[12일차] 미들러문제: https://www.acmicpc.net/problem/2631최소 횟수로 정렬하는 문제라고 생각했다. 그러나 아이들을 정렬하여 출력하는 것이 아니라, 옮겨지는 아이들의 '최소 수'를 출력하는 것이 문제의 요구이다. 심지어, 코드를 통해 실제 정렬을 수행하지 않아도 된다.정렬하기 위한 최소 이동 횟수를 구하기 위해서는, 잘못된 자리에 있는 아이들, 즉 제자리로 가야 할 아이들의 수를 구하면 된다.주어진 번호(수열)중 이미 정렬된 번호를 찾기 위해서는 부분 증가 수열을 찾아야 한다. 이를 찾는 데 DP가 활용된다.Solution주어진 수열에 대해 최장 부분 증가 수열을 찾아야, 최소로 움직일 아이들의 인원수를 알 수 있다.LIS 알고리즘이라고 하고, 이 수열을 알아내는 데 DP ..

[11일차 미들러]문제: https://www.acmicpc.net/problem/9655Solution1 혹은 3 중 어떤 것을 가져도 상관없고, 누군가를 이기도록 설계해야 하는 코드도 아니다. 그래서 더 의아했지만, 문제의 문자 그대로 구현하면 되는 쉬운 그리디 문제라고 생각했다. 이 문제가 그리디에 속하는 이유는, 당장의 최적선택(-1 or -3)을 반복하기 때문. 그러나 -1 또는 -3 중 어떤 것을 선택해도 상관이 없어(결과에 영향x), 최적의 해를 선택했다고 보기 어렵다.문제 유형을 굳이 따지자면 DP이다. 나는 그렇게 풀지 않았지만, 코드 하단에 간단한 설명을 적어두었다.const readline = require("readline");const rl = readline.createInter..

그리디 알고리즘 by. 99클럽장 김종범님특징이 많지 않은 알고리즘으로, 오히려 그리디인 것을 모르고 풀었을 때 잘 푸는 경우가 있는 아이러니한 유형 (?). 알고리즘 유형이라기보다 방법론에 가깝다. 그래서 DP, 이분탐색 등 구현법은 다양해진다.'이 문제는 그리디로 풀어야지' 보다 풀다보니 '어 그리디네?' 하는 문제가 많다. 다른 방식들과 많이 결합되어 쓰인다.각 단계에서 현재 상황에서 최선이라고 생각되는 선택을 하는 방식단, 전체의 최적해를 보장하지는 않는다.시간 복잡도는 O(n) ~ O(nlogn)장점빠른 실행 시간 : 일반적으로 한 번의 탐색으로 답을 구할 수 있다.최적화 문제에 적합 : ex. 최단경로, 배낭문제 등메모리 효율성 : 별도의 메모리를 요구하지 않음 (매순간 최적 판단)단점최적해를..