Computation suite

https://www.acmicpc.net/problem/12920 1트 https://cpusuite.blogspot.com/2025/04/bboj12865-knapsack-dp.html와 동일하게 최대의 만족도를 도출하는 문제이지만 물건에 재고 attribute가 추가되었다. 한 행에 weight : 3, value : 5, stock: 3를 입력받으면 그 물건의 재고가 3개 있다는 뜻이다. weight 3 , value 5, stock 3은 weight 3 , value 5 weight 3 , value 5 weight 3 , value 5과 같지 않을까? 대신 물건의 개수가 2개 늘어나며 테이블의 크기도 늘어나며 이는 런타임 상에서 재고 수 만큼 메모리를 더 차지한다.

https://www.acmicpc.net/problem/12865 배낭에 넣을 수 있는 물건들의 가치의 최댓값 Brute Force 물건 하나 당 가져간다(True) / 안 가져간다(False)를 마킹하는 식으로 배낭에 담을 물건을 정할 수 있음. T/F 2가지 경우가 있고 물건이 N개, 문제에서는 최대 100개 이므로 2^100 개의 경우의 수에 대해 Case 하나 하나에 대해 ( T F T T F.....T ) 무게와 가치를 계산해야한다. 2^100( Case의 수 ) * 100( N=100 이므로) 시/공간적으로 실현할 수 없다. Greedy 마찬가지로 당장 최선의 선택을 한다고 해서 최적의 결과가 나오지 않는 문제다. DP dp_table에 삽입되는 데이터 dp table에는 최대   가치 값 을 담을 것이다. dp table을 이용하여 선택된 dp table의 element를, 가치값을 구하기 위하여 이전에 계산된 값을 참조할 것이고, 다시 계산하지 않을 것이다. dp_table의 목적 가방 안의 숫자들을 물품의 id라고 가정한다. 1 2 3 에서 4의 물품을 넣었을 때, 무게가 초과한다면 처음부터 계산하지 않고 1 2 3에 계산된 값을 사용하여  다시 물품을 넣기 시작할 것이다. 1 2 3 5 에서 6번 물품을 넣었을 때, 무게가 초과한다면 처음부터 계산하지 않고 1 2 3 5에 계산된 값을 사용하여 다시 7번 물품을 넣기 시작할 것이다. 가방 그림에는 여러 물품이 element로서 들어간 것처럼 보이지만 dp_table에는 여러 물품들의 value의 합산 값 하나 만 들어간다. dp_table 설계 dp 자료구조를 설계하기 위해서는 각 index가 무엇을 의미하는지, 자료구조의 element가 무엇에 의해 결정되는지 파악해야한다. 4개정도 꼽아 볼 수 있다. w=weight, v=value, n=물건 개수 , k=소지 가능 무게 처음에는 1차원 dp 배열을 생각했으나 배낭에 다음 물건을 담을 때,  하나를 건너 뛰고 담을...

https://www.acmicpc.net/problem/1149 모든 집을 칠했을 때의 비용의 최솟값. 1. 모든 경우의 수를 나열한 뒤 정렬하여 최솟값을 찾는 방법 2. 특정 지점으로 돌아가    이전까지 계산된 값을 활용하여    중간 지점부터 계산하는 방법 이 있고 후자가 DP이다. Greedy 알고리즘으로 최적해를 구할 수 없는 이유는 아래와 같은 조건이 있기 때문에 당장 작은 색칠 비용을 선택한다고 해서 최종적으로 가장 적은 색칠 비용이 나오지는 않기 때문이다. - 1번 집의 색은 2번 집의 색과 같지 않아야 한다. - N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. - i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. -> 이웃하는 집과 색이 같아서는 안된다. 색칠 비용 배열을 cost = []라고하고  이 배열 안에 (r , g, b)의 튜플 형태로 색칠 비용이 있다. 처음에는 dp[i]의 1차원 배열로 접근했는데 cost 중 하나를 선택해야하기 때문에 1차원 배열로는 재귀 조건을 만족시킬 수 없었다. 때문에 2차원 배열 관계식을 사용해야한다. 칠할 수 있는 경우의 수는 r, g , b 의 3가지 이므로. dp[i][0] = min(dp[i-1][1], dp[i-2][2])+ rgb[n][0]  dp[i][1] = min(dp[i-1][0], dp[i-2][2])+ rgb[n][1] dp[i][2] = min(dp[i-1][2], dp[i-2][0])+ rgb[n][2] 가능한 이전 dp값중 최솟값  + 해당 집의 칠할 색깔( red, green, blue)

