https://www.teferi.net/ 2026-05-07T20:36:10+00:00 https://www.teferi.net/ https://www.teferi.net/_media/wiki/dokuwiki.svg text/html 2021-03-02T04:17:12+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/1843?rev=1614658632&do=diff 사칙연산 풀이 * 행렬 연쇄 곱셈 문제와 비슷한 방식으로 DP를 이용해서 O(n^3)에 푸는 방법이 쉽게 떠오른다. 공식 해설조차도 이 방법을 답으로 제시하고 있다 * 그러나 사칙 연산의 특성을 이용하면 훨씬 간단한 방법으로 O(n)에 푸는 것이 가능하다. text/html 2021-01-22T06:32:34+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/1844?rev=1611297154&do=diff 게임 맵 최단거리 풀이 * 그냥 전형적인 BFS문제. 따로 신경쓸것은 없고 그냥 BFS를 적용하면 된다. * V와 E가 모두 O(n*m) 인 형태이므로 시간 복잡도는 O(n*m) * BFS로 순회하면서 방문하는 노드를 yields 하는 제너럴한 함수를 만들면서 구현했는데, 만들어 놓고 나니 저게 정말 다른 문제들 풀때도 유용할지에 대한 의구심이 들었다. 그래서 이 함수를 teflib에 추가하는 것은 보류.. text/html 2021-01-21T16:10:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/1845?rev=1611245409&do=diff 폰켓몬 풀이 * 요구하는 내용은 매우 간단한데, 문제를 괜히 길게 써놓아서, 프로그래밍 스킬보다도 국어 스킬이 더 필요해보이는 문제 * 포켓몬의 종류가 가져갈 수 있는 수보다 많으면, 다 다른 종류로 가져갈 수 있으니 가져갈 수 있는 수가 답이고, 종류가 그보다 적으면 그게 답이다. text/html 2021-07-10T18:11:36+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/2021_%EC%B9%B4%EC%B9%B4%EC%98%A4_%EC%B1%84%EC%9A%A9%EC%97%B0%EA%B3%84%ED%98%95_%EC%9D%B8%ED%84%B4%EC%8B%AD?rev=1625940696&do=diff 2021 카카오 채용연계형 인턴십 Nothing found text/html 2021-07-08T16:16:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/2021_dev-matching_-_%EC%9B%B9_%EB%B0%B1%EC%97%94%EB%93%9C_%EA%B0%9C%EB%B0%9C%EC%9E%90_%EC%83%81%EB%B0%98%EA%B8%B0?rev=1625761014&do=diff 2021 Dev-Matching: 웹 백엔드 개발자(상반기) * 행사 정보는 여기. 공식 해설은 여기 에서 볼수 있다. * 코딩 문제 3문제 외에도 SQL문제 한 문제가 더 있다. * 문제 구성은 1~3레벨 한문제씩으로 난이도는 어렵지 않고, 그나마도 알고리즘보다는 구현 문제에 가까운 문제들이다. text/html 2021-01-30T14:23:27+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/2021_kakao_blind_recruitment?rev=1612016607&do=diff 2021 KAKAO BLIND RECRUITMENT * 2020년 9월 12일 토요일 오후 2시부터 7시까지 5시간 동안 열렸던 테스트이다. * 공식 해설은 카카오 테크 블로그에 올라와 있다. * 구현이 귀찮은 문제들이 많고, 사이트 내의 다른 문제들에 비해서는 레벨이 좀 낮게 측정된 느낌이다. text/html 2021-07-31T16:34:47+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12900?rev=1627749287&do=diff 2 x n 타일링 풀이 * BOJ의 2×n 타일링과 동일한 문제. 풀이는 그쪽 참고. 코드 * Dependency: teflib.combinatorics.fibonacci 프로그래머스 ps:problems:programmers:level_3 text/html 2021-07-31T16:10:50+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12902?rev=1627747850&do=diff 3 x n 타일링 * BOJ의 타일 채우기와 동일한 문제이다 풀이 * 타일 채우기 참조. 코드 * Dependency: teflib.combinatorics.linear_homogeneous_recurrence 프로그래머스 ps:problems:programmers:level_4 text/html 2021-07-04T14:25:18+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12904?rev=1625408718&do=diff 가장 긴 팰린드롬 풀이 * 가장 긴 팰린드롬 부분문자열 (Longest Palindromic Substring)을 참고. Manacher's algorithm을 이용해서 O(n)에 풀 수 있다. 코드 * Dependency: teflib.string.palindrome_radiuses 프로그래머스 ps:problems:programmers:level_3 text/html 2021-01-25T14:05:29+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12907?rev=1611583529&do=diff 거스름돈 * 많은 교과서의 2차원 DP 챕터에서 연습문제로 자주 보이는 유명한 문제이다. 풀이 * dp[m][n]을 money[0]부터 money[m]까지의 화폐를 가지고 n원을 만들 수 있는 방법의 수라고 하자. text/html 2021-07-16T15:51:58+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12911?rev=1626450718&do=diff 다음 큰 숫자 풀이 * 그리디하게 생각하자. 2진수 표현을 기준으로 최하위비트부터 스캔하면서, 현재 비트는 1이고 상위 비트는 0이 되는 위치를 찾는다. 그렇게 찾아낸 것이 하위 n번째 비트였다고 하자. n번째 비트와 n+1번째 비트의 값을 바꾸고, 0~(n-1)번째까지의 비트를 뒤집어주면 원하는 값이 된다. text/html 2021-09-27T12:39:57+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12915?rev=1632746397&do=diff 문자열 내 마음대로 정렬하기 풀이 * 그냥 주어진 기준에 맞춰서 정렬하면 끝나는 문제. n번째 글자로 비교하고 그게 같으면 문자열 전체로 비교하니까, 그대로 튜플을 만들어서 키로 넘겨주면 된다. text/html 2020-12-23T16:41:38+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12916?rev=1608741698&do=diff 문자열 내 p와 y의 개수 풀이 * 기초적 문제. 그냥 시키는 대로 하면 된다. 시간은 O(n) 코드 프로그래머스 ps:problems:programmers:level_1 text/html 2021-01-21T05:54:48+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12920?rev=1611208488&do=diff 선입 선출 스케줄링 풀이 * 먼저 n번째 작업이 시작되는 시간을 파라메트릭 서치를 통해서 구하고, 그것으로부터 몇 번 작업인지를 구한다. * f(t)를 t시간까지 시작된 작업의 갯수라고 하면, 이것을 구하는 것은 간단하다. text/html 2021-06-21T11:34:25+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12922?rev=1624275265&do=diff 수박수박수박수박수박수? 풀이 * 그냥 시키는대로 짜면 된다. 딱히 쓸말도 없다. 시간복잡도는 O(n) 코드 프로그래머스 ps:problems:programmers:level_1 text/html 2021-01-21T15:31:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12923?rev=1611243114&do=diff 숫자 블록 풀이 * 문제를 잘 이해한 뒤 다시 정리해보면. begin부터 end까지의 각 수에 대해서, 자기 자신을 제외하고 가장 큰 약수를 찾으라는 문제이다. * 정확히는 10,000,000 이하의 가장 큰 약수.. text/html 2021-06-10T14:18:56+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12928?rev=1623334736&do=diff 약수의 합 풀이 * 어떤 수의 모든 약수의 합을 구하는 것은, 그냥 모든 약수를 다 구해서 더하는 것이 가장 평범하고 빠르다. * 정수론적 함수 참고. * i를 1부터 sqrt(n)까지 증가시키면서, n이 i로 나누어 떨어지면 i와 n/i 는 모두 n의 약수이다. text/html 2021-01-22T06:37:07+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12929?rev=1611297427&do=diff 올바른 괄호의 갯수 * 카탈랑 수를 해로 갖는 대표적인 문제 풀이 * 마지막 위치에는 닫는괄호())가 와야 한다. 이 괄호와 매칭되는 여는 괄호(()가 i번째에 있는 경우들로 나눠서 생각할 수 있다. text/html 2021-07-16T15:32:44+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12930?rev=1626449564&do=diff 이상한 문자 만들기 풀이 * 그냥 기초적인 구현 문제. * split()를 이용해서 단어별로 쪼개서 단어별로 변환한 뒤에, ' '.join(..)으로 합치는 것은, 공백문자가 여러개 이어서 나올 경우를 처리해주지 못한다 text/html 2021-06-29T13:28:56+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12931?rev=1624973336&do=diff 자릿수 더하기 풀이 * 10으로 나눠가면서 나머지 값들을 모두 더해도 되고, 그냥 전체를 문자열로 변환하고 각 자리수를 다시 정수로 변환해서 합을 구해도 된다. 좀더 코딩이 짧은 후자로 처리. text/html 2021-07-08T15:56:26+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12937?rev=1625759786&do=diff 짝수와 홀수 풀이 * 그냥 기초 코드 프로그래머스 ps:problems:programmers:level_1 text/html 2021-06-21T11:27:16+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12939?rev=1624274836&do=diff 최댓값과 최솟값 풀이 * 제목은 최댓값과 최솟값으로 맞춤법을 잘 지켰지만, 문제 설명에는 최대값, 최소값으로 잘못 적혀있다. * 그냥 시키는 대로 처리하면 된다. 문자열을 나누고, 각각을 int로 바꾸고, 최댓값/최솟값을 찾고, 다시 문자열로 변환해서 리턴. text/html 2021-03-04T14:06:08+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12942?rev=1614866768&do=diff 최적의 행렬 곱셈 풀이 * 동적 계획법의 유명한 문제인 연쇄 행렬 곱셈문제이다. * O(nlogn) 알고리즘이 최적으로 알려져 있지만, 여기에서는 교과서에서 알려주는 O(n^3) 알고리즘으로 풀었다. * 추후에 O(nlogn) 알고리즘을 구현해보고 업데이트 예정. text/html 2021-07-08T15:50:39+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12949?rev=1625759439&do=diff 행렬의 곱셈 풀이 * 그냥 기초적인 행렬 곱셈 문제. * 이론적으로는 슈트라센 알고리즘등을 사용하면 좀더 시간복잡도를 줄일수 있지만 (O(n^3)을 O(n^2.8)정도로..), n이 100정도의 범위에서는 별 의미가 없을 듯 해서 그냥 단순한 방법으로 구현. text/html 2021-01-21T15:32:22+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12971?rev=1611243142&do=diff 스티커 모으기(2) * 같은 프로그래머스 사이트에 있는, 도둑질과 동일한 문제이다. * 문제 이름이 스티커 모으기(2) 인데, 정작 스티커 모으기(1)은 사이트에서 찾을 수가 없다. 풀이 * 도둑질 참고 * text/html 2022-01-04T17:10:32+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12973?rev=1641316232&do=diff 짝지어 제거하기 풀이 * 스택을 이용한 괄호쌍 매칭 문제의 변형 * 현재 문자가 스택의 top과 일치하면 pop하고, 다르다면 push해주기만 하고, 문자열을 모두 처리했을때 스택에 남은것이 없는지만 확인하면 된다 text/html 2021-01-21T15:24:36+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12983?rev=1611242676&do=diff 단어 퍼즐 풀이 * n = 문자열 t의 길이, m = 배열 strs의 크기, k = 단어 조각의 길이 * dp[i] 를 t[:i+1]을 만들기 위해 사용하는 최소의 단어 수라고 하면, 간단히 점화식이 세워진다. * dp[i] = min_k(dp[i-k] + 1), where t[i-k:i+1]∈strs text/html 2021-01-21T16:07:58+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12984?rev=1611245278&do=diff 지형 편집 풀이 * 인풋이 N*N 크기의 2차원 배열로 들어오지만 별 의미는 없다. 길이가 N^2인 1차원 배열로 들어오는 것과 풀이하는 데에는 아무 차이가 없다. * 주어진 N^2개의 높이를 정렬한 것을 h라고 하자. $i$$n^2-i$$h[i-1]$$cost(h[i-1])$$cost(t)$$i$$t-h[i]$$n^2-i$$t-h[i]$$\begin{align} cost(h[i-1]) & = cost(t) - i\times (t-h[i-1])P + (n^2-i)\times (t-h[i-1])Q \\ & = cost(t) - (t-h[i-1])\times((P+Q)i-Qn^2) \end{align}$h[i]$$cost(h[i])$$cost(t)$$i$$h[i]-t$$n^2-i$$h[i]-t$$\begin{align} cost(h[i]) & = cost(t) + i\times (h[i]-t)P - (n^2-i)\times (h[i]-t)Q \\ & = cost(t) + (h… text/html 2022-03-18T15:50:26+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/12985?rev=1647618626&do=diff 예상 대진표 풀이 * a, b가 다음 라운드에서 몇번째 조에 배치되는지를 계산하는 것을 반복하다가 같은 조에 배치되면 종료하면 된다. * 조 번호를 1-based로 계산하면 다음 라운드에서의 조는 a = (a+1)//2 와 같은 식으로 써야 한다. 하지만 처음에 a와 b에서 1을 빼주고 0-based로 계산을 시작하면 그냥 a//=2 로 업데이트 하면 되므로 좀더 편하다. 어떻게 하든 시간 복잡도는 O(logn)이 된다.… text/html 2022-01-10T02:21:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/17677?rev=1641781277&do=diff [1차] 뉴스 클러스터링 풀이 * 그냥 시키는대로 구현하면 되는 문제 * 파이썬에서는 collections.Counter을 다중집합처럼 사용할수 있다. 교집합과 합집합도 쉽게 구할 수 있다. python 3.10 이상에서는 원소의 총 갯수도 바로 구할수 있는 total() 메소드도 제공하지만, 프로그래머스에서는 아직 지원하지 않아서 그냥 sum으로 구했다. text/html 2021-01-21T05:22:43+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/17685?rev=1611206563&do=diff [3차] 자동완성 풀이 * 친절하게도 문제에 해설링크가 걸려있다. 해설은 좀 짧막하게 써있지만, 트라이 (Trie)를 쓰는 방법과 소팅을 쓰는 방법이 있다는 힌트만 있으면 사실 해법은 쉽게 나온다. * 문제에서 요구하는 것은, 각각의 단어에 대해서, 다른 단어와 공유되지 않는 가장 짧은 접두사의 길이를 구하는 것. text/html 2022-05-03T09:51:38+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42576?rev=1651571498&do=diff 완주하지 못한 선수 풀이 * BOJ의 배부른 마라토너과 완전히 동일한 문제이다. * 기본적으로는 사람마다 등장 횟수를 세어서, participant쪽의 등장 횟수가 completion쪽의 등장 횟수보다 많은 사람을 찾으면 되는 매우 간단한 문제이다. python에서는 collection.Counter을 쓰면 구현도 매우 간단하고 ( text/html 2021-05-22T17:36:11+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42577?rev=1621704971&do=diff 전화번호 목록 풀이 * BOJ의 전화번호 목록와 동일한 문제. 풀이는 그쪽 참고. 코드 프로그래머스 ps:problems:programmers:level_2 text/html 2021-07-26T17:25:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42578?rev=1627320353&do=diff 위장 풀이 * 패션왕 신해빈와 동일한 문제. 문제의 원 출처는 Benelux Algorithm Programming Contest 2013이다 * 의상의 종류가 i가지이고, 각 종류별로 n1,n2,n3,...,ni 개의 의상이 있다고 하면, 가능한 조합의 갯수는 n1*n2* text/html 2021-05-22T17:38:14+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42579?rev=1621705094&do=diff 베스트앨범 풀이 * 풀이 자체는 그냥 시키는 대로 구현하면 된다. * 그냥 이것저것 조건이 많아서 구현이 조금 지저분해지기 쉬운데, 어떻게 하면 좀 더 깔끔해질지를 생각할 여지는 있다 text/html 2021-05-21T07:16:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42583?rev=1621581414&do=diff 다리를 지나는 트럭 풀이 * 다리 위에 있는 트럭들을 큐로 관리해주면 쉽게 처리되는 문제이다. * 그것을 나이브하게 풀면, 매 초마다 새 트럭이 다리에 올라갈수 없는 경우에 무게 0짜리의 가상 트럭을 대신 다리에 올리는 것처럼 구현할 수 있고, 이 경우에는 전체 걸린 시간, 즉 O(n*m)에 풀린다 (n=트럭의 갯수, m=다리의 길이). 비효율적이지만, 정답에 올라가있는 대부분의 코드가 이러한 방식으로 구현되어있다. (코드 1)… text/html 2021-05-21T07:11:14+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42584?rev=1621581074&do=diff 주식가격 풀이 * 스택에는 아직 감소하지 않은 주식가격들을 저장하고 있는 것이 기본적인 풀이법. 이렇게 하면 증가하는 순서로 스택이 유지된다. 흔히 쓰이는 테크닉이다. * 시간 복잡도는 모든 원소를 한번씩 스택에 추가/삭제하므로 O(n)이 된다. text/html 2021-05-21T07:25:28+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42586?rev=1621581928&do=diff 기능개발 풀이 * 그냥 주어진대로 작성하면 끝. 이전 작업보다 현재 작업이 빨리 끝나면, 현재 작업은 이전 배포 예정일에 배포된다. 그렇지 않으면 현재 작업은 새로운 배포 날짜가 추가되어 그날 배포되게 된다. text/html 2021-08-12T09:09:13+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42587?rev=1628759353&do=diff 프린터 풀이 * 1966과 동일한 문제. * n 제한이 워낙 작아서 어떤 식으로 풀든지, 풀리기는 한다 * 시키는대로 계속 큐에서 로테이트 시키는 방식으로 시뮬레이션 하면서 처리한다면, 맨 앞의 문서가 가장 중요한 문서인지를 O(1)에 처리한다고 해도 (카운터 등을 써서..) 전체적으로 O(n^2)이 걸린다. text/html 2021-05-28T03:10:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42626?rev=1622171454&do=diff 더 맵게 풀이 * 그냥 시키는 대로 구현하면 되고, 그 때 쉽게 떠오르는 방법은 우선순위 큐 (Priority Queue)를 쓰는 것. 코딩테스트 고득점 Kit에서도 우선순위큐의 연습문제로 분류되어있다. * 최솟값 우선순위 큐에 값들을 다 넣어놓고, 최솟값 두개를 pop 하고, 그것을 섞어서 만든 새 값을 push 하는 것을 반복하면 된다. pop과 push는 모두 O(logn)이고, 이것을 최대 n번 하므로 시간복잡도는 O(nlogn)… text/html 2021-05-28T03:11:10+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42627?rev=1622171470&do=diff 디스크 컨트롤러 풀이 * 일종의 스케쥴링 문제이다. 보통 그리디로 많이 풀리기는 하는데, 조건이 조금씩 바뀔때마다 어떤 것을 먼저 선택해야 할지 기준도 달라져서, 경우에 따라서는 꽤나 어려울 때도 있다. 다행히 이 문제는 별로 어렵지 않게, 대기중인 작업중 소요시간이 가장 작은 작업부터 시작하면 된다. text/html 2021-05-28T03:11:35+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42628?rev=1622171495&do=diff 이중우선순위큐 풀이 * BOJ의 이중 우선순위 큐와 동일한 문제. 풀이는 그쪽 참고 * 다른 사람의 코드를 보면, O(n^2) 풀이로도 통과되는 것은 BOJ와 마찬가지인데, 그 외에도 제대로 동작하지 않는 코드들도 통과된 것들이 보인다. 테스트케이스가 약한것 같다. text/html 2021-05-28T04:49:36+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42746?rev=1622177376&do=diff 가장 큰 수 풀이 * BOJ의 큰 수 만들기과 동일한 문제. 거기에서는 무려 플래티넘 난이도로 책정되어있다. 풀이는 그쪽 링크를 참고. * BOJ문제와 다른점은 숫자 크기가 1000 이하라는 점. 그래서 문자열을 그냥 4번 반복시켜서 만든 문자열을 비교 기준으로 잡는 처리도 별 문제 없이 처리된다. text/html 2021-07-31T16:10:06+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42747?rev=1627747806&do=diff H-Index 풀이 * 배열을 인용횟수가 감소하는 순서대로 정렬을 해놓으면, 어떤 논문의 {배열내 index값} = {그 논문보다 인용횟수가 많거나 같은 논문의 갯수} 가 된다. * 따라서, 어떤 논문의 인용횟수가 h값이 될수 있는지를 찾기 위해, {그 논문보다 인용횟수가 많거나 같은 논문의 갯수} 와 {인용횟수}를 비교하는 것을 그냥 index과 인용횟수를 비교하는 것으로 끝. text/html 2021-05-28T04:49:25+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42748?rev=1622177365&do=diff K번째수 풀이 * 정확히 따지면 구간 쿼리 문제. 그중에서도 구간 k-th 쿼리문제이다. * 일반적인 경우에서는 Persistent Segment Tree나 Merge Sort Tree 등을 사용해서, 쿼리당 O(logn) 또는 O(log^2(n))에 처리하는 것을 목표로 해야 한다. BOJ의 text/html 2021-10-15T02:47:32+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42839?rev=1634266052&do=diff 소수 찾기 풀이 * 그냥 무식하게 모든 가능한 숫자들을 다 만들어본다. itertools.permutation을 쓰면 간단하다. O(n!)개의 숫자들이 만들어진다. * 어떤 수 m이 소수인지 체크하는 것은 sqrt(m)까지로 다 나눠보면 되므로 O(sqrt(m))에 가능하다. m의 범위는 O(10^n)이다. text/html 2021-06-14T15:14:36+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42840?rev=1623683676&do=diff 모의고사 풀이 * 그냥 각 패턴을 적용해서 답을 만들었을때, 정답과 같은 답이 몇개인지 일일히 세어보는 것 외에 별 방법이 없다. O(n)이 걸린다. 코드 프로그래머스 ps:problems:programmers:level_1 text/html 2021-06-14T13:21:32+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42842?rev=1623676892&do=diff 카펫 풀이 * 세로 길이를 일일히 대입해보면서, 해를 찾을수도 있기는 하다. * 하지만, 그냥 식을 세워보면 2차방정식이므로 바로 해를 closed form으로 찾을 수 있다. * y = (w-2)(h-2), b = 2*(w+h-2) 로 놓고 w에 대한 2차 방정식으로 정리한 다음, 근의 공식을 적용하면.$ w={\frac {{\frac{b}{2} + 2} + {\sqrt {{\big(\frac{b}{2} + 2}\big)^{2}-4\big(b+y\big)\ }}}{2}} $$ h={\frac {{\frac{b}{2} + 2} - {\sqrt {{\big(\frac{b}{2} + 2}\big)^{2}-4\big(b+y\big)\ }}}{2}} $… text/html 2022-01-17T16:22:24+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42860?rev=1642436544&do=diff 조이스틱 풀이 * 알파벳을 설정하는 조작 (조이스틱의 위, 아래 방향)과 커서를 이동시키는 조작 (조이스틱의 왼쪽, 오른쪽 방향)을 나눠서 생각하자. 따로 구한다음에 마지막에 더해서 리턴하면 된다, text/html 2021-07-02T14:50:30+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42861?rev=1625237430&do=diff 섬 연결하기 * 아무 트릭도 없이 순수한 최소 신장 트리 (Minimum Spanning Tree / MST) 문제. 코드 * Dependency: teflib.tgraph.minimum_spanning_tree 프로그래머스 ps:problems:programmers:level_3 tag:teflib:minimum_spanning_tree text/html 2021-07-05T10:24:02+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42862?rev=1625480642&do=diff 체육복 풀이 * 아무렇게나 빌릴때 비효율적이 되는 상황은, A는 x와 y에게 빌릴수 있고, B는 y에게만 빌릴수 있는데, A가 x가 아닌 y에게 빌리는 바람에 B가 아무한테도 못빌리는 상황이다. 이런 상황이 생기지 않게 빌려줄 사람을 결정하면 된다. text/html 2022-01-19T15:30:45+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42883?rev=1642606245&do=diff 큰 수 만들기 풀이 * BOJ의 크게 만들기와 동일한 문제. * 차근차근 생각해보자. 가장 큰 수를 만들려면 맨 앞자리에 가능한 가장 큰 수를 배치해야 한다. 맨 앞자리에 올 수 있는 수는, 앞에서부터 k+1번째 까지의 수이다. 이중에서 가장 큰 수를 찾아서, 맨 앞자리에 배치한다. 가장 큰 수가 x번째에 있었다면, 이제 그 다음 자리에 올 수 있는 수는 x+1번째부터 k+2번째까지의 수이다. 이중에서 가장 큰 수를 찾아서, 두번째 자리에 배치하고.. 이런식으로 처리하면 된다.… text/html 2021-07-05T10:09:02+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42884?rev=1625479742&do=diff 단속카메라 풀이 * 두 가지의 비슷하지만 조금 다른 그리디 풀이가 있다 * 첫번째 방법은, 진입점이 작은 구간부터 처리하는 방법이다. * 진입점 기준으로 구간들을 정렬하고, 순서대로 다음 처리를 해준다. 이전까지의 구간들의 겹치는 구간과 현재 구간과 겹치는 부분이 있다면, 겹치는 구간을 업데이트 해준다. 겹치지 않는다면, 이전까지의 겹치는 구간에 카메라를 설치한다.… text/html 2021-07-05T10:10:07+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42885?rev=1625479807&do=diff 구명보트 풀이 * 문제에 나름 강조까지 해놓았지만 놓치기가 쉬운데.. 한 보트에는 최대 두명까지만 탈 수 있다. * 사실, 이런 제한이 없다면 NP-complete 문제가 될 것이다.. * 보트에 탈 수 있는 인원이 최대 두명이므로, 두명이 탄 보트를 최대한 많이 만들면 된다. text/html 2021-12-31T16:52:29+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42888?rev=1640969549&do=diff 오픈채팅방 풀이 * 입장, 재입장, 변경 등의 과정을 거쳐서 최종적으로 user_id별로 어떤 닉네임이 오는지를 저장하고 그것을 기준으로 메세지를 만들어주면 된다. * 레코드를 순회하면서 아이디별 최종 닉네임을 딕셔너리에 저장하고, 다시한번 레코드를 순회하면서 메세지를 만드는 것이 가장 간단하다 text/html 2021-01-21T15:20:42+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42891?rev=1611242442&do=diff 무지의 먹방 라이브 풀이 * food_times를 오름차순으로 정렬한 배열을 f라고 하자. 음식의 갯수는 n이라고 하자. * 처음에는 모든 음식이 아직 남아있다. n개의 음식을 f[0]만큼씩 먹고 나면, 이제 남은 음식의 갯수는 n-1이 된다. 이제 n-1개의 음식을 f[1]-f[0]만큼씩 먹고 나면, 남은 음식의 갯수는 하나 줄어서 n-2가 된다. text/html 2021-01-21T15:23:20+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42894?rev=1611242600&do=diff 블록 게임 풀이 * 그냥 구현문제. 어떻게든 돌아가게 만드는 것은 어렵지 않지만, 깔끔하게 짜려면 (귀찮은) 시간이 소요된다.. * 처음에 실수했던 부분은, 어떤 블록을 제거할 수 있는지의 여부를 그 블록 위에 다른 블록이 존재하는가로 체크했더니, 이런 예외 케이스에 부딪혔다 text/html 2021-06-29T02:24:29+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42895?rev=1624933469&do=diff N으로 표현 풀이 * 0에서부터 시작해서 k를 증가시켜가면서 N을 k번 사용해서 만들 수 있는 모든 수를 만들어보고 그 중에 number가 있는지 확인해본다. * N을 k번 사용해서 만들 수 있는 모든 수를 찾는 것은 DP를 이용한다$ dp[i] = \bigcup_{j=1}^i \bigcup_{a\in dp[j]} \bigcup_{b\in dp[i-j]}\left\{a+b, a-b, a \times b, a \div b \right\} $ text/html 2021-06-29T13:16:39+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42897?rev=1624972599&do=diff 도둑질 * 스티커 모으기(2)과 동일한 문제이다 풀이 * 원형이 아니라 직선으로 배열되어 있다면 아주 평범한 1차원 DP가 된다. * dp[i]을 i번째 집까지에서 훔칠수 있는 최대 액수라 하면, * dp[i] = max(i번째 집에서 안훔치는 경우, i번째 집에서 훔치는 경우) = max(dp[i-1], dp[i-2] + money[i]) text/html 2021-06-29T13:16:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/42898?rev=1624972577&do=diff 등굣길 풀이 * 전형적인 2차원 DP. puddle이 없다면 최단 경로의 수를 조합으로 바로 계산할 수 있지만, 이 경우는 DP로 풀어야 한다. * 어떤 좌표까지 가는 경로의 수는, 왼쪽에서 가는 경로의 수 + 위쪽에서 가는 경로의 수가 된다. 점화식은 dp[r][c] = dp[r-1][c] + dp[r][c-1] 이고, (r,c)가 puddle일때는 dp[r][c]=0 으로 처리하면 된다. text/html 2021-06-29T12:56:23+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/43105?rev=1624971383&do=diff 정수 삼각형 풀이 * 2차원 DP 처음 배울때 접하는 대표적인 연습문제로 알고 있었는데 1994년 IOI 문제였다. BOJ의 정수 삼각형도 동일한 문제. * 각 줄을 좌측정렬시켜서 직각삼각형 모양으로 만들어서 각 수를 좌표에 매칭시키자. 이제 dp[r][c]를 꼭지점에서 (r,c) 까지 이어지는 경로의 최대 합이라고 하면, 점화식은 dp[r][c] = num[r][c] + max(dp[r-1][c-1], dp[r-1][c]) 과 같은 형태가 된다. O(n^2)에 테이블을 모두 채울수 있다. 또한 현재 열에 대해서 값을 구하는 것이, 이전 열에 대한 값만으로 계산 가능하므로 슬라이딩 윈도우 방식으로 메모리를 줄일 수 있다. 테이블을 모두 채운 다음에는 max(dp[N][0],… text/html 2021-06-30T15:38:49+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/43162?rev=1625067529&do=diff 네트워크 풀이 * 커넥티드 컴포넌트의 갯수를 찾는 문제. * 특정 노드와 연결된 노드를 모두 찾는 것은 BFS와 DFS중 어느 방법으로든 가능하지만, 여기서는 DFS를 사용. * 커넥티드 컴포넌트의 갯수에 관계 없이, 모든 노드를 1번씩 방문하게 되므로, 시간 복잡도는 O(V+E)이다. 여기에서는 E = O(V^2) 이므로 전체 시간복잡도도 O(V^2)이다. text/html 2021-06-30T08:21:37+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/43163?rev=1625041297&do=diff 단어 변환 풀이 * 기초적인 BFS 문제. 현재 단어에서 변환 가능한 단어의 목록을 구해서 각각 탐색하는 것을 BFS 형태로 하면 된다. * 다만 현재 단어에서 변환 가능한 단어의 목록을 구하는 것은 두가지 방법이 가능하다. text/html 2021-06-30T08:22:35+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/43164?rev=1625041355&do=diff 여행경로 풀이 * 모든 엣지를 포함하는 경로, 즉 오일러 패스를 찾으라는 문제이다. 그냥 흔히 알려진 DFS기반의 알고리즘을 사용하면 된다. * 그래프를 인접 리스트로 표현하고, 각 리스트의 마지막에 있는 에지부터 방문하면서 엣지를 리스트에서 pop()하는 식으로 구현하였다. 즉, 리스트의 끝에 있는 엣지부터 사용하게 되므로, 알파벳 순으로 탐색하기 위해 리스트를 알파벳의 역순으로 정렬하였다… text/html 2021-06-30T08:20:23+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/43165?rev=1625041223&do=diff 타겟 넘버 * Subset sum 문제처럼, 각 숫자의 크기 제한이 없다면 NP가 되는 문제이지만, 제한이 있어서 DP로 풀 수 있다. * 왜 사이트에서는 BFS/DFS로 분류되어 있는지 모르겠다. 풀이 * DP[n][t]을 numbers[0]부터 numbers[n-1]까지를 써서 합이 t가 되는 경우의 수라고 하면 text/html 2022-01-29T16:31:13+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/43236?rev=1643473873&do=diff 징검다리 풀이 * 제자리 멀리뛰기와 동일한 문제이다. * 파라메트릭 서치로 푸는 문제. * “제거할 돌의 갯수가 n일때의 거리의 최솟값 중 최댓값=x를 구하라” 가 원래 문제인데, 이걸 파라메트릭 서치 형태로 바꾸기 위해서 f(x)를 text/html 2021-06-29T02:11:14+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/43238?rev=1624932674&do=diff 입국심사 풀이 * 원본은 COCI에 출제되었던 문제로, BOJ에도 동일한 문제를 번역한 것이 입국심사에 있다. 풀이는 그쪽을 참고. 코드 * Dependency: teflib.algorithm.binary_search 프로그래머스 ps:problems:programmers:level_3 text/html 2021-07-02T14:46:35+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/49189?rev=1625237195&do=diff 가장 먼 노드 풀이 * 그래프에서 BFS를 사용해서 모든 노드까지의 거리를 찾아주면 끝. 그 뒤에는 그중에서 가장 긴 거리가 얼마인지 구하고, 그만큼 떨어져 있는 노드의 갯수를 세면 된다. text/html 2021-07-02T14:45:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/49190?rev=1625237153&do=diff 방의 개수 풀이 * 더 간단한 풀이를 알게 되어서 업데이트. * 기존의 풀이는 화살표 방향으로 이동하다가 이전에 지나간 점 위를 다시 지나간 횟수를 방의 개수로 계산하는 방식이었다. 여태가지 이동한 직선의 목록 L과 점의 목록 P를 유지하면서, 새로 이동한 경로(도착점이 p고 직선이 l인)가 l∉L 이고 p∈P 이면 방의 갯수를 하나 증가시키는 식으로 구현했었다. text/html 2021-09-07T14:27:50+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/49191?rev=1631024870&do=diff 순위 풀이 * BOJ의 Cow Contest과 동일한 문제. 원 출처는 USACO이다. * 어떤 선수를 기준으로 {그 선수보다 순위가 낮은 선수의 수} + {그 선수보다 순위가 높은 선수의 수}가 {전체 선수의 수 - 1} 이라면, 그 선수는 순위를 정확하게 매길 수 있다. text/html 2021-01-25T08:51:37+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/49995?rev=1611564697&do=diff 쿠키 구입 풀이 * 구해야 할것은 문제에 다 주어져있다. sum(A[l:m]) == sum(A[m:r]) == X 인 X의 최대값이다. * 이터레이션을 하는 방법에 따라 조금 더 공간복잡도를 효율적으로 쓰거나, 브랜치를 좀더 잘하거나 하는 방법이 있지만, 결국 시간 복잡도는 모든 구간에 대해서 구간합을 구해보는 O(n^2)이다. text/html 2021-07-31T16:51:04+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/60057?rev=1627750264&do=diff 문자열 압축 풀이 * 그냥 무식하게, 문자를 1개단위, 2개단위, ..., |s|개 단위로 모두 압축해보고, 그중에서 가장 길이가 짧은것을 찾으면 된다. * 단위가 전체 길이의 절반을 넘어가면 압축이 불가능하므로, |s|/2 까지만 해봐도 되긴 하다만, 큰 의미는 없다. text/html 2022-01-17T11:39:27+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/60059?rev=1642419567&do=diff 자물쇠와 열쇠 풀이 * M과 N이 작기 때문에, 그냥 열쇠를 한칸씩 움직여 대어보면서 자물쇠가 열리는지 확인해 보면 된다. * 자물쇠가 열리는지를 확인하는 것은 모든 자물쇠 칸이 다 맞물렸는지 체크해보면 된다. 시간복잡도는 O(n^2). text/html 2021-01-21T14:50:27+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/60060?rev=1611240627&do=diff 가사 검색 풀이 * 트라이 (Trie)를 사용하면 간단히 풀리는 문제. * 생각할 부분은 단순히 특정 접두어로 시작하는 단어의 갯수가 아니라, 특정 접두어로 시작하면서 전체 길이가 x인 단어의 갯수를 구해야 한다는 것. text/html 2021-01-22T14:53:41+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/62050?rev=1611327221&do=diff 지형 이동 풀이 * 전체가 연결되도록 사다리를 설치한다는 말을 바꾸면, 모든 인접 격자간에 사다리가 있는 상태에서 전체가 연결되도록 최소한만 남기고 철거한다고 볼수도 있다 * 이렇게 생각하면 바로 text/html 2021-01-17T15:44:06+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/64063?rev=1610898246&do=diff 호텔 방 배정 풀이 * Disjoint Set을 사용해서 푸는 문제이다. * 어떤 방을 요청할 때 실제로 같은 방으로 배정되는 방들을 하나의 집합으로 유지하면 된다 * 구체적으로, n번부터 m-1번까지의 방이 모두 차 있는 상태라면, 다음에 n번부터 m번 사이의 방으로 요청이 들어오면 m번에 배정을 해줘야 한다. 이것은 n부터 m까지는 같은 집합이고, 그 집합의 다음 배정 예정방은 m으로 매핑이 되어있는 상태로 표현된다… text/html 2022-01-12T09:22:23+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/64065?rev=1641979343&do=diff 튜플 풀이 * 시키는대로 하려면, 각 집합들을 크기순서대로 정렬해서, 크기 1짜리 집합의 원소를 튜플의 첫번째 원소로 두고, 크기 2짜리 집합의 원소들중 처음 등장한 것을 튜플의 두번째 원소로 두고, 이런식으로 끝까지 반복하면 된다. 다만 구현이 귀찮다 text/html 2022-01-10T04:51:43+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/67257?rev=1641790303&do=diff 문제제목 풀이 * 세가지 연산자의 가능한 우선순위는 총 3!=6가지이다. 그냥 이 6가지 조합에 대해서 전부 식을 계산해보고 최댓값을 구하면 된다. * 식을 계산하는 것은 스택을 써서 정석적으로 구현할 수도 있지만, 식의 형태가 단순하기 때문에, 그냥 연산자를 갖고서 문자열을 split한 뒤에, 분할된 각 문자열들에 대해서 다시 재귀적으로 값을 계산하고 마지막에 합쳐주는 방법으로도 충분하다.… text/html 2020-12-23T15:44:50+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/67260?rev=1608738290&do=diff 동굴 탐험 풀이 * 유향 그래프에서 사이클의 존재 여부를 찾는 문제의 변형. * 주어지는 그래프는 트리이다 * 문제의 “임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며 text/html 2021-01-21T16:22:48+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/68645?rev=1611246168&do=diff 삼각 달팽이 풀이 * 그냥 구현 문제 * 삼각형 형태의 2차원 리스트에 채우고 이어 붙이는 방법도 가능하지만, 1차원 리스트에 바로 채우는 방식으로 했다. * 1차원 리스트을 삼각형 모양으로 가정하고 채우려면 조금 번거롭다. 예를 들어, 맨 처음 아래쪽으로 채워 나갈때도, 인덱스가 0, 1, 3, 6, text/html 2021-01-21T16:27:49+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/68646?rev=1611246469&do=diff 풍선 터트리기 풀이 * 생각만 하면 구현은 굉장히 간단한 문제 * 풍선들 중에서 가장 작은 번호를 가진 풍선만 남기는 것은 '큰풍선 터트리기'만 사용해서 터뜨릴수 있다. * 따라서, 어떤 풍선 a[i]가 그보다 왼쪽에 있는 모든 풍선들보다 번호가 작다면, a[0:i+1]에서 가장 작은 번호가 a[i]니까 text/html 2021-01-31T17:17:38+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/68647?rev=1612113458&do=diff 짝수 행 세기 풀이 * 문제에서는 인풋으로 테이블이 들어오지만, 사실 테이블 자체는 필요 없고, 각 열에 1이 몇 개씩 있는지만 알면 된다. 굳이 의미도 없는데 테이블 전체를 인풋으로 준 것은 일부러 헷갈리게 하려 한건가..$ f(c+1, e-x+y, e) = DP[c][e]*C(e,x)*C(R-e,y) $$ DP[c+1][e-x+y] = \sum_e{f(c+1,e-x+y,e)} = \sum_e{DP[c][e]\times C(e,x) \times C(R-e,y)} $ text/html 2021-01-16T15:37:29+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/68937?rev=1610811449&do=diff 트리 트리오 중간값 풀이 * 구하라고 하는 값이 설명으로는 좀 복잡해보이는데, 따져보면 단순하다. * 우선, 트리의 지름이란 트리에 존재하는 경로중 가장 긴 경로의 길이를 의미한다는 것을 기억하자. text/html 2021-01-25T17:00:20+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/68938?rev=1611594020&do=diff 문자열의 아름다움 풀이 * 공식 블로그에 공식 해설이 이미 있기는 하다. * 그러나 해설에서는 세그먼트 트리를 이용해서 O(nlogn)에 푸는 방법을 설명하고 있지만, 수식을 잘 정리하면 O(n)에 푸는 것도 가능하다.$\sum_i(len(s_i)) = \sum_{i=1}^n{\sum_{j=i+1}^n(j - i)} = \frac{n(n-1)(n+1)}{6} $ text/html 2021-01-30T14:21:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/72410?rev=1612016513&do=diff 신규 아이디 추천 풀이 * 기초적인 문자열 연산 문제 * 가독성을 위해서 문제에서 주어진 프로세스를 각각 한줄씩에 나눠서 처리하도록 작성 * 7단계의 프로세스중 어느것도 O(n)을 초과하지 않는다 text/html 2021-01-30T14:23:44+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/72411?rev=1612016624&do=diff 메뉴 리뉴얼 풀이 * 효율적인 방법은 딱히 없다. n이 작으니 주문이 한번 올 때마다, 모든 부분집합을 다 구해서 카운터를 각각 올려주는 무식한 방법으로 해결 가능 * 모든 요리 조합에 대해서 주문 횟수를 세는 것은 O(n*2^m). (n=주문의 갯수, m=한번 주문에 포함가능한 요리 갯수) text/html 2021-02-04T16:09:47+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/72412?rev=1612454987&do=diff 순위 검색 풀이 * 알고리즘적으로 어려운 부분은 없고, 구현 문제에 가깝다. * 총 3*2*2*2 개의 타입으로 지원자를 분류 가능하므로, 각 타입별로 리스트를 따로 만들고, 각 리스트에는 점수를 정렬해서 저장한다. 쿼리가 들어오면 매칭되는 리스트들에서, 기준점수 이상의 지원자의 수를 이진검색으로 찾는다. text/html 2024-03-14T08:35:20+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/72413?rev=1710405320&do=diff 합승 택시 요금 풀이 * 합승해서 x까지 같이 간 뒤에, x에서 부터는 따로 택시를 타고 a와 b로 간다면 총 요금은 cost[s][x] + cost[x][a] + cost[x][b]. * 모든 x에 대한 cost[s][x], cost[x][a], cost[x][b]의 값을 계산해놓는다면, min_x(cost[s][x] + cost[x][a] + cost[x][b]) 는 O(n)에 계산가능 text/html 2021-03-02T04:09:28+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/72414?rev=1614658168&do=diff 광고 삽입 풀이 * 구간 업데이트와 구간 쿼리가 섞여있다보니 세그먼트 트리가 필요할 것 같지만, 구간 업데이트가 모두 끝난 뒤에 쿼리들이 나올 때에는 prefix sum만을 이용해서 더 빠르게 풀 수 있다. 방법은 text/html 2021-01-30T15:21:37+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/72415?rev=1612020097&do=diff 카드 짝 맞추기 풀이 * 카드의 종류가 작아서 어떻게 풀든 풀리기는 풀린다. * 최대 n종류의 카드를 지우는 방법의 순서는 n! 가지. 그리고 각 카드 종류별로 두장의 카드가 있으니까, 어느쪽을 먼저 선택할지에 따라서 두종류의 방법이 있다. 그러면 이동하는 경로의 종류는 (2^n)*(n!) 가지이다. 각 경로는 2*n개의 카드를 선택해야 한다. 한번 선택하기 위해 이동할때마다 BFS가 필요하다. BFS는 노드 갯수가 4*4=16으로 정해져 있으니까 그냥 상수처리 한다고 해도 총 시간 복잡도는 O(2^n * n! * 2n). 복잡도는 크기만.. n이 최대 6이므로 풀리긴 풀린다.$ \begin{aligned} dp[s][p[c0][0]] = \min_i(\min(&d(p[c0][0], p[c0][1])+d(p[c0][1], p[ci][0]) + dp[s-\{c0\}][p[ci][0]], \\ & d(p[c0][0], p[c0][1])+d(p[c0][1], p[ci][… text/html 2021-01-30T15:49:20+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/72416?rev=1612021760&do=diff 매출 하락 최소화 풀이 * 트리에서의 DP를 이용하는 문제. * 사실 내가 푼 아래 코드와 공식 풀이가 거의 일치한다. 그래서 풀이는 생략. * DP table을 명시적으로 만드는 대신 functools.lru_cache를 붙이는 것으로 처리했다. text/html 2021-07-08T16:17:37+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/77484?rev=1625761057&do=diff 로또의 최고 순위와 최저 순위 풀이 * 최고 순위의 경우는 일치된 숫자의 갯수를 {실제 매칭된 숫자의 갯수} + {0의 갯수} 로 놓고 순위를 계산하면 되고, 최저 순위의 경우는 {실제 매칭된 숫자의 갯수}만 일치된 숫자로 간주해서 순위를 구하면 된다. text/html 2021-07-08T16:14:56+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/77485?rev=1625760896&do=diff 행렬 테두리 회전하기 풀이 * 그냥 단순하게, 매 회전 명령마다 실제 행렬을 회전시키면서 처리하면 된다. * 데이터 구조를 어찌어찌 잘 만들면 좀더 효율적인 알고리즘이 있을것 같기도 한데 생각해내지는 못했다.. 어차피 행과 열 사이즈가 100 이하라서 효율적인 방법이 존재하더라도 실제 수행 시간은 별 차이 없을것이다.. text/html 2021-07-08T16:40:27+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/77486?rev=1625762427&do=diff 다단계 칫솔 판매 풀이 * 특별한 알고리즘 없이 그냥 그대로 구현하면 된다.. * 자식이 업데이트될때 부모들도 똑같은 값이 증가된다면, 오일러 트리 테크닉과 세그먼트 트리를 이용하여 효율적으로 푸는 방법을 고민해 볼수 있겠지만, 이 문제는 그렇게 하기도 쉽지 않거니와 그렇게 할 필요도 없다. 이익이 최대 100*100 = 10000원이기 때문에, 10%씩 부모에게 떼어주는 것을 반복하면, 업데이트 되는 노드의 갯수는 최대 5개뿐이다. 따라서 한개의 쿼리에 5개 이하의 노드만 업데이트해주면 되므로 그냥 O(1)으로 생각할수 있다. n개의 노드로 트리를 만드는 데에는 O(n), m개의 쿼리를 각각 O(1)에 처리하는 데에는 O(m). 총 시간복잡도는 O(n+m).… text/html 2021-07-10T14:41:08+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/81031?rev=1625928068&do=diff text/html 2021-07-10T14:55:35+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/81032?rev=1625928935&do=diff text/html 2021-07-10T18:12:34+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/81301?rev=1625940754&do=diff 숫자 문자열과 영단어 풀이 * 단순 구현 문제. * 다만 구현 방법에 있어서는, 직접 매칭을 구현하는게 가장 효율적으로 동작할것 같지만, 코딩이 너무 귀찮다. * 'zero'부터 'nine'까지에 대해서 string.replace() 함수를 10번 반복해서 호출하는 방법이 쉽게 떠오른다. 그리고 정규표현식을 통해서 '(zero|one| text/html 2021-07-10T18:11:54+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/81302?rev=1625940714&do=diff 거리두기 확인하기 풀이 * 그냥 구현문제.. * 모든 셀에 대해서 그 셀에 응시자가 있는 경우, 맨해튼 거리 2 이내의 셀중에 거리두기를 안지킨 응시자가 있는지 확인하면 된다. BFS로 구현할수도 있지만, 그냥 상하좌우로 인접한 셀, 대각선으로 인접한 셀, 상하좌우로 2칸 거리의 셀의 세가지 패턴으로 나누어서 응시자가 있고 파티션이 없는 경우가 있는지를 각각 확인하는 것이 좀더 편리하다.… text/html 2021-07-10T18:12:48+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/81303?rev=1625940768&do=diff 표 편집 풀이 * 사실 문제를 얼핏 보자마자, Order Statistic Tree를 써서 풀어야 하는 문제라고 생각을 했고, 파이썬에서는 세그먼트 트리 기반의 구현체를 사용해야 할것이라고 생각했다. 그리고 그렇게 풀었다. text/html 2021-07-10T18:12:21+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/81304?rev=1625940741&do=diff 미로 탈출 풀이 * 양수 가중치 그래프에서 최단 거리 경로를 찾는 문제이므로 다익스트라 알고리즘을 쓰면 된다. * 다만 트랩의 상태에 따라서 그래프가 바뀌는 것이 문제인데, 무식해보이지만 단순한 방법은 노드와 트랩 상태를 묶은 것을 새로운 노드로 정의하고, 그러한 노드들을 가지고 그래프를 새로 만드는 것이다. text/html 2021-07-10T18:12:06+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/81305?rev=1625940726&do=diff 시험장 나누기 풀이 * k개의 그룹으로 나눌때의 그룹의 최댓값을 최소화시키는 문제는 파라메트릭 서치의 기본 유형중 하나이다. * 파라메트릭 서치로 풀 때는, 결정 문제가 그룹의 최댓값을 X로 만들때 필요한 그룹의 갯수가 K 이하인지를 확인하는 것이 된다. 즉, 그룹의 최댓값을 X로 만들수 있는 그룹의 최소 갯수를 구하는 것이 필요하다. 1차원 배열을 이런식으로 그룹들로 나누는 문제들은 흔히 나오는 편이고 이 경우는 최댓값이 고정되있을 때 그룹의 최소 갯수를 그리디한 방법으로 간단하게 구할수 있다. 이 문제에서는 이진트리라서 좀더 복잡하지만 그래도 그리디하게 구할수 있다.… text/html 2021-08-30T15:21:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/84512?rev=1630336869&do=diff 모음 사전 풀이 * 무식한 방법은 모든 단어를 다 만들어 놓고서 그 중에서 word의 위치를 찾는 것이다. 단어의 갯수는 5^5 개밖에 안되므로, 단어를 전부 생성하고, word 를 찾는것 모두 O(5*5^5)으로 처리된다. text/html 2021-09-13T14:37:40+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/85002?rev=1631543860&do=diff 복서 정렬하기 풀이 * 그냥 시키는대로, 주어진 정렬 기준에 해당되는 값을 계산해서 정렬하면 된다 * 한 선수의 승률을 계산하기 위해서는, n명의 선수와의 전적을 봐야 하므로 O(n). 따라서 n명의 선수 모두에 대해서 승률을 각각 구하려면 O(n^2). {자신보다 무거운 복서를 이긴 횟수} 를 모든 선수에 대해서 구하는 것도 마찬가지로 O(n^2). text/html 2021-09-13T14:24:10+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/86048?rev=1631543050&do=diff 입실 퇴실 풀이 * 레벨에 비해서는 다소 까다로운 문제. 아이디어도 떠올려야하고, 그 아이디어를 효율적으로 구현할수 있는 방식도 떠올려야 한다 * 단순하게 A와 B만 갖고서 생각하면 A가 B와 만난것을 확신하기 위한 조건은, B보다 일찍 입실하고 늦게 퇴실한 경우에만 가능한 것처럼 보인다. 예를 들어서 A가 B보다 먼저 입실하고 먼저 퇴실했다면, B의 입실보다 A의 퇴실이 더 빨랐을 경우에는 만나지 못한다. 하지만 C가 추가되면, 똑같이 A가 B보다 먼저 입실하고 먼저 퇴실했어도 A와 B가 만난것을 확신할 수 있는 경우가 생긴다. 예를들면 입실시간이 A<B<C이고 퇴실시간이 C<A<B 일 경우에는 A의 퇴실은 B의 입실 이후이므로 A와 B는 만날수밖에 없다.… text/html 2022-01-12T10:00:57+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/86052?rev=1641981657&do=diff 빛의 경로 사이클 풀이 * 각 노드들에 대해서 다음 노드들이 주어져있을때, 사이클을 모두 찾는 문제이다. 처음 노드를 시작점으로 해서 경로대로 따라가며 사이클을 찾고, 그 다음에는 아직 방문하지 않았던 노드를 골라서 그 노드를 시작점으로 하는 사이클을 찾고, 이것을 모든 노드를 방문할때까지 수행하면 된다. text/html 2021-09-27T12:30:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/86491?rev=1632745853&do=diff 최소직사각형 풀이 * 가로길이의 최솟값과 세로길이의 최솟값을 곱하면 끝. * 명함마다 가로 방향을 각각 다 바꿔가면서 계산할 필요 없이, 그냥 모두 긴쪽을 가로로 놓는다고 생각해도 동일한 결과를 얻을 수 있다. 따라서 시간복잡도는 O(n). text/html 2021-10-21T15:47:06+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/87377?rev=1634831226&do=diff 교점에 별 만들기 풀이 * 그냥 시키는 대로 구현하면 되는 문제. * 각 line 쌍에 대해서 공식대로 교점을 구하고, 교점의 좌표가 정수이면 저장해둔다. 이렇게 구해둔 교점의 좌표들중 x좌표와 y좌표의 최솟값과 최댓값을 구해서 그 크기만큼 2차원 배열을 .으로 채우고, 교점의 위치에 *을 저장하면 끝. text/html 2021-10-18T02:58:25+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/87694?rev=1634525905&do=diff 아이템 줍기 풀이 * 그냥 구현 문제. 사각형의 최대 갯수와 좌표의 범위가 모두 작아서 어떤식으로 구현하든 통과되는데에는 문제가 없다. * 여기에서는 그냥 둘레를 따라서 1칸씩 이동하면서 한바퀴 돌면서, 전체 둘레 길이와 아이템까지의 거리를 재는 방식으로 구현했다 text/html 2022-02-28T07:21:12+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/92341?rev=1646032872&do=diff 주차 요금 계산 풀이 * 그냥 시키는대로 구현하면 되는 문제. * 자동차별로 주차 시간을 저장하는 것을 dict를 이용해서 처리하고, 자동차 번호순으로 출력하기 위해서 소팅을 사용했기 때문에 시간복잡도가 O(nlogn)이 되었다. 자동차 번호의 범위가 0000~9999 까지이므로 그냥 크기 10000짜리 배열을 이용해서 처리한다면 소팅없이 O(10000) 의 상수시간으로 주차 요금을 번호순으로 출력하는 것도 가능하다.… text/html 2021-07-02T14:47:46+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/%EA%B3%A0%EB%93%9D%EC%A0%90_kit?rev=1625237266&do=diff 코딩테스트 고득점 Kit * 코딩테스트에 자주 나오는 유형별로 3~4문제씩을 추린 일종의 문제집. * 백준 온라인 저지 (BOJ)의 BOJ / 단계별 과 비슷한 느낌으로 생각하면 된다. 문제목록 해시 문제 번호Page레벨분류42576완주하지 못한 선수Level 142577 text/html 2021-11-01T04:18:52+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/%EC%9C%84%ED%81%B4%EB%A6%AC_%EC%B1%8C%EB%A6%B0%EC%A7%80?rev=1635740332&do=diff 위클리 챌린지 * <https://programmers.co.kr/learn/challenges> * 가장 많은 '좋아요'를 받은 코드를 작성하면 치킨 키프티콘을 준다고 한다 * 8주차 최소직사각형 에서 가장 많은 '좋아요'를 받았는데 쿠폰은 못받았다. 나중에 보니까 프로필에 전화번호 등록이 안 되어있었다.. text/html 2021-08-30T14:42:43+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.teferi.net/ps/problems/programmers/start?rev=1630334563&do=diff 프로그래머스 * 사이트 주소: <https://programmers.co.kr/> * 프로그래머즈가 아니라 프로그래머스이다. 특징 * 적용되는 파이썬3 버전은 Python 3.8.5 이다 (2020-12-11 기준) * numpy를 사용할 수 있는 것 같다?? => 그치만 다른 사이트와의 통일성을 위해 쓰지 말자.