본문 바로가기

그래프4

[백준 2573번] 빙산 난이도: 골드 IV 문제 링크: https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 이번 문제부터 문제화면 캡쳐는 생략하겠습니다. 오늘도 풀 만한 문제가 없나~ 하고 보다가 고른 탐색 겸 구현 문제입니다. 구현 문제라서 코드의 길이가 길어지고 잔실수를 조심해야 하지만... 제가 접근한 방법입니다. 시작에 앞서, 빙산이 두 개 이상인지 판별하는 함수, 빙산을 1년어치만큼 녹이는 함수를 작성합니다. 빙산이 두 개 이상인지 판별하는 함수의 경우, .. 2022. 1. 3.
[프로그래머스] 방의 개수 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/49190 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr ※주의: 제 코드는 문제를 풀기는 했지만 굉장히 깔끔하지 못한 코드입니다. 더 좋은 풀이가 많으니 다른 풀이도 참고해 보세요! 좌표평면에서 시작점을 (0, 0)으로 하고, 0~7에 지정된 이동 방향을 따라 선을 쭉 그린 후, 완성된 방의 개수를 세는 문제입니다. 여기서 방이란, 사방이 선으로 막혀 있는 상태를 방 하나로 센다고 합니다. 맨 처음 제가 생각해낸 아이디어는 다음과 같습니다. "이미 방문했던 좌표에 다시 방문하는 .. 2021. 10. 3.
그래프 이론 그래프 자료구조는 코딩 테스트에서 난이도가 제법 있으면서도 어려운 부분입니다. 앞서 살펴본 DFS/BFS, 최단 경로 모두 그래프 자료구조를 활용합니다. 이 외에도 다양한 그래프 자료구조를 이용한 문제들과 알고리즘이 있으며, 이들 역시 코딩 테스트에 종종 등장하므로, 반드시 알아 두어야 합니다. 이런 알고리즘은 또한 앞에서 소개한 개념에 포함되기도 합니다. 아래 소개할 크루스칼 알고리즘의 경우 그리디 알고리즘에 포함되며, 위상 정렬의 경우 큐/스택 자료구조를 잘 알고 있어야 이해할 수 있습니다. 더불어, 트리 (tree) 자료구조는 그래프 자료구조를 이용하는 다양한 알고리즘에서 사용되므로, 잘 알아 두어야 합니다. 앞서 최단 거리를 살펴볼 때 등장했던 우선순위 큐의 경우, 최대/최소 힙을 이용하는데, 힙.. 2021. 2. 12.
[백준 16236번] 아기 상어 이 문제는 삼성 SW 역량 테스트 기출문제 입니다. 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS를 이용한 탐색을 핵심으로 하는 문제입니다. BFS에 대한 이론적 배경은 여기를 참고하세요. BFS를 실제로 이용하여 문제를 푸는 접근법이 아직 생소하여, 인터넷 검색을 많이 활용했습니다. 문제가 내용이 긴데, 요약하면 아래와 같습니다. 상어는 본인보다 작은 물고기만 잡아먹을 수 있다. 상어는 빈 공간 혹은 자기보다 .. 2020. 11. 23.

티스토리툴바