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

이번에는 이차원 배열을 함수형 프로그래밍으로 구현해보자. 첫 구현은 실패해서 일단 스위프트로 구현하는 것에 의의를 두고 통과한 코드이다. import Foundation var maxCache = [Int:Int]() let n = Int(readLine()!) //print(n) //text = x?.split(separator: " ") for i in 0 .. Int in return (Int(val)!)}))! //let tmp = readLine()?.components(separatedBy: " "..

거스름돈 문제 동전들에 배수관계가 성립할때만 한정. 대부분의 화폐는 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/17070] 근데 내 생각에 이 문제의 포인트는 파이프를 어떻게 저장할 것이냐다. 무슨 말이냐면 두칸다 저장할지, 한쪽 끝만 저장할지? 근데 생각해보니, 가로,세로,대각선이냐에 따라서 이동시킬 거니까, 왼쪽 끝 지점이랑, 회전 상태만 저장하면 될거 같다. 음 생각 보다, 제한 조건 부분에서 제한을 구현하는게 쉬운거 간다. 나는 전에 파이프가 길이가 2이지 않은가, 그걸 두개다 옮기려고 해서 코드 구현이 복잡해 졌다. 이번에는 state를 선언해서 가로,세로,대각선을 나누어 간단하게 표현했다. #define _CRT_SECURE_NO_WARNINGS #define debug 0 #include #include #include #include usi..

별찍기 10 음 모르겠다.... 그 이전 것들은 쉬웠는데 이것을 참고 했따. 프랙탈 처럼 뭔가 같은 모양이 반복된다는 건 알겠었는데 한줄씩 출력해야 될것이라 생각 했다. 전체를 배열로 놓고 채울 생각을 못했따. 전에 그냥 줄게 관계 없이 하면 좋겠다는 생각 정도는 했었는데 분할정복이라니.... 스스로 구현해볼라했는데 분할 정복의 코드를 모르는거 같다.;; #define _CRT_SECURE_NO_WARNINGS #define debug 0 #include #include #include #include #include #include #include using namespace std; #define NUM 3001 #define MAXV 10000001 long long int N, M, S; char..

게임 음 틀렸다. 왜 틀렸지 처음에는 일단 분모를 안바꿔줘서 틀렸었다. #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]; vectoras, bs; long long int T, A, B; int X, Y, Z; int divd(int x, int y) { return (int)(((double)x / (double)y)*100); } int main() { ios_base::sync_with_stdio(false..

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

달리기 *일단 나는 머지소트로 했는데 [https://justicehui.github.io/koi/2019/03/03/BOJ2517/] 여기보면 세그먼트 트리도 된다 함 아직 안해봤다 난 그리고 비슷한 문제로 [https://www.acmicpc.net/problem/10090] 앞에 자기보다 큰게 몇개 있느냐는 문제이다. 2 8 10 7 1 9 4 15 최악의 시간 복잡도로라도 생각하면 그냥 하나씩 고르고 그 앞을 쭉 보면서 자기보다 큰게 몇개인지 세어보면 된다. 근데 그러면 O(n^2)이겠지.... 음 이런식으로 고르고 오름차순 정렬이되 도록 올려주면 결국 되긴한다. 근데 문제가 그러면 효율적으로 올려서 정렬되는게 아니라는거. 여기서 방법으로 머지소트 방식을 떠올릴 수 있겠다. 근데 구현했는데 틀렸다..

스도쿠 ( 백트레킹 문제를 더 고민해보자!!, 이전에 백트레킹인줄 몰라서 틀린게 좀 있는거 같다. 카카오 원판 순회?) 음 완전탐색해야 될거 같다. 가능한 놈들을 추려서 결국에 가능한 한가지 경우만 도출하면 될거같은데 구현 방법이 떠오르지 않는다. 후보를 어떻게 저장해야 될까, 각 칸마다 저장하는건 올바르지 못한거 같다. 각 행,열 마다 후보들을 저장해놓자. 그리고 3x3 그리드 마다 가능한 후보들을 저장해 놓자. 그리고 각 칸마다 가능한 놈들을 행,열,그리드에서 공통인 것을 찾으면 될거 같다. 일단 테스트 케이스는 맞았는데 처음에는 틀렸었다. 틀린 이유는 행,열,그리드 모두를 만족하는 숫자를 넣어줘야 하는데 그걸 구현을 잘못했었다. 다시 한 방법은 bool num_r[10] = { 0 }; bool n..

2504번 괄호의 값. 내 코드 #include #include #include #include #include using namespace std; using li = long long int; string str = ""; int idx = 0; stack st; bool flag =true; void pushStack(char x) { if (x == ')') { if (st.size() > 0) { if (st.top() == '(') { st.pop(); } else { flag = false; } } else { flag = false; } } else if(x==']'){ if (st.size() > 0) { if (st.top() == '[') { st.pop(); } else { flag..

1517번 각 숫자 보다 오른쪽에 큰 숫자가 몇개있는지 구해서 다 더하면 될거 같다. 생각 나는 방법1. 그냥 오른쪽으로 쭉 가면서 갯수를 다 세어본다. -> 이건 시간초과; 문제 카테고리상 세그먼트 트리이다. 세그먼트 트리는 분할 정복의 느낌이 조금 있는거 같다. 음 모르겠다. 노드 두개를 병합해서 새로운 노드를 만들때 어떠한 정보를 저장해야 답을 구할 수 있을 텐데 그것을 모르겠다. 12015번 : LIS 방법 6 10 20 10 30 20 15 1 2 1 2 1 1 1 2 1 3 2 2 dp[n] : n번째까지 가장 긴 부분 수열의 길이. dp[n] = (이전에 가장 긴 부분 수열의 연장됨(가장 긴 수열의 마지막 위치와 수를 저장하자) , 현재의 n번째가 처음 시작 수열로 한다) dp에 도대체 무슨..