프로그래머스

프로그래머스 사이트에서는 AI가 문제 풀이 이력을 분석해서 영역별 능력을 점수로 보여준다. 그리고 이를 바탕으로 다음에 풀 문제도 추천해준다. 일단 문제에 레벨이 표시되어 있어 0레벨과 1레벨 문제부터 싹 풀어버렸고, 추천해주는 문제를 풀어내다 보니 어느 정도 수준에

문제입력의 길이가 최대 1,000,000개이므로 시간초과를 피하려면 $O(n)$ 안에 풀 방법을 찾아야 한다.문제의 표현대로 '최후까지 남기는 것이 가능한 풍선'을 찾기 위해 a를 순회한다고 생각해 보자. a\[i]를 최후까지 남길 수 있으려면 어떤 조건이 필요한가?

문제배열 길이가 2000 밖에 안 되길래 누적합만 구하고 직접 세도 되지 않을까 했는데... 효율성 테스트에서 걸러지고 말았다. 아무리 2000이라도 l, r, m 을 모두 반복문으로 구현하면 $O(n^3)$이니 시간초과가 발생한 모양이다. 시간복잡도를 낮추기 위해 m

문제(2023 KAKAO BLIND RECRUITMENT 1차 코딩 테스트 마지막 문제)완전 탐색으로 풀었다간 시간초과가 날 것이 뻔하므로 일단 문제에 숨어있는 원리를 찾아보려 고민했다. 결국 모든 수는 리프 노드에 들어가므로 중간 과정은 생각할 필요가 없고, 탐색 순

문제Four Fours 퍼즐과 비슷한 형태이나 사용할 수 있는 수가 N으로 주어진다. 최소 개수를 반환하라길래 얼핏 BFS로 푸는 건가 생각했으나 연산 순서 때문에 다이나믹 프로그래밍으로 풀어야 한다는 사실을 깨달았다. (문제 카테고리부터가 동적계획법이다.)top-do

문제모든 부분문자열을 다 검사하면 $O(n^3)$이 되어 효율성 테스트를 통과할 수 없다(고 생각했는데 의외로 된다). 그래서 투포인터 느낌으로 접근해서 가운데에서 점차 늘려가며 최대 길이를 찾아보았다. 길이가 홀수일 수도 있고 짝수일 수도 있다는 점을 유의해야 한다.

문제아이디어는 간단하다. 임의의 노드를 루트로 잡아서 후위 순회를 하는데, 문제에 주어진 방식대로 자식을 0으로 만들기를 반복하여 루트 노드가 0이 되면 누적된 횟수를, 아니면 -1을 출력하면 된다. 그런데 반드시 트리를 이루는 것이 보장되므로 최초 가중치의 합이 0이

문제n이 최대 백만이길래 혹시나 하는 마음으로...알고리즘은 맞는데 아깝게 시간 초과가 걸렸다. 위 방식은 최댓값을 1씩 깎는 방식인데, 이 때 야근 지수가 최소가 됨은 아래에 의해 보장된다.$$V(X)=E(X^2)-{E(X)}^2$$야근 지수는 제곱의 합인데, 단순

문제오늘은 문제가 너무 안 풀려서 잠깐 머리 식힐 겸 글부터 쓰고 있다.일단 문제의 조건을 이해하는 것부터 시작하면, 중위 순회 하면서 노드를 0과 1로 치환해서 얻은 이진수가 트리와 일대일대응 된다. 하지만 직접 순회하기에는 제한 사항이 애매해 보여서 DP로 풀어보고

문제최대 길이가 500,000이므로 $O(n^2)$으로는 불가능하다. 그러니 뭔가 기준을 잡아야 하는데, 교집합의 원소를 기준으로 삼았을 때 스타 수열의 최대 길이는 그 원소 개수의 2배이므로 이를 이용했다. 이런 식으로 집합의 원소 개수가 필요할 때 collectio

