야생가오리

https://school.programmers.co.kr/learn/courses/30/lessons/87946 순서를 정하는 데 있어 별다른 규칙이나 식을 세우기가 어렵고, 던전 개수는 최대 8개로 입력 크기가 작으므로 완전탐색으로 풀 수 있겠다.그럼 순열을 구하는 코드를 만들어보자. ✒️ 순열 구하기예를들어 배열 [1, 2, 3, 4] 에서 가능한 모든 순열을 구해본다고 치자그럼 일단 첫번째 원소가 1인 조합들을 고를 테니 [1, ( 나 머 지) ] 가 되고 그럼 저 나머지에서 가능한 모든 순열을 또 구하면 된다. 즉 재귀호출로 구현할 수 있다.첫번째 원소를 고정해두고, 나머지 원소 조합들로 재귀호출을 해준다. 종료조건은 정렬할 원소가 1개밖에 남지 않았을 때가 되므로 num === 1일 때로 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 장르이름과 재생횟수가 따로 배열로 주어지고, 각 노래는 고유번호 즉 인덱스로 구분한다.구해야 할 것은 일단- 장르별 전체 재생횟수의 합, 순서대로 정렬- 장르 안에서 재생횟수(같으면 고유번호) 순서대로 정렬 뭔가 이런저런 시도를 해봤는데 역시 "고유번호"가 유지되어야 한다는 점이 거슬렸다. 대충 벡터에 넣어서 소트하자니 순서도 없어지고... 장르별로 소트를 하고 그 안에서 또 따로따로 소트가 되어야 하고...결국에는 map을 사용해서 풀었다.장..

https://www.acmicpc.net/problem/1629  큰 수의 곱셈 문제가 있을 때 떠올리면 좋은 건 분할정복과 비트마스킹이다.a를 b번 곱할 때 반복문으로 b번 곱하는 것이 아니라, 지수를 반으로 나눠서 거듭제곱하는 방식이다. 물론 이때 지수가 짝수이면 그냥 반 갈라도 되지만 지수가 홀수이면 1을 하나 빼서 나눈 뒤 마지막에 한번 더 곱해줘야 한다.처음에는 그냥 비트마스킹만 생각했는데 그럼 2의 거듭제곱만으로 계산해야 하니 귀찮았다.. 단 숫자가 아주 커질 수 있기 때문에 그냥 계산하면 오류가 날 수 있으므로 계산 과정에서 매번 c로 나눈 나머지를 사용하도록 해서 오버플로가 나지 않게 해준다. b & 1 이라는건 비트마스킹에서 첫번째 비트가 1인 수와 and를 했을 때 true 즉 0이 ..

https://www.acmicpc.net/problem/1655 부른 수들 중에서 중간값을 찾아내야 한다. 짝수개면 둘 중 더 작은거무작위로 부른 수들의 정렬이 필요하니 우선순위 큐를 사용해야 함을  생각할 수 있다. 예시인 1, 5, 2, 10, -99, 7, 5 을 생각해보면크기순 정렬하면 -99, 1, 2, 5, 5, 7, 10이 되고 중간은 5가 된다.이걸 왼쪽(작은값들)과 오른쪽(큰값들)으로 나눠서 생각해보자. 이러는 이유는 우선순위큐에서 우리가 쓸 수 있는 값은 어쨌든 top값밖에 없기 때문이다. 중간에 든 걸 뺄 수가 없는 구조니까 우린 중간값이 top에 오도록 만들어주는 편이 좋다.그렇다면 왼쪽(작은값들)은 내림차순(최대히프)으로,오른쪽(큰값들)은 오름차순(최소히프)으로 정렬해준다면, 각..

https://www.acmicpc.net/problem/1052 용량 제한은 없고, 처음 상태에는 물 1리터가 들어있는 물병 N개한번에 옮길 수 있는 물병은 K개하고자 하는 것: 물을 재분배(같은 양의 물병 2개를 한쪽에 몰아넣음)해, 비어있지 않은 물병이 K개를 넘지 않도록 만들기 (찬 물병이 K개 이하가 되게)이걸 위해 새 물병(1리터가 들어있음)을 구매할 수 있음 ex) N=3, K=1이면물병 3개, 한번에 1개밖에 옮길 수 없다면1 1 1이 상태에서 재분배를 해도2 0 1 이 되므로 비어있지 않은 물병이 1개 이하가 될 수는 없다. 이때 물병 1개를 산다면, 물병이 4개가 되므로2 0 1 1이렇게 들어있을거고2 0 2 0이래되고4 0 0 0최종적으로 이렇게 될 수 있으므로 비어있지 않은 물병이 ..

