DevLog: 기록하는 생활

플로이드-워셜 알고리즘이란?모든 정점 쌍 간의 최단 거리를 구하는 알고리즘입니다.다익스트라는 한 정점에서 출발하는 최단거리만 구하지만, 플로이드-워셜은 모든 정점에서 모든 정점까지의 최단거리를 구합니다. 플로이드-워셜 과정i: 출발지, j: 도착지 라고 하자.i에서 j로 가는 최단 거리는, i → j와 i → k(경유지) → j 중 더 작은 값을 선택해 갱신합니다.(경유지가 0번인 경우, 1번인 경우 ...n-1번인 경우) 코드와 시간복잡도O(n^3)for문이 3개가 중첩이 되어 있기 때문에, 시간 복잡도가 굉장히 높습니다.public class Main { static final int INF = 99999999; // 이동 불가 (문제에 따라 다르게 설정) public static void main..

다익스트라 알고리즘이란?그래프에서 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다.음의 가중치가 없는 그래프에만 사용 가능합니다. 다익스트라 과정1) 시작 노드의 거리를 0, 나머지는 무한대로 설정합니다. ex) k가 출발점이면, dist[k]=0 2) 방문하지 않은 정점 중, 출발지로부터 가장 거리가 짧은 정점을 방문합니다. 3) 해당 정점을 거쳐 연결된 다른 정점의 거리가 기존의 기록된 거리보다 작으면 갱신합니다. - 이 부분에서 음수 간선일 경우, 갱신이 반복되어 잘못된 최단 경로가 저장될 수 있어 오류가 생길 수 있습니다. 4) 모든 노드를 방문할 때까지 2-3단계를 반복합니다. 코드와 시간복잡도- 우선순위큐+ 인접리스트를 사용할 경우: O(E log V)인접리스트를 ..

문제 요약이 문제는 하노이탑 변형문제이다.기존의 하노이탑은 3번 막대기에 하노이탑을 쌓으면 된다.하지만 이 문제에선, 각 막대기에 디스크가 크기순대로 놓여져있는 상황에서 원하는 막대기에 최소비용으로 1-n 번 디스크를 놓으면 된다. 입력: n: 디스크 개수 (1 ≤ n ≤ 100,000) a, b, c: 차례로 1, 2, 3번 막대기에 꽂혀 있는 디스크의 개수 (0 ≤ a,b,c ≤ n ) 3줄에 걸쳐서, 각 막대기에 꽂혀있는 디스크들의 번호가 주어진다. 출력: 첫째 줄에 모아야 하는 막대기의 번호(1, 2, 3 중 하나)을 return한다. 최소의 이동 횟수를 1,000,000으로 나눈 나머지를 return한다 접근 방식n=4 라고..

문제 요약NxM 지도는 땅과 바다로 이루어져 있다. 이때 땅은 섬으로, 이 섬들을 다리로 연결해야한다. 다리는 최소 길이(격자에서 차지하는 칸의 수) 가 2여야하며, 바다에만 건설이 가능하다.다리의 양 끝은 섬과 인접한 바다에 있어야한다.아래 그림에서 B는 다리가 맞지만 A는 올바른 다리가 아니다.방향은 중간에 꺾일수가 없다. 즉 가로 다리와 세로 다리만 존재한다.다리는 교차로 설치가 가능하다.  입력:첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 1 ≤ N, M ≤ 103 ≤ N×M ≤ 100둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.2 ≤ 섬의 개수 ≤ 6출력:다리 길이의 최솟값을 re..

문제 요약모기 입퇴장 시간을 기반으로 가장 많은 모기가 있는 연속 구간 추출입력:방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE 출력: 첫째 줄에 지동이 방에 모기가 가장 많이 있는 시간대의 모기 마릿수를 return한다.둘째 줄에 지동이 방에 모기가 가장 많이 있는 시간대의 연속 구간 전체를 출력하되, 여러 가지 방법이 있으면 가장 빠른 시작 시각을 기준으로 출력 접근 방식처음에는 1차원 배열의 누적합이니까 아 엄청 쉽네 라고 생각했다 입장시간 +1 퇴장시간 에 -1을 한뒤 처음부터 쭉 누적합을 해서 계산할 생각이었으나, 퇴장 시간의 최댓값이 21억인 것을 보고 메모리초과가 나겠다고 생각했다. ..

