BOJ - 2583 - 영역 구하기 문제 2583번: 영역 구하기 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 &l...

BOJ - 2468 - 안전 지대 문제 2468번: 안전 영역 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간...

BFS 너비 우선 탐색 개요 BFS 너비우선탐색 BFS는 그래프를 탐색하는 알고리즘으로 노드에서 시작해 이웃한 노드들을 우선적으로 탐색하는 알고리즘 이다. 같은 가중치를 가진 그래프에서 최단거리를 구할 때 사용되는 알고리즘이다. 시간 복잡도는 앞의 포스팅에서 소개한 DFS와 같으며 주어진 맵 전체를 탐색하며 한번 방문한 노드는 다시 방문하...

DFS 깊이 우선 탐색 개요 DFS, 깊이우선탐색 깊이 우선탐색은 그래프를 탐색할 때 쓰이는 알고리즘으로, 특정한 노드에서 가장 멀리 있는 노드를 우선적으로 탐색하는 알고리즘이다. 주어진 맵 전체를 탐색하며, 한번 방문한 노드는 재 방문하지 않기에 인접한 리스트로 이루어진 맵이면 O(V + E) 인접 행렬로 이루어진 맵이면 O(V^2)...

BOJ - 11478 - 서로 다른 부분 문자열의 개수 문제 11478번: 서로 다른 부분 문자열의 개수 문제 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b...

BOJ - 7785 - 회사에 있는 사람 문제 7785번: 회사에 있는 사람 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이...

BOJ - 1620 - 나는야 포켓몬 마스터 이다솜 문제 1620번: 나는야 포켓몬 마스터 이다솜 문제 포켓몬의 이름을 입력하면 해당 번호를, 번호를 입력하면 포켓몬의 이름을 출력하라. 입력 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,0...

BOJ - 1302 - 베스트셀러 문제 1302번: 베스트셀러 문제 김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다. 오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많...

BOJ - 2346 - 풍선 터뜨리기 문제 2346번: 풍선 터뜨리기 문제 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 ...

BOJ - 1072 - 게임 문제 1072번: 게임 문제 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는...