무딘붓의 코딩기록

문제 https://www.acmicpc.net/problem/7570  문제 풀이 과정N=100만이고, N log N ~ 2000만이므로 O(NlogN) 시간 내에 풀어야 하는 문제입니다. 처음 봤을 때 떠오른 방식은 최장 증가 부분수열(LIS) 이었습니다. (처음 풀이 코드 - 실패)import sysinput = sys.stdin.readlinen = int(input())data = list(map(int, input().split()))# target 보다 작은 값 중 가장 큰 값의 index 반환def binary_search(array, target): start, end = 0, len(array) - 1 result = -1 while start = len(dp): ..

문제 https://www.acmicpc.net/problem/1003  문제 풀이 과정 전형적인 dp 문제입니다. dp[n]에 fibonacci(n)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 저장하도록 해보겠습니다.배열의 첫 원소는 0이 출력되는 횟수, 두 번째 원소는 1이 출력되는 횟수를 저장하는 식으로 구현하겠습니다. 먼저 손으로 dp[0]부터 값을 채워보면서 규칙을 찾아보겠습니다. dp[0]과 dp[1]은 예시에서도 나와있듯이 [1,0]과 [0,1]입니다.dp[2]는 dp[0]과 dp[1]을 호출하므로 두 값을 합한 값인 [1,1]이 되고,마찬가지로 dp[3]도 dp[1]과 dp[2]를 합한 값이 됩니다. dp[i][0] = dp[i - 1][0] + dp[i - 2][0]dp[i][1]..

문제 https://www.acmicpc.net/problem/2482 문제 풀이 과정 일단 규칙성을 찾아보기 위해 n=4부터 7, k=1부터 4까지의 값을 손으로 계산해 보았습니다.  풀면서 찾게 된 점화식은 다음과 같습니다.dp[n][k] = dp[n-2][k-1] + dp[n-1][k]예를 들어, 각 색상을 1번부터 n번까지의 번호라고 가정하고 1번과 n번이 연결되었다고 해보겠습니다.n=7, k=3 인 상황에서 가능한 경우는 다음과 같습니다.1 3 61 4 62 4 72 5 73 5 71 3 52 4 6위의 경우를 잘 살펴보면 n=5, k=2일 때 가능한 값에6과 7이 추가된 경우의 수가 있고1 3 + 61 4 + 62 4 + 72 5 + 73 5 + 7n=6, n=3일때 가능한 ..

문제 https://www.acmicpc.net/problem/11726  문제 풀이 과정  예전에 풀었던 2xn 타일링 문제와 비슷해서 바로 dp 문제라는 것을 떠올릴 수 있었습니다. dp 테이블은 dp[n]이 3*n 크기의 벽을 채울 수 있는 경우의 수로 가정하고 만들었습니다. 규칙을 찾기 위해서 위의 그림처럼 하나씩 경우의 수를 그려가며 풀어보았습니다. 그 결과n=홀수 인 벽은 채울 수 없다.n=2인 경우에는 3가지 경우가 가능n=4인 경우부터는 기존의 조합을 사용하지 않는 2개의 새로운 경우와, 기존의 조합을 활용한 경우의 수가 존재한다.라는 규칙을 찾았습니다. 조금 더 구체적으로 설명하면, n=4 이상일 때 가능한 경우의 수는 다음과 같습니다.기존 경우의 수로 채우지 못하는 2가지 경우먼저 2칸..

https://school.programmers.co.kr/learn/courses/30/lessons/147355 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [소스 코드] // 23.06.23 #include #include using namespace std; int solution(string t, string p) { int answer = 0; for(int i=0;i

https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [소스 코드] //23.06.22 #include #include #include using namespace std; bool compare(vector a, vector b) { return a[1] < b[1]; } vector solution(vector plans) { vector answer; vector waitTesk; sort(plans.begin(), plans.end(), c..

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [소스 코드] // 23.06.21 #include #include using namespace std; vector solution(vector sequence, int k) { vector answer; answer.push_back(1); answer.push_back(1000002); int i=0; int j=0; int sum=sequence[0]; while (i = k){ if(s..

https://school.programmers.co.kr/learn/courses/30/lessons/181187# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [소스 코드] // 23.06.12 // https://sirius7.tistory.com/ #include #include #include using namespace std; long long solution(int r1, int r2) { long long answer = 0; for(int i=1;i

https://school.programmers.co.kr/learn/courses/30/lessons/172928 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [소스 코드] // 23.06.12 // https://sirius7.tistory.com/ #include #include using namespace std; vector solution(vector park, vector routes) { vector answer; for(int i=0;i

https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr map에 대한 학습 없이 풀었다가 시간 초과가 나왔던 문제입니다. 아래는 시간초과가 나온 코드입니다. #include #include #include using namespace std; vector solution(vector players, vector callings) { vector answer(players); for(int i=0;i