https://www.acmicpc.net/problem/1043 거짓말쟁이가 되기시러각 파티의 참여자를 서로 연결하고, 타고타고 올라갔을때 진실을 아는 사람을 만나는지 안 만나는지를 확인해야 한다. 연결하고 찾는데는 유니온파인드를 사용한다.보자마자 이거다 하고 생각이 안 났다.. 사실 지금도 잘은 모르겠다 첨엔 걍 단순히 진실을 아는 사람이 파티에 섞여있는가를 따지는 문제인가 싶었는데, 같은 사람이 다른 파티에 참여해 다른 사실을 듣는 것 역시 안 된다는 조건 때문에 유니온파인드를 사용해줘야 했다. 우선 유니온파인드 구현은 언제나와 같다.vectorparent;int findParent(int node) { if (parent[node]  입력으로 진실을 아는 사람들이 주어진다. 이 사람들을 kn..

https://www.acmicpc.net/problem/1260 클래스 3 승급 필수문제가 하나 남았길래... 근데 이걸 안 풀었길래... ㅋㅋ3 에센셜에 그래프 탐색문제가 참 많은듯?? DFS는 이제 잘 쓴다void dfs(int idx, vector&ans_dfs){ visited_dfs[idx] = true; ans_dfs.push_back(idx); for(int i=1;i BFS큐!! 를 쓴다는 것을 꼭 기억할 것시작정점을 큐에 넣고, 그걸 빼면서 그 자식이 되는 정점들을 반복문으로 큐에 넣고... 반복void bfs(vector&ans_bfs){ queue q; q.push(v); visited_bfs[v] = true; while(!q.empty()){..

https://www.acmicpc.net/problem/10026 그래프에서 구역을 찾는 문제 = DFS. 이제 바로바로 튀어나온다적록색약인 사람과 아닌 사람의 차이는 R과 G를 똑같이 처리하냐 아니냐밖에 없으므로, 그냥 보드를 따로따로 만들고 함수도 (귀찮아서) 따로따로 만들어 각자 실행해줬다.visited 배열도 두 개 만들어도 될 테지만 이건 그냥 memset(visited, 0, sizeof(visited)) 로 초기화해서 재사용 반복문으로 상하좌우를 탐색.순환호출의 조건은 다음 좌표가 보드 안에 있을 것, 그리고 같은 색깔 즉 같은 char값을 가질 것이다. (visited가 방문되지 않았음은 당연하고)void dfs(int x, int y){ char color = board[x][y]..

https://www.acmicpc.net/problem/7662 시간제한 6초여서 어떻게 문제 시간제한이 6초? 했는데 6번의 시도 6번의 시간초과로 얕본 업보를 받음문제자체는 단순하다... 수를 입력받고 명령에 따라 최댓값이나 최솟값을 삭제하기. 1트로는 그냥 깡 배열에 저장하고 최대냐 최소냐 입력받는 것에 따라 매번 sort를 통해 재정렬 후 삭제했다. 당연하지만 시간초과다. 쓰면서도 안 될 것 같았다그럼 제목에도 나와있듯 우선순위 큐를 쓰긴 써야 할 것 같은데, top이 최소냐 최대냐는 최소히프냐 최대히프냐에 따라 달라지므로 우선순위 큐 두 개가 필요하다.두개를 만들어서 저장해서 쓴다고는 치자. 문제는 두 큐를 동기화시키는 것이다. 최솟값 빼래서 최소히프에서 뺐는데 최대히프에서는 안 빼면 나중에 ..

https://www.acmicpc.net/problem/11399 최소 시간(전체)이 되도록 순서를 정하라는데전체 기다리는 시간이 줄어들려면 그냥 빨리끝나는 사람부터 뽑으면 된다.매 상황마다 가장 빨리 끝날 수 있는 사람을 뽑아나가면 그게 곧 최소시간이 된다.= 그리디를 써라#include #include #include using namespace std;int main(){ int n; cin >> n; vector arr(n); for(int i=0;i> arr[i]; } sort(arr.begin(), arr.end()); int answer = 0; for(int i=0;i