2022 KAKAO BLIND RECRUITMENT 문제자체는 굉장히 단순해 이해하기 쉽다. 헷갈리는 부분은 파괴된 건물이 다시 회복을 할 수 있다 정도이다. 문제 요약NxM Map에 건물이 각 칸마다 존재, 내구도 0이하 시 파괴 skill의 Type 에 따라 (r1,c1) - (r2,c2) 직사각형 범위에 degree 만큼 공격 혹은 회복  입력:건물 내구도 2차원 정수 배열 board(n,m 출력:최종적으로 파괴되지 않은 건물 개수를 return한다접근 방식m,n 이 각 100 이하 skill 행 개수가  250000 이하이므로 최악의 시간복잡도를 따져보면100*100*250000 이면 25억이되면서 시간초과가 발생할 수 있다.이때 매번 직사각형 범위에 degree만큼 값을 빼주고 더해주는 것이 굉..

2024 KAKAO WINTER INTERNSHIP 문제 요약 생성된 정점으로 부터 세가지 유형의 그래프가 만들어진다.예제를 보며 이해해보자. 2로 부터 1 도넛모양그래프와 3 막대모양그래프가 만들어졌다.    4를 기준으로 맨 왼쪽의 크기가 3인 도넛모양그래프 1개와 위쪽의 크기가 1인 막대모양 그래프(정점 2) , 오른쪽의 크기가 3인 8자모양 그래프 1개가 만들어진 것을 볼 수 있다.  즉 생성된 정점에서 뻗어나간 간선 개수가 그래프 개수가 된다. 이제 세가지 그래프 유형에 대해 파악해보자. 1. 도넛 모양 그래프 (크기 n) : n개의 정점, 간선순환이 특징순환인지 보면 좋은데, 판단 과정이 다른 그래프에 비해 복잡하게 느껴진다. 2. 막대 모양 그래프 (크기 n): n개의 정점, n-1개의 간선..

기술 블로그를 쓰게 된다면, 꼭 올리면 좋겠다고 생각한 약 1년전 n-queen풀이이다 ! 이유는, 그 때 일차원 백트래킹에 대한 숙지가 부족해서 직관적인 방법으로 접근을 하였는데 지금 봐도 이 풀이는 이해가 쉽고 깔끔하고, 시간도 양호하다는 점에서 꽤 잘 푼 풀이라고 생각하여 올리게 되었다.문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. *퀸은 상하좌우, 대각선으로 이동이 가능하다 풀이방법백트래킹함수인 nqueen에서 cnt는 현재 배치된 퀸의 수를 나타내며, 즉 행을 의미한다. 왜냐하면 퀸은 좌우 이동이 되므로, 행 안에서는 1개의 퀸밖에 놓지 못한다는 것을 이용해서 배치된..

2021 카카오 채용연계형 인턴십 문제 요약5개의 5x5 대기실에서 응시자들이 코로나19 방역 수칙에 맞게 거리두기를 준수했는지 확인하여, 각 대기실에 대해 거리두기가 지켜졌으면 1, 그렇지 않으면 0을 반환. 규칙:응시자(P) 간 맨해튼 거리가 2 이하가 되면 안 됩니다.단, 예외:P 사이에 파티션(X)이 있다면 거리두기를 지킨 것으로 간주.빈 테이블(O)이 있더라도 P가 맨해튼 거리 2 이하로 배치된 경우는 거리두기 미준수.입력:places: 5개의 대기실을 나타내는 2차원 문자열 배열 (각 대기실은 5x5 크기).출력:거리두기가 지켜졌다면 1, 한 명이라도 지키지 않았다면 0을 1차원 배열로 반환.예: [1, 0, 1, 1, 1]제약사항:각 대기실의 크기는 항상 5x5.각 자리에는 다음 중 하나가 ..

문제 요약모든 행성을 탐사하는 최소 시간 계산입력:행성의 개수 N과 발사되는 행성의 위치 k가 주어진다. N개의 줄에 각 행성 간 이동시간이 주어진다. (출력: 모든 행성을 탐사하기 위한 최소 시간 접근 방식 문제를 처음 보고 , 다익스트라인 줄 알았으나 이미 방문한 행성도 중복해서 갈 수 도 있다 라는 포인트와  N 이 10개 미만이라는 점에서 플로이셜-워셜 알고리즘이 떠올랐다.플로이셜-워셜 알고리즘으로 각 출발점으로부터 행성에 방문할 수 있는 최소 거리를 계산하고, 그리고 나서 이 문제는 출발점(k)가 있으므로 다익스트라로 접근하여 마무리 지었다 !  여기서 문제의 접근 논리는 맞은 것 같았는데, 틀렸습니다 ! 가 떠서 당황스러웠다. 여기서 간과한점이 바로 있었는데,  boolean[] 배열을 Pla..