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

스위프트로 구현한 코드이다. 고민했던 점은 이걸 완전탐색으로 하는 수 밖에 없나 고민했었다. 근데 수식도 100자리 이하고, 연산 우선순위 바뀌는 경우도 12가지라 시간 복잡도를 계산하면 1초안에 들어와서 완탐을 목적으로 낸 문제가 맞다 생각했다. (다른 효율적인 방법이 있다면 댓글좀 ㅠㅠ) 또 고민의 과정은, 문자열을 어떻게 리스트로 파싱할지, parse는 안된다는 결론이 났다. +-*/ 네가지로 분할해야 되서, 그래서 리스트로 순회하면서 숫자랑 연산기호를 따로 읽고 저장하는 식으로 했다. 이제 연산을 해야되는데, 일반적으로 스택을 사용한 연산을 하는걸 알고 있다. 그런데 오래되서 스택으로 하는 방법을 아무리 생각해도 안나더라.,... 쉬운문제 부터 다시 해봐야 겠다. 그래서 스택을 사용하지 않고 리스..

[https://programmers.co.kr/learn/courses/30/lessons/49188] 문제 링크 여기를 좀 참고했다. 노드를 제거하고, 사이클이 존재를 확인하는 방법을 내가 아는 걸로는 dfs였다. 근데 이건 시간 초과이니까;; 그래서 disjoint set으로 확인 가능한가 고민해봤는데 내가 생각하는 선에서는 안되는거 같은데 [https://jackpot53.tistory.com/92] 아 이분말 보니까, 유니온파인드를 하고나서, 확인할 수 있는게 아니라, 하는 과정에서 확인이 되네;; 음 만드는 과정에서 확인할 수 있다는 생각은 왜 못했지; 그래서 유니온 파인드로 하면 각 노드 없다 치고, 각 노드 없다 칠때마다 유니온 파인드 해야되니까, 5000 * 5000쯤 이겠다. 대신에 밸..

가장 먼 노드. #include #include #include #include #include #define N 20001 using namespace std; bool visit[N] = { 0 }; vector adj[N]; //stack st; int maxv = 0; vector ans; queue q; queue dep; void dfs(int cur,int depth) { if (depth == maxv) { ans.push_back(cur); } if (depth > maxv) { maxv = depth; ans.clear(); ans.push_back(cur); } for (int i = 0; i < adj[cur].size(); i++) { if (visit[i] == 0) { visi..

체육복 음 이 문제를 모든 경우를 생각한다 해보면, 앞뒤로 학생이 빌려주는지 확인한다. 그러면 30명이니까 2^30이 된다 .....그러니까 아님 그래서 탐욕법을 사용하나 보다. 그냥 쉽게 생각해보면 빌려주려는 애가 앞뒤로 옷이 없으면 누굴 줘야 되는 지가 문제다, 자기 뒤에 친구가 옷이 있는지 보고 없으면 그 뒤에 친구가 여분이 있는지 확인하면 될듯?뒤에 친구가 여분이 있으면 앞에 친구 옷 빌려주면 되고, 뒤에 애들도 옷이 없으면 앞에 친구 빌려주면 되지 않을까?? 아니 그냥 앞에사람 빌려주면 되는듯 앞에 사람이 있으면 뒤에사람 맞았다. #include #include using namespace std; int student[31] = { 1 }; int solution(int n, vector lo..

음 비형 대비 내가 일단 다 구현해 보는데 벡터 값은 정렬을 어떻게 하지? 콜 바이 레퍼런스로 넘기면 될듯?? 일단 정렬 코드를 작성했다. 파티션 부분에서 while문 종료되고 마지막에 피벗이랑 i 위치랑 스왑하는걸 빼먹어서 안됬었다. left budgets[j]) { swap(&budgets[i], &budgets[j]); i++; } j++; } swap(&budgets[pivot], &budgets[i]); return i; } void qsort(int left,int right,vector&budgets) { if (left < right) { int pivot = partition(left, right, budgets); qsort(left, pivot - 1, budgets); qsort(p..

모의고사 이건 그냥 하면된다. ㅋㅋ 소수찾기 음 이게 좀 문젠데, 소수를 조합하는거랑 소수인지 확인하는 두가지 과정이 필요해 보인다. 음 이런 문제에서 항상 궁금했었다. 갯수 별로 잘라서 그걸 순열로 해야되는건가?!?!? 만들고 그게 소수인지 아닌지 확인하고, 중복인건 배열로 체크해서 제외하도록? 순열 알고리즘 구현을 찾았다. https://gorakgarak.tistory.com/522 순열(Permutation) 알고리즘 1,2,3 와 같은 숫자들이이 있다. 이것을 중복하지 않고 순서를 끌어내는 방법을 생각해보자 1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1 여섯가지 방법이 존재한다. 이제 숫자 네개인 1,2,3,4를 한번 섞어본다. 1-2-3-4.. gorakgarak.tistor..

https://hongku.tistory.com/149 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현) 퀵 정렬 (Quick sort) 특정한 값(Pivot)을 기준으로 큰 숫자와 작은 숫자를 구분하자 '분할 정복' 알고리즘으로 평균속도가 O(N * logN) 이다. 퀵정렬에는 기준이 되는 값이 존재한다. 이때, 기준값을 피봇(pivot).. hongku.tistory.com 정렬 코드 수정할때 참고 했다. K번째 수 #include #include #include using namespace std; void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } void sort(int st, int dt, int*arr) { if (st..

이 파트에 되게 취약하다..... 전에 전공 복습에서 힙을 공부 했었다. 이번에는 c++로 객체 지향으로 구현해 보자. 문제는 최소 힙을 구현하면 된다. 그리고 최소힙 팝, 푸쉬를 구현하면 된다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) scoville의 길이는 1 이상 1,000,000 이하입니다. K는 0 이상 1,000,000,000 이하입니다. scoville의 원소는 각각 0 이상 1,000,000 이하입니다. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다. 길이가 100만이다. 음 힙을 구현하느라 애를 많이 먹었다. 버블 다운 방식, 바텀 업 방식. #include #inc..

전에 테스트때 풀었던 문제이다. 그런데 그때 구현이 틀렸다. 근데 틀린 원인이 내 생각에는 설계를 잘못한듯. 완전 탐색이긴 한데 , bfs도 어떻게 수행할지 조건들에 대한 내용을 결정하고 , 그것을 깔금하게 구현해야 할듯. 나는 이동할 수 있는 경우가 몇가지인지 제대로 파악 안하고 시작했다. 그리고 일단 로봇의 상태를 어떻게 표현할지 부터 정했어야 했다. 로봇의 상태를 어떻게 표현할지 정확히 생각하고, 배열의 범위 확인도 함수로 구현해서 확인 후 그 함수 내부에서 큐에 넣도록 하니까 깔금하게 금방 구현했는데, 예제만 맞고 테케는 한개만 맞는다..... 왜그러지 ㅠ #include #include #include using namespace std; enum { ver = 1, hori = 2 }; str..

프린터 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 1번은 수행이 매우 단순하다. 2번 부분에서 뒤에 중요도가 높은 문서가 한 개라도 존재하는지가 문제 해결의 부분인거 같다. 내 생각에는 맨 처음에 대기 목록에서 맨 앞에 것을 제외하고 가장 높은 우선 순위를 max_priority에 저장한다. max_priority > J 이면 J를 대기 목록 맨 뒤에 넣는다. max_priority < J이면 출력하고 order를 1 증가한다 . J가 location이면 order를 출력한다. 근데 max_priority는 뒤에 가장 ..