development korean paul development korean paul

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net #include #include using namespace std; int main() { int N = 0; int num = 0; cin >> N; vector DP = vector(101, 0); DP[0] = 1; DP[1] = 1; DP[2] = 1; for (int i = 3; i > num; cout

접근법 최적이 행렬 곱셈 알고리즘을 사용하여 푼다. https://ggjjdiary.tistory.com/132 [알고리즘] 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication) 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication) 연쇄 행렬(ex, 2 by 4 행렬 x 4 by 7 행렬 x 7 by 9 행렬 x ...)의 곱셈을 할 때 곱셈 연산을 최소로 하는 곱셈 순서를 찾는 알고리즘이다. 행렬 곱셈은 결 ggjjdiary.tistory.com 풀이 시간 복잡도 : 200 * 200 .. 200 의 형식으로 결합순서까지 생각하며 풀면 시간초과가 발생한다. 일단 다음과 같이 5개의 행렬이 있다고 생각해보자. 1) 그림에서 제시하고 있는 순서 외에도 ..

접근법 예제 1번을 보면 (1, 9) 보단 (2, 8)이 크다. 쭉 진행하다 보면 (3, 6) 보단 (4, 4)가 크다. 야근 지수 문제처럼 균등하게 분포 될 때 곱의 최대가 된다는 것을 알 수 있다! 풀이 s / n을 한 값을 정답에 담고, s % n 즉 나머지를 마지막 인덱스부터 추가한다. sort를 사용하는 것보단 위의 방식이 시간 복잡도를 줄여준다. 코드 #include #include using namespace std; vector solution(int n, int s) { if(n > s == 1) return vector(1, -1); int div = s / n; int ex = s % n; vector answer = vector(n, div); int i = answer.size()..

접근법 야근 지수를 구하는 공식이 a^2 + b^2 + c^2 .... n^2이므로 수학적으로 접근하면 크기가 균등하게 작아지면 된다는 점으로 접근하면 된다. 따라서 우선순위 큐를 사용해서 현재 가장 큰 값을 줄이는 방식으로 접근하면 된다! 풀이 우선순위 큐를 사용하면 제일 큰 값이 top()에 오기 때문에 감소 시킨다. 이 때 N시간 동안 일을 할 수 있기 때문에 N을 감소시키고 우선순위 큐도 갱신하기 위해 pop() 을 진행 후 push()를 해준다. works의 원소가 모두 0이 되는 경우가 있기 때문에 push() 전에 원소가 0인지 아닌지를 체크한다. works의 모든 원소가 0이되는 예) works n result [1,1] 3 0 코드 #include #include #include #inc..

문제 해석 n 처리해야 할 작업의 개수 cores 각 코어의 처리시간이 담긴 배열 cores에 담긴 시간이 경과 할 때 처리 작업의 개수를 하나씩 줄여나간다. (2개 이상의 코어가 남을 경우) 접근법 완전 탐색의 경우 BigO(n * 코어의 개수) 이므로 시간 초과가 발생한다. 따라서 Parametric Seach를 이용해야한다. 1. 파라메트릭 서치란? 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어 나가는 기법입니다. 여기서 결정 문제란 'yes' or 'no' 즉 '예' 또는 '아니오:로 답하는 문제를 말합니다. 파라메트릭 서치는 주로 특정 조건을 만족하면서 동시에 가장 적합한 변숫값을 찾아나가는 문제에서 활용되며, 이진 탐색(Binary Search)을 이용하여 구현합니다. 예를 들어, ..

접근법 "정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요." 라는 문구를 보고 완전 탐색은 배제해야하는 문제이다. 따라서 DP로 접근해야하는데, 예를 들어서 손님께 5원을 거슬러 줘야하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원은 5개를 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러준다. 5원을 1개 사용해서 거슬러준다. 예시를 보고 3원을 구하는 경우의 수를 볼 때 3원 = 1원 + 1원 + 1원3원 = 1원 + 2원3원 = 2원 + 1원이렇게 경우의 수가 순서에 따라 달라질 수 있으므로 순서에도 신경을 써야하는 문제이다. ..

문제 풀이 해당 문제는 인덱스 접근을 통해서 풀었다. 전체 문자열을 반복하면서 패린드롬을 구하는 포인터를 다르게 하면서 홀수인 경우와 짝수인 경우의 팰린드롬을 나눠서 구했고 최대값을 저장했다. for(int i = 0; i < s.size(); ++i) { int odd = isPalindrome(s, i, i); int even = isPalindrome(s, i - 1, i); int ismax = max(answer, odd); answer = max(ismax, even); } 포인터로부터 left는 감소 right는 증가시켜나가며 문자열이 같은지 확인했다. 문자열의 길이는 right - left -1 이다. ex) 7 - (-1) -1 int isPalindrome(string s, int le..

https://school.programmers.co.kr/learn/courses/30/lessons/1838 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 헬스장의 예약 내역이 주어졌을때, 구현을 통해서 구하는 것이 아닌, 회원수가 최대인 구간만 구하게 되면 나머지는 회원수가 최대인 시간의 배열의 부분 집합으로 구할 수 있습니다. 2. priority_queue를 사용하여, 그리디하게 회원수가 최대인 시간을 구해주었으며, 3. 문제의 핵심인 락커의 위치를 구할떄는 락커의 각 부분배열을 완전탐색으로 구해주어, 시간내에 문제를 해결할 수 있었습니다...