코딩관계론

문제 이해하기 주어진 그래프에서 임의로 삽입된 노드를 찾고, 막대 그래프가 몇 개인지, 도넛 그래프, 8자 그래프가 몇 개인지 찾는 문제였다.여기서 중요한 점은 그래프를 순회해서 모양을 판별하는 것이 아니라, 노드와 간선의 개수를 가지고 어떤 그래프인지 판별하는 것이다. 문제 해결 방법 설명하기 1. 먼저 어떤 정점이 임의로 삽입된 정점은 진출차선만 있는 노드라고 생각했다. 2. 당연히 원래 있던 그래프에서 임의로 정접을 삽입했다고 했으니 해당 정점은 강제로 이어진 것 따라서 진출차선만 있어야 함 3. 그 다음 dfs를 사용해서 그룹을 나눴고, 해당 그룹에는 몇 개의 노드와 엣지가 있는지 계산했다. 4. 모든 노드를 순회했다면, 그룹의 노드와 엣지 정보를 토대로 어떤 그래프가 있는지 판별했다. 코드 im..

문제 이해하기 시추관을 세로로 뚫었을 때 최대 몇 개의 오일을 뽑을 수 있을까를 묻는 문제였다. 아래 그림과 같이 7번으로 뚫었을 때는 총 9개의 오일을 뽑을 수 있는 것을 볼 수 있다 문제 해결 방법 설명하기 1. DFS알고리즘을 이용해 그룹을 나누기로 결정했다. 처음에는 최대 석유 개수를 기록하려고 했는데 아래 오른쪽 그림과 같은 상황에서는 원하는 답을 찾을 수 없기 때문에 그룹으로 나누었다.예를들면 6번 라인에서 굴착을 하면 [2, 1, 1, 12]만큼 오일을 얻을 수 있다는 것을 알기가 어려울 것 같았다. 2. 굴착을 했을 때 어떤 그룹들이 있는지를 저장했다. 아래 그림과 같은 경우에는 초록색 그룹이 3개나 발견됐는데 중복을 제거하는 코드가 필요하다. 3. 그 후 시추 1, 2, ~ 8까지 반복문..

문제 이해하기 숫자 0이 적힌 블록들에 다른 숫자가 적힌 블록들을 설치하려고 한다. 블록을 설치하는 규칙은 다음과 같습니다 블록에 적힌 번호가 n 일 때 가장 첫 블록은 n * 2번 째 도로의 위치에 설치, 그 다음은 n * 3, 4 ...도로의 위치에 설치합니다. 이 때 기존에 설치된 블럭이 존재한다면 해당 블록을 빼고 새로운 블록을 설치합니다. 각 블록은 오름차순으로 주어집니다. 또한 블럭의 숫자는 1 ~ 10,000,000까지의 숫자만 존재합니다. 문제 해결 방법 1. 도로의 입장에서 생각해보면 도로에 설치될 수 있는 블럭은 도로의 위치의 약수입니다. 예를 들면 10번 도로의 위치에는 1, 2, 5의 블록이 설치될 수 있다. 10의 블록이 설치될 수 없는 이유는 10(도로)은 10(블럭) * 1이기..

문제 이해 과제를 끝내는 순서대로 배열에 담아 반환하는 문제입니다. 여러 과제가 주어지는데, 가장 빨리 시작해야 하는 과제부터 선택하여 수행하고, 새로운 과제를 시작할 시간이 되면 기존에 진행 중이던 과제는 멈춥니다. 그리고 현재 수행 중인 과제가 다음 과제의 시작 시간보다 빠르게 끝나면 멈추었던 과제를 이어서 수행합니다. 멈추어 둔 과제를 실행하는 순서는 최신에 멈춘 과제부터 실행합니다. 문제 해결 방법 설명 1. 선택한 과제를 다음 과제를 시작하기 전까지 끝낼 수 있을까? 먼저 초로 단위를 통일했습니다. 해당 초를 정렬해줌으로써 수행하고 있는 과제와 다음에 수행해야하는 과제의 시간을 알아낼 수 있었습니다. 현재 과제의 시작 시간과 과제(A)를 끝내기까지 요구되는 시간(B)과 다음 시작 시간(C)을 알..

