devlog

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법order, orders의 크기가 작으므로 완전탐색 + 조합의 문제인 것을 확인할 수 있다. 이제 조합을 어떻게 구현할지에 대해 생각을 해보아야 한다. course마다 돌아가며 모든 조합을 딕셔너리에 보관하는 방법으로 풀이했다. 여기서 중요한 점은 map의 초기값은 자동으로 0으로 할당이 된다는 것이다. 즉 combination [temp]++ 를 수행하기 위해 temp키 값이 초기화되어 있으면 +1, 초기화 되어 있지 않으면 ..

출처 : https://www.acmicpc.net/problem/20055 풀이 방법 단순 시뮬레이션 문제이다.배열의 범위만 잘 고려하면 풀이할 수 있다. (중간에 -1을 하는 과정에서 다시 시작 위치로 초기화하기, 음수가 안되게 +2n을 한 후 % 2n연산하기)문제에 한 칸에 로봇이 2개 이상 올라갈 수 없다는 조건이 없어 애매했지만, 한 칸에는 로봇이 1개만 올라갈 수 있다. 핵심 아이디어 1. 벨트 회전(rotate) • 실제로 배열을 돌리는 대신, “시작 인덱스(startIndex)”를 조정하는 방법을 쓴다. • 예: startIndex를 1 감소(startIndex = (startIndex - 1 + 2N) % (2N))시키면, 컨베이어 벨트가 시계 방향으로 한 칸 돌아간 것과 같은 효과를 낼..

출처 : https://www.acmicpc.net/problem/10775 풀이 방법처음에는 그리디한 방법으로 자신이 연결 가능한 가장 큰 게이트부터 차례대로 1씩 줄이며 가능한 곳에 연결하는 방법을 생각했지만, 이는 계산해 보니 시간초과가 난다.그러므로 다른 방법이 있어야 하는데 도저히 생각하지 못했다. 다른 사람의 풀이를 보니 유니온파인드를 사용해서 풀이하고 있었다.자신의 부모와 자신의 부모 -1한 값을 유니온 하는 방식으로 풀이하면 된다. 그러다 자신의 부모가 0이 되는 값이 발생하면 종료를 해주면 된다.  #include using namespace std;int g, p;int gate[100001];int parents[100001];int find(int a) { if (a == paren..

출처 : https://www.acmicpc.net/problem/23291풀이 방법 구현 문제이다. 각 step에 따라서 함수를 나누고 구현을 했다. 먼저 문제를 풀이하기 전에 고려해야 할 자료구조를 생각해 보자어항을 관리해야 한다. 어항에서 step을 보면, 물고기를 한 칸 올린 후 90도 또는 180도를 돌리는 과정이 있다.이를 구현하기 위해 2차원 배열을 선택했고, 90도, 180도 돌린 후 기존 어항 위에 올려놓아야 하므로 처음 시작을 y = n-1에서 시작했다. 각 step에 대해 살펴보자 step1가장 작은 물고기의 인덱스를 찾아 +1을 해주면 된다.void step1() { // 가장 작은 물고기 인덱스에 +1 해주는 함수 int min_v = 987654321; vector m..

출처 : https://www.acmicpc.net/problem/1790 풀이 방법 1. 문제 접근:단순히 1부터 시작하는 모든 수를 문자열로 이어 붙여서 k번째 문자를 찾는 방식은 시간 초과를 유발한다. 따라서 각 자릿수 별로 숫자가 몇 개나 등장하는지 계산하고, 이를 이용해 빠르게 k번째 문자가 어느 범위(몇 자릿수)에 속하는지 판단해야 한다. 2. 자릿수 범위별 숫자 개수: • 한 자릿수: 1~9 ⇒ 총 9개 • 두 자릿수: 10~99 ⇒ 총 90개 • 세 자릿수: 100~999 ⇒ 총 900개 • …일반적으로, d자리 수는 9 \times 10^{d-1}개 존재한다. 3. 자릿수 범위별 문자(숫자) 개수:각 자릿수 범위 내 숫자가 N개라면, 문자열로 이어 붙일 때는 각 숫자가 d자리이므로 총 N..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150367# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 방법문제를 이해한다. 트리에서 중위순회를 통해 빈 노드는 0, 존재하는 노드는 1로 표현된다는 것을 알 수 있다. 또한, 문제의 예시에서 7과 42가 같은 트리로 표현되며, 42는 생략된 노드가 많아 이러한 표현이 가능하다는 점을 이해한다. 문제 풀이 방법 1. 10진수를 2진수로 변환한다. 2. 2진수를 완전 이진트리로 변경할 수 있도록 부족한 노드 수만큼 앞에 0을 추가한다. 2진수에 생략된 0을 추가하는 과정 완전 이진트..

