Numa 개발일지

그래프에서 최단거리를 구하기 위해 알아야 하는필수 알고리즘인 대망의 다익스트라(dijkstra) 알고리즘 학부 자료 구조 시간에 가중치가 있는 방향 그래프를 배우면서 다익스트라 알고리즘을 공부했었는데 까먹었던 내용들이 이번 공부를 통해 리마인드 할 겸 기록함. 다익스트라 알고리즘의 전제는 간선의 가중치가 양수여야 한다는 점이다. 그렇지 않으면 확장 알고리즘인 벨만-폴드 알고리즘을 사용해야 됨 기본적인 아이디어는 BFS에서 시작하며, 여기서 각 노드의 정보들을 저장할때는 MinHeap을 통해 구현하는 PriorityQueue를 사용한다. 이유는 시작점에서 다음 간선으로 이동하기 위한 최소 거리를우선적으로 탐색해야 그 루트가 최소 거리가 되기 때문 문제설계도시 N개와 버스 노선 M개가 주어진다.각 버스는 ..

해당 문제는 3차원 그래프 순회 + multi source 처리에 대한 문제이다.이전 실버 단계에서 풀었던 grid 형태의 그래프 순회에 3차원의 높이 축까지 확장한 형태이며 본질은 크게 다르지 않다. 처음 방문 노드 -> 다음 간선 이동 -> 중복 방문 방지 예외 처리 해당 3가지 틀을 의식하여 문제를 정의해 본다. 처음 방문 노드익은 토마토를 1, 안익은 토마토를 0, 토마토가 없는 위치를 -1로 설정하였을 때,처음 queue에 넣어야 할 요소들은 익은 토마토의 위치들이다.중요한 것은 익은 토마토들이 하루가 지날수록 동시에 단계씩 퍼져 나가기 때문에한번에 input으로 넣어 처리 해 주어야 한다. 이를 multi source(여러개의 출발점)에 관련된 문제라고 하는 것 같다.multi source..

dp로 인식하여 자력 솔브한 문제이기에 기록함 해당 문제에 대해서 dp로 생각한 이유는 이전 상태에 따라서 최대값이 달라지기 때문에 현재 선택한 와인의 순번에 대하여이전 상태에서 최대로 마실 수 있는 양과 적절한 계산을 통해계산할 수 있을 것이라는 생각을 하게 됨 문제에서 와인을 세번 연속 마실 수 없게 되어 있으므로 이에 대한 적절한 조치가 달라질 것을 염두하였다. 문제설계현재 순번의 선택 결과가 이전 선택 상태에 따라 달라지므로 DP 문제로 판단.특히 3연속 불가 제약 때문에 이전 상태를 나누어 관리해야 한다고 생각함. 생각한 문제 패턴이전 상태 기반 최대값 갱신 DP.현재 와인을 마시는 경우 ,마시지 않는 경우를 나누고, 연속 선택 조건을 함께 고려 첫 접근했을 때 생각현재 선택 와인 + ..

PS에서 트리의 자료 구조 저장 방법과 자료구조의 순회 방법에 대한 문제 포인터 기반으로 하여 트리 자료구조를 구현했던 기억이 나는데 PS에서는 동적 할당이비싸므로 배열을 통한 구현을 전제로 한다. 트리 순회에는전위 탐색중위 탐색후위 탐색이 있으며 각각 ROOT를 기준으로 어느 순서에서 탐색할지를 기준으로 이름을 명명한다. 전위탐색은 맨 앞에 ROOT를 탐색하고 다음 왼쪽 오른쪽,중위 탐색은 왼쪽 다음 중간에 ROOT를 탐색, 그리고 오른쪽후위 탐색은 왼쪽 오른쪽 자식노드를 먼저 탐색하고 마지막으로 ROOT 자료를 저장하는데 있어서는 해당 문제에서는 이진 트리이므로 각 원소에 대해 pair를 통해 자료를 저장하도록 한다. 탐색 시에는 stack를 쌓는 순서와 출력 순서를 traversal 순서에 고려..

1. 문제 해석1. N개의 집이 있음 2. 집에 RGB 색상을 칠할 수 있음 3. 칠하는 색상마다 비용이 존재, 집마다 칠하는 비용은 제각각 다르다.4. 이웃하는 집에는 서로 같은 색깔을 칠할 수 없다. 즉, R G B 조합 혹은R G R 조합과 같은 형태5.집의 수는 2개이상 1000개 이하 / 집을 칠하는 비용은 1000보다 작은 자연수 2. 처음 들었던 생각문제를 접근했을때a. 브루트 포스경우의 수는 3x2x2....이고 이것을 브루트 포스로 전체 다 순회한다면 지수 복잡도 -> 말이 안됨 b. 그리디처음에 가장 작은 선택지를 사용한다.하지만 다음과 같은 경우에 대처할 수 없음첫번째 집에서 1, 100, 100일때 당연히 1을 선택하는게 현명해 보이지만두번째 집에서 1, 1000, 1000이면 첫..

