devlog

출처 : 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..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법일반적인 dfs로 풀이할 수 있다.방향의 우선순위를 d l r u로 dy, dx를 설정해 사전순으로 dfs를 방문하도록 설정을 했다.또 사전순으로 탐색을 했기 때문에 만약 도착지에 도달을 하게 된다면, 탐색을 멈추고 답을 도출했다. 또 시간을 줄이기 위해 K에서 출발지와 도착지의 거리의 차가 2로 나누어 떨어지지 않는다면, 도착 불가능한 경우이므로 제거했다. 또한 중복 탐색을 방지하기 위해, y, x지점에 cnt의 횟수를 가진..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법특정 알고리즘을 사용한다기보단 특징과 조건을 잘 찾고 엣지 케이스만 확인 잘하면 된다. 1. 중앙 노드 찾기먼저 아무 모형과 관련이 없는 중앙 노드를 찾으려고 특징을 살펴보았다.문제의 제한 사항에 모든 그래프의 수의 합은 2 이상이라는 점에서 들어오는 edge가 없으며, 나가는 edge가 2개 이상인 노드를 중앙 노드라고 판별할 수 있다. 2. 각 그래프 구별하기  1. 막대 그래프: • 그래프 내에 나가는 간선(out_edg..

출처 : https://www.codetree.ai/training-field/frequent-problems/problems/medusa-and-warriors/submissions?page=1&pageSize=10 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai개요2024년 하반기 삼성 코딩테스트 당시 해당 문제를 푸려고 했으나, 생각보다 고려해야 할 조건이 너무 많고 코드가 길어지면서 잔실수도 많이 나와 실수를 잡는데만 시간을 많이 소요했고 4시간 만에 풀이하기엔 부족했던 거 같다. 시험이 종료 후 다시 풀어보려고 한다. 풀이 방법우선 해당 문제는 ..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/250134 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법주의할 점 dfs 백트레킹백트레킹에서 전역 변수를 최대한 덜 사용하고 문제를 최대한 분리하기 위해 함수의 인자로 넘길 것 최대 크기가 4x4 밖에 안되므로 완전 탐색 + 백트레킹으로 생각해 볼 수 있다. 조건에 맞게 서로 교차되는 경우, 같은 곳에 이동하는 경우, 방문한 곳에 다시 방문하는 경우를 하나씩 잘 구별해 주면 된다. 또한 공이 도착하지 않은 경우에만 이동시켜주어야 한다. 이 부분에서 크게 실수를 했다.if (g_ma..

출처 : https://www.acmicpc.net/problem/6549 풀이 방법대표적인 분할 정복의 문제이다.왼쪽에서 가장 큰 사각형, 오른쪽에서 가장 큰 사각형, 경계 지역 사각형을 포함하는 사각형 중 가장 큰 사각형을 찾으면 된다.  가장 중요한 부분은 경계 지역을 포함하는 사각형의 최대 크기이다.주의 히스토 그램이 위와 같을 때 파란색 부분과 검은색 부분도 while문을 사용해 다 계산을 해주어야 한다. 기저 조건으로 start == end, end - start == 1인 경우로 설정했다. 실수한 점 넓이는 long long을 사용했다. 하지만 밑변과, 높이는 int이였다.long long width = height * (end - start)위와 같이 식을 작성했는데 연산 순서가 int끼리..