실전 문제에는 해결할 수 있는 로직이 더 숨겨져있다. 즉,  https://www.acmicpc.net/problem/11048 처럼 직관적으로  1, 2차원 dp table 2. 초기값 3, 재귀 구조를 알려주지 않는다. 알고리즘 테스트를 풀면서 이를 난이도 차이를 더 크게 체감하게되어서 다시 dp기초부터 복습하고자 한다. ====================================================== 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구한다. 미로의 사탕 크기에 대한 규칙이 따로 없기에 Greedy 한 방법, 즉, 사탕의 개수가 큰 곳으로만 이동하는 방법이 최적해라는 보장이 없다. 따라서 Greedy 한 접근 방법은 제한다. 어떤 방법을 이용했을 때, 최댓값이 아니라면 처음부터 재계산하는 것이 아니라 중간지점부터 시작한다. 즉, 중간지점 이전에 계산해 놓았던 값을 활용한다. -> memoization -> recursive memoization에 활용할 자료구조는 미로의 모양대로 2차원 배열 table[i][j]의 i=n, j = m에 저장할 수 있다. dp table에서 초기값을 정의할 수 있다. base case 재귀 관계식을 정의할 수 있다. recurrence  문제를 읽고 위 요건들이 정의되었다면 재귀를 사용할 준비가 되었다. ====================================================== 어떤 지점 i, j에서의 dp[i][j]는 그 지점에서 준규가 가진 사탕의 최대 개수이다. 그리고 이 값은 문제에서 직관적으로 제시해준다. (실전 문제는 좀 더 문제 속에 숨어있다.) 준규는 현재 (1, 1)에 있고,  (N, M)으로 이동하려고 한다.  준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고,  각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두...

  코드는 깃헙 레포 참고 1. Brute force 포인터만 2개 활용하기는 했는데 로직이 그냥 이중 for문이라 투 포인터 풀이는 아님. 로직 p1 포인터는 수열을 순회하며 한 칸 씩 이동하고     이 순회 루프 내에서 p2 포인터는 p1+1 index부터 시작하여       - M이 total값보다 커지거나       - p2 index가 N에 도달할 때까지       array[p2] 값을 total에 합산함.     위 조건에 의해 p2 index의 nested loop가 탈출하면     - tot값을 검사하여 M과 일치하면 카운터 cnt 증가     - 초과해버리면 p1을 한 칸 씩 이동시켜 다음 루프 수행.  <최하단 제출> : Python3으로 제출하니 시간 초과됨. <그 위 제출> : Pypy3로 제출하니까 시간 내에 수행됨. 2. Two pointer 코드 right pointer, p2를 left로 초기화 시키지 않고 while문이 알아서 증가시키게 한다. 그렇다면 left pointer p1가 맨 바깥 for문에 의해 한 칸 이동하고 나서 partial_sum -= arr[p1]을 해 주는데,   left pointer, p1가 한 칸 이동함에 따라 l의 이전 원소를 빼주어 부분합 개념을 유지한다.  슬라이딩 윈도처럼 부분합의 range가 이동하는데 크기가 고정된 것이 아니라 partial_sum < M, p2 < N-1 의 조건에 따라 변화한다고 보면 된다. <최상단 제출> : Python3으로 제출했으며 시간, 메모리 면에서 우수 * Bonus   left를 고정시킨 뒤에는 r을 찾을 때,   M과 일치하는 r이 존재하는지 없는 지가 결정된다.      ...

