Coding Test(125)
-
[BOJ] 17472번 | 다리 만들기 2 (C++)
🔗문제 보러가기 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 👨💻풀이 과정 BFS + DFS + 최소 신장 트리(MST) 알고리즘을 구현해야 풀 수 있는, 대단히 체력적으로 힘든 문제였습니다. 그래도 문제에서 주어진 조건들이 까다롭진 않아, 구현만 제대로 한다면 통과는 쉽게 되네요. 제가 푼 과정은 다음과 같습니다. 주어진 입력을 2차원 배열에 저장하되, 땅(1)은 1이 아니라 엄청 큰 다른 숫자(1억)로 대신 채워줍니다. BFS 알고리즘을 통해, 각 섬의 번호를 해당 섬의 영역에 채..
2023.12.12 -
[BOJ] 13549번 | 숨바꼭질 3 (C++)
🔗문제 보러가기 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🧑💻 풀이 과정 최단 경로 알고리즘을 연습 중에 있어, 저는 다익스트라 알고리즘으로 풀었습니다. (비용에 음수가 없기 때문) 시작 위치는 N, 도착 위치는 K로 주어집니다. N에서 i번째 노드로 가는 데에 드는 최소 시간을 저장하는 배열, times를 선언합니다. 범위가 0 ~ 100,000이니, 이 범위를 포함할 수 있는 만큼의 크기로 선언 후, 무한대 값으로 초기화합니다. times[N] = 0 으로 초기..
2023.12.06 -
[BOJ] 16928번 | 뱀과 사다리 게임 (C++)
🔗문제 보러가기 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 🧑💻풀이 과정 BFS로 쉽게 풀 수 있는 문제인데, 저는 사다리나 뱀을 타고 간 보드칸을 방문 처리해주질 않아, 엉뚱한 답이 나왔습니다. 이걸 빨리 알아채지 못해서 시간을 좀 허비했네요. 아무튼, 제가 푼 풀이 과정은 다음과 같습니다. 뱀이나 사다리 정보를 가지고 있는 vector teleports(100 + 1)을 준비한다. teleports[i] = 0 👉🏻 뱀이나 사다리가 없음을 의미 telep..
2023.12.01 -
[Programmers] Lv3. [1차] 셔틀버스 | C++
🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨💻풀이 과정 제 문장 독해력에 하자가 있는건진 몰라도, 처음에 문제 읽고 무슨 소리지 했었습니다. 핵심은 셔틀 버스 운행 횟수인 \(n\) 번 내에 사무실에 갈 수 있는 가장 늦은 시간을 고르는 것이었네요. 단순 구현 문제이긴 한데, 시간과 관련된 문제는 항상 계산 부분에서 주의를 기울여야 하는 것 같습니다. 일단은 계산하기 쉽게, string을 int로 변환하는 작업을 먼저 해보죠. 1. String 👉🏻 Int로 변환하는 함수 작성 주어지는 시간은 "HH:MM" 형태를 띄고 있다고 문제..
2023.11.18 -
[Programmers] Lv3. 섬 연결하기 | C++
🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑💻풀이 과정 🔗최소 신장 트리(MST, Minimum Spanning Tree)를 활용하는 문제입니다. 최소 신장 트리를 구축하는 과정에서 크루스칼(Kruskal) 또는 프림(Prim)의 알고리즘이 사용되며, 저는 크루스칼(Kruskal)의 알고리즘을 사용하여 풀었습니다. 신장 트리의 조건 중 하나로 사이클이 있으면 안된다가 있는데, 분리 집합(Disjoint set)의 개념인 🔗유니온 파인드(Union Find)라 불리는 자료구조로 쉽게 점검할 수 있습니다. 이번 기회에 공부하여 개념을 ..
2023.10.22 -
[Programmers] Lv3. 가장 먼 노드 | C++
🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑💻 풀이 과정 처음엔 다익스트라(Dijkstra) 알고리즘을 먼저 떠올렸는데, BFS로도 간단하게 풀 수 있겠단 생각이 들어 BFS로 풀었습니다. 알고리즘은 다음과 같습니다. 행 번호는 노드의 번호, 열 번호는 행 번호 노드와 연결된 다른 노드들의 번호로 이루어진 2차원 배열을 선언한다. 1번 노드를 방문 처리 후 Queue에 넣고, BFS 탐색을 시작한다. Queue에서 노드(source)를 꺼낸 후, 해당 노드와 연결된 다른 노드들을 방문 처리 후 Queue에 넣는다. 이 때, sour..
2023.10.22