본문 바로가기

Algorithm6

[이것이코딩테스트다] 최대한 복잡도가 낮게 챕터 1을 읽으며 깨달은 꿀팁들은 정리하겠다 1. 모든 2중 반복문의 시간 복잡도가 O(N^2)은 아니다만약 소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 한다 2. 최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다 3. 시간복잡도 분석은 문제풀이의 핵심이다. 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있다 N N N N 4. 코테에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다. 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다 2025. 2. 7.
[알고리즘] 동적계획법에 대해 산모양 타일링을 DP로 그렇게 간단히 푸는 것에 적잖이 충격을 받아, 동빈나님 유튜브를 참고하여 비슷한 유형의 문제를 여러개 풀면서 감을 잡았다 다이나믹 프로그래밍(Dynamic Programming)컴퓨터적인 사고력이 중요!하나의 문제는 단 한 번만 풀도록 하는 알고리즘점화식을 사용한다큰 문제를 작은 문제로 나눌 수 있습니다작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일합니다👉 이것을 만족한다면 DP를 고려하자!메모이제이션을 통해 중복 연산을 제거예시 ) 피보나치 수열D[i] = D[i-1] + D[i-2]// 인덱스값을 구한다면? int dp(int x) { if (x == 1) return 1; if (x == 2) return 1; return dp(x - 1.. 2025. 2. 4.
[프로그래머스][JAVA] lv3. 산 모양 타일링 제 의도는 이러했습니다물론 DFS호출을 남발하여 그림대로 실행되지는 않았습니다 1. 정삼각형 타일로 덮기2. 위에 정삼각형이 있다면, 다이아로 덮기1) 다시 남은 타일은 정삼각형으로2) 혹은 다이아, 평행사변형으로 ...3. 다이아를 선택하지 않는 경우 평행사변형으로1) 다시 남은 타일은 정삼각형으로2) 혹은 다이아, 평행사변형으로 ... 이러한 깊이 탐색을 원했습니다 어떻게 고쳐야 할까요? https://tech.kakao.com/posts/610 2024 카카오 겨울 인턴십 코딩테스트 문제해설 - tech.kakao.com안녕하세요, 카카오에서 계정시스템 개발을 맡고 있는 잭입니다. 2024 카카오 채...tech.kakao.com해설을 보니 더 우울해졌습니다아 ....다이나믹프로그래밍이었군요...... 2025. 2. 2.
[프로그래머스][JAVA] lv2. 도넛과 막대 그래프. 문제 참고https://school.programmers.co.kr/learn/courses/30/lessons/258711 위 주석처리된 입력 케이스들은 모두 성공.그러나, 런타임 오류가 있었다 . . .public class DoughnutAndStick { public static void main(String[] args) { DoughnutAndStick doughnutAndStick = new DoughnutAndStick();// int[][] edges = new int[][]{{4, 11}, {1, 12}, {8, 3}, {12, 7}, {4, 2}, {7, 11}, {4, 8}, {9, 6}, {10, 11}, {6, 10}, {3, 5}, {11, 1},.. 2025. 1. 31.

티스토리툴바