__Main__

https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 📌 - 처음 생각한 풀이 예상 등수를 정렬 1씩 증가하면서 예상 등수랑 차이를 더함 - 풀이가 분명히 맞다고 생각해서 제출을 했는데 틀림 - 숫자를 보니 50만까지 증가할 수 있는데 최악의 경우 에상등수와 실제 등수의 차이가 최대치로(ex - 예상등수 50만등, 실제 1등) 날 경우가 50만개 있는 경우 int타입을 벗어나서 틀리게 됨 📌- 풀이 예상 등수를 정렬 1씩 증가하면서 에쌍 등수랑 차이를 더 ..

https://www.acmicpc.net/problem/12785 12785번: 토쟁이의 등굣길 인하대학교에 다니는 토쟁이는 y축과 평행한 w개의 도로, x축과 평행한 h개의 도로가 있는 도시에 살고 있다. 토쟁이의 집은 이 도시의 맨 왼쪽 아래에 위치하며 좌표로는 (1, 1)로 표시할 수 있다. www.acmicpc.net - 처음엔 간단하게 생각해서 BFS로 구현을 했었는데, 풀고나니 메모리 초과가 발생해서 다시 dp로 풀었다. 📌 - 풀이 이 문제는 결국 출발점 -> 토스트 집의 경로 * 토스집의 경로 -> 도착점까지를 구하는 문제인데 DP를 이용해서 해당하는 경로까지의 경우의 수를 업데이트 해주고 경로의 수를 곱해주면 결과값이 나온다. 🔥 - java code package DP.S1_12785..

https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 코딩테스트 언어를 python에서 java를 바꾸는 과정에서 문제들의 유형들을 여러가지 풀어봐야할 것 같아서 DFS 문제로 정하고 문제를 품 📌 - 처음 생각한 풀이 DFS로 완전탐색을 하면서 부등호에 맞는 모든 경우의 수를 List에 저장 list의 크기가 N+1이 됐을 때, 리스트에 있는 모든 값들을 str에 순차적으로 저장 str을 long으로 형변환 하면서 크기 비교 -> 최솟값과 최댓값 비교해서 저장..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 📌 - 로봇 청소기 DFS, BFS 문제로 풀어야 하는지 고민했는데, 단순 구현으로 풀어도 시간복잡도가 초과되진 않아서 단순 구현으로 품 이동, 방향전환 함수를 따로 만들어서 로봇 청소기의 움직임을 조금 더 보기쉽도록 구현함 구현문제는 주어진대로 구현만 하면 되는데, 로봇 청소기는 문제를 이해하는데 생각보다 조금 오래 걸렸던 것 같다. 현재 위치 ..

📌 - RB트리 삭제 int rbtree_erase(rbtree *t, node_t *z) { node_t *y = z; // 삭제하려는 노드 z를 우선 y에 저장. node_t *x; color_t y_original_color = y->color; // y의 컬러를 저장 if (z->left == t->nil){//유효한 값을 가진 자식이 오른쪽에만 하나 있는 경우 x = z->right; //오른쪽 자식을 x에 담아두고 transplant(t, z, z->right); //z의 오른쪽 자식을 z에 위치에 이식(transplant)하면서 z는 제거 }else if(z->right == t->nil){//유효한 값을 가진 자식이 왼쪽에만 하나 있는 경우 x = z->left; transplant(t, ..

📌 - RB트리 Insert 🚀 - 트리 생성 rbtree *new_rbtree(void) { rbtree *p = (rbtree *)calloc(1, sizeof(rbtree)); // TODO: initialize struct if needed node_t *nil = (node_t*)calloc(1,sizeof(node_t)); nil -> color = RBTREE_BLACK; p->nil = p-> root = nil; return p; } 🚀 - 노드 삽입 node_t *rbtree_insert(rbtree *t, const key_t key) { // TODO: implement insert node_t *new_node = (node_t*)calloc(1,sizeof(node_t)); //..