[문제 설명] A나라에서 발사한 미사일의 구간이 (s, e)로 주어지고, B나라는 최소한의 요격 미사일로 A가 날린 미사일을 요격해야 한다. B가 사용하는 최소한의 미사일을 개수를 찾는 문제다. [해결 방법] 저는 이 문제를 풀기위해 그리디 알고리즘을 사용했습니다. 그리디 알고리즘을 사용한 이유는 다음과 같습니다. 우리가 원하는 답은 최소한의 요격 미사일 개수 입니다. A가 날린 미사일의 위치를 모두 알 수 있으니, 우리는 미사일의 공통된 구간을 찾아서 요격 미사일을 날려주면 원하는 답을 찾을 수 있습니다. 코드 # Copyright 2023 bae # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use t..

문제 이해하기 판매원 A가 칫솔을 판매하면 판매한 금액의 10프로가 판매원 A의 상관인 B에게 분배되고, B의 상관인 C에게 분배되는 형태의 판매망을 운영하고 있습니다. 이 때 조직 내 누가 얼만큼의 이득을 가져갔는지 알고자하는 문제였습니다. 문제 해결 방법 설명하기 조직 내 누가 얼마만큼의 이득을 가져갔는지를 파악하기 위해서는 각 판매원이 판매한 금액을 추적해야 합니다. 예를 들어, 판매원 A가 100만원짜리 칫솔을 판매하면, A는 100만원의 10%인 10만원을 B에게, B는 10만원의 10%인 1만원을 C에게 주어야 합니다. 따라서 이 판매망에서 각 판매원이 얼마만큼의 이득을 가져가는지를 계산하려면, 각 판매원이 판매한 금액을 추적하고, 이를 기반으로 각 판매원이 상위 조직원에게 주는 이득을 계산하..

문제 이해하기 양의 정수 n을 k진수로 변환한 후, 다음의 네 가지 규칙에 맞는 소수를 찾는 문제입니다. 0P0 형태의 소수: 양쪽에 0이 있는 소수 P0 형태의 소수: 오른쪽에만 0이 있는 소수 0P 형태의 소수: 왼쪽에만 0이 있는 소수 P 형태의 소수: 양쪽에 0이 없는 소수 예를들면 437674이라는 십지수 정수를 3진수로 변환하면 "211020101011"이 됩니다. 이 숫자들 중에 규칙이 적용되는 숫자를 찾으면 2110(P0 조건) 011(0P 조건), 020(0P0 조건)이 있어 답이 3이 됩니다. 문제 해결 방법 설명하기 1. 10진수를 k진수로 변환할 수 있어야합니다. 10진수에서 n을 k 진수로 변환하는 방법은 아래와 같습니다. n을 k로 나눈 몫과 나머지를 구합니다. 해당 나머지를 가..

문제 이해하기 이진트리를 수로 표현하는 문제입니다. 이진트리의 노드를 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴보고, 더미 노드인 경우 문자열 뒤에 0을 추가하고, 더미 노드가 아닌 경우 문자열 뒤에 1을 추가합니다. 마지막으로 문자열에 저장된 이진수를 십진수로 변환합니다. 문제의 예시인 42를 설명해보자면, 42를 이진수로 변환하면 101010이 됩니다. 이는 완전이진포화트리가 아니기에 0101010으로 변환됩니다. 하위 리프노드에 더미노드가 추가 되야 했지만, 카카오 예시에선 생략되어 있는 모습입니다. 문제 해결 방법 설명하기 1. 이진수를 포화 이진트리로 만들 수 있어야 합니다. 주어진 정수를 이진수로 변환하여 포화 이진트리를 만드는 것이 요구되고, 이때 0을 삽입해야 합..