출처 : https://www.acmicpc.net/problem/31797 풀이 방법이 문제를 풀며 실제 아파트 게임과 다른 점은 중간에 빈 층도 있다는 것이다.이 부분을 고려하지 못해 문제를 틀렸다.증간에 빈 층을 처리해 주기 위해 hand [i] == 0인 경우 층수를 update 하지 않았다. 또한 참가자의 손 수는 M*2이므로 M*2보다 큰 경우 N % (M*2)를 해주면 된다. 만약 해당 값이 0이라면 마지막 층인 M*2로 구해주면 된다. #include using namespace std;int n, m;int hand[10001];int main() { cin >> n >> m; // n = 층수, m = 참가자 수 int idx = n % (m * 2); if (i..

출처 : https://www.acmicpc.net/problem/3197 풀이 방법 처음에는 매 번 visited를 초기화하고 BFS를 두 번씩 수행하면서 얼음을 녹이고, 백조가 만날 수 있는지 확인하는 방식을 사용했다. 그러나 이 방법은 시간 초과가 발생한다. 이를 개선하기 위해, 다음 턴에 녹일 얼음을 따로 큐에 저장해 두고, 해당 얼음들만 녹인 뒤 인접한 얼음을 다시 큐에 넣는 방식으로 변경한다. 이렇게 하면 불필요한 중복 연산을 줄여 얼음을 녹이는 알고리즘의 시간 복잡도를 낮출 수 있다. 백조가 만날 수 있는지 확인할 때에도, 첫 번째 백조 위치에서 BFS를 진행하며 물과 인접한 얼음을 별도로 저장한다. 이후 턴에서 그 얼음이 녹았는지 확인한 뒤, 녹았다면 그 지점부터 다시 BFS를 탐색하며, ..

출처 : https://www.acmicpc.net/problem/2042 풀이 방법 구간 합을 구하고, 요소를 변경하고 구간 합을 또 구하니 세그먼트 트리를 사용하면 된다. 세그먼트트리 구현 시 주의점세그먼트트리의 인덱스는 1부터 시작한다.node와 배열의 idx는 다르다build함수 구현시 start == end일 때 tree [node] = arr [start]이다.update를 할 때 원래 배열값과 차이인 diff값으로 업데이트를 진행한다.tree의 노드의 수는 일반적으로 n * 4로 잡는다.#include using namespace std;int n, m, k;long long arr[1000001];long long tree[4000004];long long build(int start, i..

특징트리의 모든 노드들은 오른쪽, 왼쪽 서브트리의 높이 차이를 {-1, 0, 1} 중 하나를 가짐노드 추가, 삭제 후 조건을 만족시키지 않는다면, 균형을 맞추는 작업을 진행한다. 노드 하나 씩 검사하며 만족하지 않는 노드가 발생한다면, 해당 노드에서 작업을 수행하면 된다.만족하지 않는 경우70에서 만족하지 않으므로 70을 기준으로 오른쪽 회전을 한다.60은 70이 원래 자신의 왼쪽 자식이 있었지만 비게 되었으므로 60을 70의 왼쪽 자녀로 해준다.노드의 삭제에서2번의 단계가 필요한 경우아래와 같은 경우 노랜 색만 집중을 해보면 60이 루트로 가야 완전 이진트리가 된다.1단계70을 기준으로 오른쪽으로 회전해 60을 70자리로 올려준다.2단계50을 기준으로 왼쪽 회전을 한다.이러면 완전 이진트리가 완성된다...