문제합, 정렬, 순회를 여러번 해야 해서 깔끔하게 짜기가 어려웠다. 정렬 과정에서 heapq를 쓰긴 했는데 이 문제에서는 곡 수가 최대 10,000이라 내장 sort 함수를 써도 괜찮을 것 같다.분명 어제 스타 수열도 레벨 3, 이 문제도 레벨 3인데 난이도 차이가 상

문제단순 탐색은 절대 불가능... (배열 길이가 최대 200,000인데 단순 탐색하면 $O(nk)$이라 시간 초과되어 효율성 테스트를 통과할 수 없다.)그렇다고 DP도 아닌 것 같고, 슬라이딩 윈도우로도 시간 복잡도는 못 줄일 것 같고... 결국 도저히 어떻게 풀지 모

문제동적계획법으로 풀면 되는데, 집이 원형으로 배열되어 있어 1번째 집과 N번째 집이 서로 이웃한다는 점에 주의해야 한다. 1번째 집을 터는 경우 N번째 집을 털 수 없고, 1번째 집을 털지 않는 경우 N번째 집을 털 수 있다. 그래서 집이 선형으로 배열되어 있다 가정

문제DP로 $O(N)$에 풀었다. i번째 원소로 끝나는 수열의 최댓값을 기준으로 삼았으며, i번째 원소에 1이 곱해지는 경우와 -1이 곱해지는 경우가 있으므로 2차원 배열에 저장했다.만약 i-1번째 원소로 끝나는 수열의 최댓값이 음수라면 i번째 원소부터 더하는 것이 더

문제순서를 알고 있기 때문에 내가 원하는대로 대진을 짝지을 수 있다. 그러므로 크기 순으로 배열한 뒤 하나씩 짝지어 가며 이길 수 있는 숫자 쌍의 개수를 세면 된다.더 지니어스에 나온 흑과 백이라는 게임이 생각나는 문제였다. 물론 이 문제는 수를 내는 순서가 모두 공개

문제배열 길이가 20 밖에 안 되기 때문에 브루트 포스로도 충분히 풀 수 있다.열쇠가 자물쇠 영역을 벗어날 수 있으며 회전할 수 있다는 점에 유의하여야 한다.자물쇠를 좌표축으로 삼고, 열쇠를 회전하고 평행이동하는 모든 경우를 반복하였을 때 자물쇠가 1로만 이루어지는 경

문제효율성 테스트를 통과하기 위해서 알고리즘을 잘 세워야 한다. 투 포인터 알고리즘을 이용해서 통과했다. 구매를 시작하는 진열대와 종료하는 진열대의 인덱스를 각각 포인터로 삼아서 선택된 구간의 보석 수를 딕셔너리로 저장한다. 이때 구매하지 못한 보석이 있다면 오른쪽 포

문제출발 지점만 다르고 도착 지점이 모두 같기 때문에 도착 지점에서부터 BFS로 바로 풀 수 있다.리포트가 새로 발행되는 바람에 갑자기 쉬운 문제를 추천해주는 건가 했는데 이 문제가 의외로 정답률이 39%밖에 안 되는 거였다.

문제 풀이 원본에서 번역이 누락된 조건이 있는데, "한 번 지나간 선 위로 다시 그릴 수 있다". 효율성 테스트는 따로 없지만 좌표가 2차원이고 최대 100,000번 그리므로 시간복잡도를 고려해야 한다. 그리면서 지나간 점과 선의 개수만 세면 오일러 공식을 이용해

문제조건에 따르면 작업을 수행하고 있지 않을 때는 먼저 요청이 들어온 작업부터 처리해야 한다. 작업을 처리하는 동안 요청이 들어오면 따로 저장해 두었다가, 처리 시간이 짧은 작업부터 처리하면 된다. 전체 처리 시간을 줄여야 하는데 대기 중인 작업이 있는 동안 처리하는