[문제 설명] 주어진 작업을 처리하기 위한 여러 개의 코어가 있는 CPU가 있습니다. 각 코어는 작업을 처리하는 시간이 다르고, 작업이 끝나면 작업이 없는 코어가 다음 작업을 수행합니다. 처리해야 할 작업의 개수와 각 코어의 처리 시간이 주어질 때, 마지막 작업을 처리하는 코어의 번호를 반환하는 함수를 작성해야 합니다. [해결 방법] 우선 이 문제를 풀기 위해선 모든 작업들이 코어에 할당되는 최소 시간을 찾아야 합니다. 이를 빠르게 찾기 위해 이분탐색을 사용했습니다. 구체적인 해결 방법은 아래와 같습니다. 이분 탐색을 통해 최소 시간을 구합니다. (최소 시간 - 1)을 하여 해당 시간에 코어가 처리하고 있는 작업의 수를 파악합니다. (코어 시간 % 최소시간 == 0)이면 해당 시간에 코어에 작업을 할당할..

[문제 설명] 출발지에서 목적지까지 최단거리로 이동하는 경우를 구하는 문제입니다. [해결 방법] 해당 문제는 BFS를 사용해 풀이하는 문제입니다. BFS를 이용한 빠른 길 찾기는 출발점으로부터 인접 노드들의 최단거리를 갱신하는 구조입니다. 이 때, 출발점이 하나이고 목적지는 x개일 수 있습니다. 주어진 예시를 보면 출발점은 x개인 반면에 도착점은 하나로 고정되어 있습니다. 즉, 도착점을 출발점으로 생각하여 인접 노드들의 최단거리 노드를 갱신하면 도착점에서부터 출발점까지의 최단거리를 구할 수 있습니다. 결과적으로 도착점을 출발점으로 탐색을 진행한다면 도착점에서 출발할 수 있는 모든 노드들의 최단거리를 구할 수 있습니다. sources 배열에 있는 노드들의 최단거리를 return하여 정답을 받을 수 있습니다..

[문제 설명] 인센티브를 받는 사람 중 완화가 몇 등인지 구하는 문제였다. 인센티브를 받을 수 있는 조건은 다음과 같다. 사원.근무태도 >= 사원들.근무태도 or 사원.동료평가 >= 사원들.동료평가 둘 중에 하나라도 높은 것이 있다면 인센티브를 받을 수 있다 [해결 방법] 주어진 예시(sources = [[x, y], [x,y]...])를 도식화 시키면 아래와 같은 모습이 나타나게 된다. 여기서 빨간색 부분은 인센티브를 받을 수 없는 사람들의 영역을 나타낸다. 아래의 사진을 보면 두 가지의 특징을 획득할 수 있다 x의 크기 순서 및 만약 x의 크기가 같으면 y 값이 작은 사람부터 인센티브의 여부를 우선적으로 판별할 수 있다. x가 0으로 가까워 질 수록 y 값이 커지는 특징을 확인할 수 있다. 왜냐하면 ..

아이디어 도출 방법 주어진 문제는 search배열(n)에서 특정 숫자(m)를 찾는 문제였다. 하지만 배열의 길이가 크고, 찾고자 하는 특정 숫자가 많아지면 이중반복문으로는 해결하기 어렵다. 따라서 이중 반복문을 제거하고, 주어진 배열에서 더 빠르게 탐색할 수 있는 알고리즘이 필요한데 이것이 이분 탐색이다. 이분 탐색은 기존의 O(n)의 시간 복잡도를 O(logn)으로 줄여준다. 이런 방법을 사용한다면 기존의 O(n*n)의 시간 복잡도에서 O(nlogn) + O(mlogn)으로 개선할 수 있다. 또한 이분 탐색을 하기 전 필수적으로 수행되어야 할 것은 '특정 배열'(주어진 숫자를 찾고자 하는 배열)이 정렬되어 있어야 한다. 최종 결과 n = int(input()) search = list(map(int, ..