코딩테스트 문제를 풀 때, 입력의 크기 n에 대해 시간초과가 나지 않도록 알고리즘을 고려해야 한다.이 사실을 알고 있지만, 항상 특정 시간복잡도에 대해 n의 크기를 어느정도까지 가져갈 수 있는지를 까먹어 해당 글을 작성하게 됐다. 1️⃣ 입력의 크기에 따른 시간복잡도입력의 크기시간복잡도대표 알고리즘n \[O(n!)\]완전탐색n \[O(2^n)O(n^2*2^n)\]Bitmask DPn \[O(\sqrt{2}^n)\]MITMn \[O(n^3)\]Matrix Chain Multiplication(행렬 곱셈)n \[O(n^2)\] n \[O(n\sqrt{n})O(n\log^{2}n)\]모스(Mo's) 알고리즘n \[O(n\log n)\]정렬, LIS(최장 증가 부분 수열)n \[O(n)\]DP, DFS, Tre..
해당 글에서는 입국심사 문제를 Python을 이용해 풀이하고자 한다. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🔷 문제 설명더보기이 문제는 이분탐색에 관련된 문제다.코딩테스트를 보기에 앞서 평소에 이분탐색 문제인 것을 알아내는데 어려움을 느껴 연습하는 시간을 가지고자 해당 문제를 풀게 됐다. 🔷 문제 풀이만약 이 문제가 이분탐색인 문제라는 걸 몰랐다면 어떻게 접근했어야 할까?이분탐색이라는 것의 힌트는 바로 입력의 크기이다. 해당 문제에서 입국심사를 기다리는 사람의 최댓값과 한 명을 심사하는데 걸리는 최대 시간은 1,000,000,000이다. 따라서 ..
해당 글에서는 단어 변환 문제를 Python을 이용해 풀이하고자 한다. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🔷 문제 설명더보기 🔷 문제 풀이처음엔 완전 탐색을 이용해 문제를 푸려고 했다.combination을 이용해 words의 방문 순서를 정하고, 방문 순서에 따라 한 글자씩 차이나는지 아닌지를 통해 모든 경우를 탐색하고 최솟값을 찾으려고 했다. 하지만 시간초과가 발생하는 것을 확인했다. 해당 문제는 알고리즘 고득점 Kit에 있는 문제이기 때문에 카테고리가 깊이/너비 우선 탐색이라는 것을 알고 있었지만, 마땅히 풀이 방식이 떠오르지 않아서 구..
해당 글에서는 줄 서는 방법 문제를 Python을 이용해 풀이하고자 한다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔷 문제 설명 더보기 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러 가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다. [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을..
