2022년 회고를 지금 하는 게 조금 웃기긴 하지만...(?) 나름 알차게 살았던 2022년을 기록하고 싶었다. 나의 2022년은 SSAFY로 시작해서 SSAFY로 끝났다... 물론 중간중간 놀 거 다 놀긴 했다 ㅎㅎ 2022년 내가 어떤 SSAFY 생활을 했고, 어떻게 놀러 다녔는지(?) 포스팅해보려고 한다!! 1. SSAFY 7기 입학 및 스타트 캠프 SSAFY 7기로 입학하면서 웰컴 키트를 배송받았다! 다른 사람들은 못생긴 파란 후드티를 받았다고 했는데 나는 검정 후드티라서 잠깐 외출할 때도 잘 걸치고 다녔고, 2학기에 캠퍼스로 나갈 때 가지고 다니며 잘 입었다 ㅎㅎ 그리고 SSAFY를 처음 입학하게 되면 스타트 캠프 기간이 있다. 사람들과 해커톤도 하고 간단한(?) 팀플을 하면서 얘기하는 시간을 ..
문제 - 택배 화물이 각 집하장들 사이를 오갈 때, 어떤 경로를 거쳐야 하는지 정해야 함 - 이를 경로표로 정리해야 함 - 경로표에는 한 집하장에서 다른 집하장으로 최단 경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타냄 해결방법 다익스트라 알고리즘을 활용하여 문제를 해결하였다. 다익스트라 알고리즘에 대한 설명을 아래 포스팅을 확인하면 좋을 것 같다. [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 (Dijkstra Algorithm) 개념 - 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 - BFS와 DP를 활용한 최단경로 탐색 알고리즘 - DP를 활용 sa11k.tistory.com 다익스트라 기본..
문제 - n개의 도시, m개의 버스 - 버스는 한 도시에서 출발하여 다른 도시에 도착 - A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용과 경로 출력 해결방법 다익스트라 알고리즘을 활용하여 문제를 해결하였다. 다익스트라 알고리즘에 대한 설명은 아래 포스팅을 확인하면 좋을 것 같다. [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 (Dijkstra Algorithm) 개념 - 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 - BFS와 DP를 활용한 최단경로 탐색 알고리즘 - DP를 활용 sa11k.tistory.com 다익스트라 기본 코드를 활용하여 기본적인 문제 해결 틀을 잡았는데 이 문제에서는 경로도 함께 출력..
다익스트라 알고리즘 (Dijkstra Algorithm) 개념 - 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 - BFS와 DP를 활용한 최단경로 탐색 알고리즘 - DP를 활용하는 이유는 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 활용하기 때문 - 그래프의 간선마다 가중치가 존재할 때 사용 (음의 가중치는 존재하지 않음) 구현 - 최단 거리 테이블 MAX 값으로 초기화 (최단 거리를 저장해야 하므로 큰 수로 초기화 시킴) - 출발 노드 설정 - 방문하지 않은 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택 - 해당 노드를 거쳐 다른 노드로 이동하는 비용을 계산하여 최단 거리 테이블 갱신 - 계속해서 가중치가 가장 짧은 노드를 선..
문제 - 방향 그래프가 주어짐 - 시작점에서 다른 모든 정점으로의 최단 경로 구하기 - 다익스트라 기본 유형 해결방법 다익스트라 알고리즘을 사용하는 기본적인 유형으로 가중치가 있는 그래프에서 최단경로를 찾는 문제였다. 주어진 간선 정보를 저장하기 위해 각 정점에서 출발하는 간선에 대한 정보를 list에 저장하였고, 각 정점에 도착할 수 있는 최단 경로의 값을 result 배열에 저장하였다. 큐에 출발점부터 이어지는 정점들 중 최단거리로 이동할 수 있도록 넣어가면서 비교하여 최단거리를 구할 수 있도록 코드를 구성하였다. 다익스트라에 대한 자세한 설명은 아래 포스팅에서 확인할 수 있다. [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 (Dijkstra Algorith..
문제 - 사무실에 총 K개의 CCTV가 설치되어 있음 - CCTV는 5가지 종류 - CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있음 - 사무실에 벽이 있는데 CCTV는 벽을 통과할 수 없음 - CCTV가 감시할 수 없는 영역은 사각지대 - CCTV는 회전할 수 있는데, 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 함 - 0은 빈칸, 6은 벽, 1~5는 CCTV를 나타냄 - CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하기 해결방법 처음에는 그리디 방식으로 각 CCTV에서 감시할 수 있는 최대의 칸을 감시할 수 있도록 코드를 작성하였다. 하지만, 더 나은 방법으로 감시할 수 있는 방향이 있었다. 예를 들어 (0, 0)부터 CCTV에서..
문제 - 상근이네 집에서 맥주 한 박스 들고 출발 - 맥주 한 박스에는 맥주가 20개 들어있음 - 50미터에 한 병씩 마실 것임 (50미터 가기 직전에 맥주 한 병을 마셔야 함) - 가는 길에 맥주를 더 구매해야 할 수도 있음 - 편의점에 들렀을 때, 빈 병은 버리고 새 맥주 병을 살 수 있음 - 박스에 들어있는 맥주는 20병을 넘을 순 없음 - 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 함 - 상근이가 행복하게 목적지까지 도착할 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력 해결방법 맥주가 20병 있는데 1병 당 50미터를 이동할 수 있기 때문에 현재 좌표부터 다음 좌표(편의점 or 목적지)까지 1000미터 이내여야 이동이 가능하다. 따..
문제 - 상근이는 빈 공간과 벽으로 이루어진 건물에 갇힘 - 건물의 일부에 불이 났고, 상근이는 출구를 향해 뛰는 중 - 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나감 - 벽에는 불이 붙지 않음 - 상근이는 동서남북 인접한 칸으로 이동 가능. 1초 걸림 - 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 / 이제 불이 붙으려는 칸으로 이동할 수 없음 - 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있음 - 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하기 - '.' : 빈공간 / '#' : 벽 / '@' : 상근이의 시작 위치 / '*' : 불 - 탈출할 수 없는 경우에는 "IMPOSSIBLE" 출력 해결방법 탈출을 위한 escape 함수와 불..