문제를 풀때 코드를 입력하기 전 알고리즘을 먼저 설계해야 한다는 후임의 말을 듣고 피드백을 반영하여 먼저 생각하는 연습을 진행하였다. 조건1.각 입력들이 무엇을 의미하는지에 대해서 먼저 생각하기 n, m, list2. 문제 조건에서 비내림차순 형태( 사전순으로 증가) 3. 같은 수를 여러번 골라도 된다 4. 중복되는 수열을 여러번 출력하면 안된다 해당 문제에 대하여 전체적으로 처음에 설계한 부분은 다음과 같다. 알고리즘 설계 1. 입력2. list에 대해서 오름차순 정렬3. dfs에 들어가야할 인자 먼저 생각(정렬된 리스트, 탐색하면서 값이 집어넣어질 빈 컨테이너, 시작index, 리스트 개수 n , 출력 개수 m )4. dfs를 사용하는 이유는 M의 수열을 한 칸씩(단계별) 선택하며 만들어 가야 하므..

해당 문제는 solved.ac 티어 골드 5관문을 입장하게 한 문제로 기념비적으로 정리해 본다.문제이름boj 11403 경로 찾기 문제 설계방향 그래프i에서 j로 갈 수 있는 경로 존재 여부 출력최단거리 X단순 도달 가능성 문제생각한 문제 패턴(i, j) 쌍에 대해 BFS를 개별적으로 돌려야 한다고 생각2차원 visited로 관리하려고 함(start, end)를 큐에 pair로 넣는 방식으로 전이 폐쇄 구현 시도visited를 전역으로 유지해야 하나 고민-> 한 쌍씩 확인해야 한다는 사고로 접근 알고리즘 1 (초기 잘못된 접근)bfs(adj, visited, start, end)(start, end) 쌍을 상태로 관리visited를 2차원으로 두고 전이 확장문제점BFS가 불필요하게 복잡해짐adj 대신 v..

자력으로 풀어서 두번째로 잘 풀고 성장했다는 느낌을 받은 문제에 대해서 정리해 본다. DFS, BFS 개념에 대해서 1,2주 전만 해도 명확하게 잡히지 않고 구현할때 헤매는 느낌이 있었는데 오늘 문제를 풀면서어느정도 감을 잡은것 같은 느낌을 받았기에 정리함. 문제번호21736 - 헌내기는 친구가 필요해 문제 설계1. 시작점 I에서 출발하여야 하므로 I에 대한 정보를 x,y변수에 처음 저장 (시작점 정보) 2. 격자 탐색 + 연결된 영역을 순회해 X ( dx, dy로 관리하여 다음번 순회 처리)(벽)을 제외한 모든 영역을 탐색하며 P의 개수를 카운트 3. 방문 관리를 visited 변수를 따로 두어 classic 하게 해결함 (방문 처리)BFS/DFS 중 하나로 전체 도달 가능한 영역을 탐색 생각한 문제 ..

문제설계 2D 격자에서 배추 위치가 주어지고,상하좌우로 연결된 배추 묶음마다 지렁이 1마리가 필요하다.결국 서로 연결된 배추 그룹의 개수를 세는 문제. 생각한 문제 패턴 격자에서 상하좌우 연결을 보는 순간 그래프 탐색 문제라고 판단은 함.연결 요소 개수 세기 유형으로 DFS/BFS를 사용해야 하는 문제.근데 DFS BFS에 대해서 로직에 대해 확장성 등이 익숙하지 않아서 어떻게 설계해야 할지 막힘 첫 접근했을 때 생각 방문 여부를 어떻게 처리해야 하는지가 가장 먼저 고민됨. visited 배열을 써야 하나, 값을 바꿔야 하나 헷갈렸고, DFS/BFS 중 무엇을 써야 하는지도 명확하지 않았음. DFS BFS에 대한 로직 자체의 변형 등의 확장성에 익숙하지 않음 내가 생각한 알고리즘 설명배추를 발견하면 ..

풀이 없이 바로 솔브하여 사고 방식이 처음 PS를 본격적으로 시작한 1월 8일보다 그래도 성장했음을 느꼈던 문제이다. 문제번호BOJ1003 - 피보나치 함수 문제설계단순 피보나치 구현이 아니라재귀의 중복 호출 -> 시간초과 -> DP 전환을 유도하는 문제DP : dynamic programming 생각한 문제 패턴피보나치 수 n이 40 이하로 작음 재귀 함수 처리시, subroutine 많이 생성되므로 그만큼 동작 시간에 TLE 가능성 염두점화식 존재 + 중복 계산 발생 → 1차원 DP 패턴 내가 생각한 알고리즘 0과 1 호출 횟수를 각각 저장하는 DP 테이블 생성. → pair로 생성(추천은 struct 방식도 있었음)fibo[i] = fibo[i-1] + fibo[i-2] 점으로 0~40까지 미리 ..