Brute force 코드 1 : 메모리 초과 BOJ_1342_permu.py 1. from itertools import permutations 라이브러리로 입력받은 문자열에 대해서 모든 가능한 순열 조합들을 뽑아내었다. 그리고 이 조합들에 set을 취해 중복 조합을 걸러내었다. 1.1 문자열의 길이가 최대 10일 경우, 후보 case는 약 360만 개 (=10!) 1.2 후보 case의 인접 문자 2개씩 비교하는 비교 연산을 9 (10-1)라고 하면 총 약 3200만번의 연산이 필요. 2. 순열 조합의 문자들을 순회하며 인접한 문자열끼리 비교를 통해 행운의 문자열인지 아닌지 판별했다. # 메모리 초과 # Test case 4 경우 2.9s 소요 # 다른 방법 필요 비효율성 permutation으로 순열을 뽑으면 aabaa라는 문자열에서 각각의 a가 모두 다른 문자로 간주되기 때문에 많은 양의 중복 case가 발생한다. 단계1에서 permutation결과에 다시 set을 취하는 과정에서 많은 계산으로 인한 시간이 소요된 것으로 보인다. 대안 - 확률과 통계에서 배웠던 방법으로 중복 순열 Case를 처리하거나( N! / (a! b!) ) - 아래와 같이 set() 자료형에 tuple객체를 추가함으로서 중복을 처리할 수 있다. s = set() s.add(tuple(candidate)) # candidate는 permutation에서 나온 case 개수만 필요한 경우 전자, 중복 처리된 데이터까지 필요하다면 후자를 사용. 전자의 경우 dict를 통해 문자열에 어떤 문자가 몇 개 존재하는지 기록해도 좋지만, 원 문자열의 각 문자가 'a'~'z'라는 조건이 있으므로 set()으로 문자열 조합 하나하나를 비교하기 보다 수학 공식을 이용하여 산술적으로 처리하는 것이 더 빠르다. Brute force 코드 2 : 통과 BOJ_1342_permu2.py 1. 인접 문자들 조건을 만족하는 문자열 개수를 모두 센 후 2. 개수에서 산술적으로 중복된...

코드는 github repository 참고 상단이 recursive 하단이 itertools.combination으로 푼 코드이다. recursive로 푸니까 공간, 시간적으로 더 효율적이었다. 상단의 경우 재귀 함수를 호출하며 stack 메모리를 소비한다. 하단은 모든 경우의 수, 부분 수열 조합을 combination 모듈을 사용하여 리스트 형태로 메모리에 적재한 후에  리스트를 훑으면서 검사하는 알고리즘이다. 1182 문제의 조건과 제약사항에서는 두 방식을 사용해도 충분했다. 재귀 방식에 대한 보충 설명 def search (lev): global N, S, arr, choose, ans # print("current lvl : ", lev) # print("current choose : ", choose) # print() # base case if lev == N: if choose and sum(choose) == S: ans+=1 return # select elements whose index is lev choose.append(arr[lev]) # print("choosing") search(lev+1) choose.pop() # not choosing element whose index is lev (select next instead) # print("not choosing") search(lev + 1) N, S = map(int, input().split()) arr = list(map(int, input().split())) choose = [] ans = 0 search(0) # recursive method print(ans) 재귀 호출 시 함수에 전달되는 level 인자는 0부터 시작한다. 문제에서는 양의 길이의 부분 수열의 합을 검사하지만 코드에서 합을 계산하는 전제 조건에는 lev==N이 있다...

출처 https://school.programmers.co.kr/learn/courses/18/lessons/1878 코드 https://github.com/PapyrusNotes/Algorithm-note 세 점의 좌표가 주어졌을 때 나머지 한 점의 좌표를 구한다. 위 그림을 참고. 직사각형에는 같은 x 좌표값 2개와 같은 y 좌표값이 존재하는 특성을 이용한다. 파란색 사각형은 input값을 sorted후 순회했을 때 접근 순서이다. 내가 처음 접근한 풀이에서는 파이썬 list의 내장 메서드 remove를 사용하였기에 정렬하지 않았다.  코드 BruteForce/ 1. Rectangle_sol1.py = 내가 처음 접근한 풀이 2. Rectangle_sol2.py = XOR 비트 연산을 활용한 다른 사람의 풀이 XOR 비트연산에 참여하는 값들 중하나라도 다른 값이 있다면 다른 값이 반환된다.  A XOR A = 0 A XOR B = B A XOR A XOR A XOR B = B 정수 int 연산이 아니라 비트 연산임에 주의