devlog

출처 : 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://www.youtube.com/watch?v=bqkcoSm_rCsB tree아래와 같이 이진트리에서 확장해 자녀에 3개의 값을 저장하고 싶어 사용한 트리이다. 자녀를 최대 몇 개까지 가질 수 있게 할 것이냐가 중요하다.파라미터M = 각 노드의 최대 자녀 노두 수M-1 = 각 노도의 최대 key 수[M/2] = 각 노트의 최소 자녀 수 (루트랑 리프노드는 제외한다.)[M/2] - 1 = 각 노드의 최소 key 수  특징internal 노드의 key 수가 x라면 자녀 노드의 수는 언제나 x+1개이다.그러므로 아래와 같은 경우는 존재하지 못한다.즉 노드는 최소 하나의 key를 가지기 때문에, 몇 차 b tree인지 상관없이 최소 두 개의 자녀는 가진다.M이 정해지면 root를 제외하고는 ..

출처 : https://www.youtube.com/watch?v=2MdsebfJOyMnill 노드란존재하지 않음을 의미한다.자녀가 없을 때 자녀를 nill노드로 표현한다. 값이 있는 노드와 동등하게 취급한다.모든 nill노드는 블랙이다.레드 블랙 트리 특징루트 노드는 블랙, 모든 노드는 블랙 혹은 레드이다.레드가 연속할 수 없다.모든 Nill노드는 블랙이다.(리프노드)레드의 자녀는 모두 블랙이다.임의의 노드에서 nill노드까지의 블랙 노드의 수는 동일하다 (본인 제외)블랙 height = 노드 x에서 임의의 자손 nill까지 갈 때 경로의 모든 black의 수는 같다.부모와 두 자녀의 색을 바꾸어 주어도 5번 속성은 유지된다. 트리들의 삽입, 삭제하며 위 속성을 맞추다 보면 균형된 트리가 만들어진다...

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

출처 : https://www.acmicpc.net/problem/9466 풀이 방법 사이클을 찾는 문제이다.사이클을 찾기 위해서, group을 만들고 dfs로 탐색을 했다.group을 저장하기 위해 visited 배열을 사용했고, 해당 그룹에서의 사이클 원소 개수를 저장하기 위해 cnt_arr를 사용했다.만약 visited가 0이라면 자신이 그룹의 시작으로 설정하고 탐색을 한다. 그러다 다음 원소가 자신의 그룹가 같다면 사이클이 완성되었다는 뜻이고, 그룹 중에서 몇 번째로 방문한 원소인지를 통해 사이클의 원소 개수를 구할 수 있었다. 풀이 #include #include #include using namespace std;int t, n;int visited[100001];int cnt_arr[1000..

개요PGP방법이 아닌 S/MIME에 대해 알아보자S/MIME는 MIME에 보안기능을 추가한 것이다.S/MIME에 대해 알아보자 Overview MIME란  초기의 이메일은 단순히 텍스트만 지원했다.MIME는 여러 콘텐츠 (텍스트, 이미지)등을 포함할 수 있게 하기 위해 개발이 되었다.  S/MIME S/MIME의 다양한 유형과 보안 적용 방식 이중 목적에 따라 하나를 사용하거나 여러 개를 결합하여 사용가능하다. 1. Enveloped data암호화된 메시지 + (메시지를 복호화할 수 있는 키) 암호화2. Signed data인코딩 된 메시지 + 디지털 서명 해시 값(signed digest를 포함한다.)3. Clear-signed data원본 메시지 +인코딩 된 디지털 서명 해시 값4. signed & ..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/340212 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법통과할 수 있는 level 중에 가장 작은 level을 선택해야 한다. 해당 부분을 통해 이분 탐색을 이용한 완전 탐색으로 풀이해야 겠다고 생각했다.문제에서 해결을 못하는 경우는 없다고 했으므로 가장 최댓값을 limit으로 최솟값을 1로 설정하고 이분 탐색을 진행했다.이때 해당 level로 통과를 할 수 있다면 right = mid -1로 하여 작은 level에 대한 시도를 하며통과를 하지 못한다면 left = mid + 1을..