개인적으로 공부한 내용을 정리중입니다.

// // main.cpp // algorithm_practice // // Created by 김동환 on 2020/04/12. // Copyright © 2020 김동환. All rights reserved. // #include #include using namespace std; int n,k; int dp[100001] = {0}; vector vec; int main(){ //freopen("input.txt","r", stdin); cin >> n >> k; //cout

거스름돈 문제 동전들에 배수관계가 성립할때만 한정. 대부분의 화폐는 1,5,10,25,50 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디로 해결된다. https://www.acmicpc.net/problem/5585 https://www.acmicpc.net/problem/11047 [https://blog.tomclansys.com/64] 위는 그리디로 되고 [https://mygumi.tistory.com/129] 여기는 dp문제도 준다. 동전1번 [https://www.acmicpc.net/problem/2293] 일단 이거 풀어야 되는데 잘 모르겠다. 음 분할 문제로 생각되서 접근하게 된다. 그래서 자꾸 재귀함수로 분할해 풀려고 한다. 일단 그냥 생각나는 풀이인 완탐으로 했는데 틀렸다. // ..

일단 내가 생각한 문제는, 동전이 다양한 금액으로 여러개 있을때, 두 사람한테 최대한 공정하게 분배하려면 어떻게 분배해야 할까. 나는 이 문제가 그리디라고 생각했다. 하지만 디피라는 의견이 있는데 왜 그런지 모르겠어서 다른 문제들을 찾아보고 문제 분석과 올바른 접근법을 생각해 보려 한다. https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다. www.acmicpc.net 음 일단 나중에 풀겠지만, 절반으로 정..

[https://www.acmicpc.net/problem/11400] 음 내가 생각한 풀이는 단절선은 단절점 - 단절점 단절점 - 혼자인 노드 (방금 단절점이랑만 연결된 노드인거) 라고 생각하고 했는데 틀렸다.;; #define _CRT_SECURE_NO_WARNINGS #define NUM 100002 #include #include #include #include using namespace std; vector edges; vector adj[NUM]; int order[NUM]; int arti[NUM]; int root = 1; //이게 첨에 1부터 되야지,,order를 0으로 초기화했잔아... int number = 0; int dfs(int u) { //prev는 해당 노드 이후로 가장 작..

그냥 리스트 두개를 더하면 되는거 같은데 왜인지 모르겠는데 런타임 에러 난다 .ㅠㅠ 말록을 잘못 사용하는거 같다. class Solution { public: ListNode * addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *ans = (ListNode*)malloc(sizeof(ListNode)); ListNode *cur = ans; while (l1->next != NULL || l2->next != NULL) { int sum = l1->val + l2->val; int up = 0; if (sum val = sum; up = 0; } else { cur->val = sum - 10; up = 1; } cur->next = (ListNode*)ma..

[https://leetcode.com/problems/two-sum/submissions/] 릿 코드 문제가 면접에 나오기 좋아 보인다.ㅎㅎ; 공부하자. 음 이 문제는 배열이 주어져 있을때, 특정 수가 되는 두 수의 위치를 구하는 것인데, 나는 어떻게 했냐면, 배열을 정렬하고, 합을 두 수로 만든다는 것에서, 작은 것과 큰것을 더하고 투포인터 방식으로 둘중에 한쪽을 줄여서 찾는 방식으로 풀었다. 이전에 백준에서 풀어본 문제라 그냥 자연스럽게 떠오른거 같다..... 근데 음 솔루션을 보니 1. 브루트 포스 2. 투패스 해쉬 테이블로 ,시간 절약 왜 투패스냐면 두번 이터레이트 하는데, 첫번째는 해쉬테이블에 값을 넣고, 두번째는 타겟과의 차이값이 해쉬테이블에 있는지 확인 하는것이다. 3. 원패스 해쉬 테이블..

[https://www.acmicpc.net/problem/17070] 근데 내 생각에 이 문제의 포인트는 파이프를 어떻게 저장할 것이냐다. 무슨 말이냐면 두칸다 저장할지, 한쪽 끝만 저장할지? 근데 생각해보니, 가로,세로,대각선이냐에 따라서 이동시킬 거니까, 왼쪽 끝 지점이랑, 회전 상태만 저장하면 될거 같다. 음 생각 보다, 제한 조건 부분에서 제한을 구현하는게 쉬운거 간다. 나는 전에 파이프가 길이가 2이지 않은가, 그걸 두개다 옮기려고 해서 코드 구현이 복잡해 졌다. 이번에는 state를 선언해서 가로,세로,대각선을 나누어 간단하게 표현했다. #define _CRT_SECURE_NO_WARNINGS #define debug 0 #include #include #include #include usi..

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 이게 근데 median이 중간값 아닌가? 예시2에 2.5인게 중앙에 위치한 값이 없..

음 이렇게 생각했다. 일단 A에 대해서 투포인터로 부분합을 좀 구하다가 , B에 대해서도 투포인터로 연산하면 된다고 생각했는데 틀린 부분이 A에 대해 경우가 다 나오지 않는다. #define _CRT_SECURE_NO_WARNINGS #define debug 0 #include #include #include #include using namespace std; #define NUM 100001 #define MAXV 987654321 long long int N, M,S; int arr[NUM],brr[NUM]; long long int T, A, B; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freope..

음 leet code trapping rain drop 문제가 이중포인터 카테고리에 있길래 이중 포인터 문제를 더 풀어본다. 첫번째 그냥 시간 복잡도 무시하고 생각해보면 왼쪽에서부터 쭉 가면서 거기서 부터 주어진 합을 만들 수 있는 부분 수열인지 알아 보면 된다. 근데 이러면 시간이 너무 오래걸린다. 그냥 여기서는 이중포인터로 하래서 생각난 방법인데 어떻게 떠오른지도 모르겠고, 검증을 못하겠다. 좌우끝에서 해당 배열의 총합을 구해놓고 하나씩 빼면서 좌우로 좁혀나가는 것이다. 일단 이렇게 좌우로 뺄 수 있으면 막 빼니까 원하는 S가 안만들어진다. #define _CRT_SECURE_NO_WARNINGS #define debug 0 #include #include #include #include using ..