L.O.K

16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net ◎문제풀이 타이틀을 완성하도록 전공책을 선택할 때 가장 적은 비용을 고르는 문제이다. 나는 DFS 풀이를 발상하기는 했지만 완전탐색을 어떤 방식으로 할지 구현하지 못했다. 그러나 굉장히 단순한 풀이였다. 오히려 너무 단순해서 풀이방식을 떠올리지 못한 것 같다. 전공책을 선택할 수 있고 전공책을 선택 안 할 수도 있다. 선택하는 경우와 안 하는 경우로 DFS 탐색하며, 타이틀을 완성 여부를 체크하고 비용의 최소값을 구하면 된다. ◎ 코드 import java.io.*;..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 상자 안에는 다음 오픈할 상자의 번호가 적혀있는 카드가 들어있다. 임의의 한 상자를 오픈하여 연달아 오픈해서 이미 오픈한 상자를 만날 때까지 오픈한다고 했을 때, 연달아 오픈할 수 있는 상자의 개수가 가장 많은 것과 그 다음 많은 것의 곱을 구하는 문제이다. 문제가 복잡해보이지만 싸이클을 찾는 문제이다. 방향그래프에서 싸이클을 찾는 문제는 DFS 알고리즘을 사용하면 된다. DFS 알고리즘으로 가장 큰 싸이클과 그 다음 싸이클을 찾아서 싸이클 안의 상자수를 곱하면 된다. 주의할 점은 입력으로 주어진..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ◎ 문제풀이 문제요약 : 학생들이 원하는 팀원 정보가 그래프로 주어질 때, 싸이클을 형성하면 팀으로 구성된다. 싸이클을 형성하지 못하는 팀원의 수를 구하라. 문제풀이 : - 방향그래프에서 싸이클을 찾는 문제이므로 DFS를 발상하였다.( 무방향 그래프에서 싸이클을 찾는 문제는 UNION-FIND 알고리즘 사용 ) - 방문여부 배열과 싸이클 여부 배열로 DFS 로직을 구성하였다. - 탐색과정에서 이미 방문한 노드를 다시 접근하면 싸이클이 형성된다. - 싸이클 여부가 결정..

16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ◎ 문제풀이 문제 이해력과 구현력이 필요한 문제였다. 접근이 가능한 인접지역을 탐색하는 문제이므로 DFS와 BFS가 떠올랐다. DFS는 깊이우선탐색으로 깊이를 먼저 파다보면 접근하지 않아도 되는 경우의 수도 접근할 수 있다. DFS와 BFS 결국 모두 동일한 지역을 접근하므로 접근가능한 경우의 수를 줄이기 위해 BFS로 탐색한다. 그럼 며칠을 인구이동해야 인구이동이 필요없는지 구해보자. 인구차이가 20(L)보다 크거나 같고 90(R)보다 작거나 같아..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net ◎ 문제풀이 A지점에서 B지점으로 최소비용으로 이동하는 문제는 BFS로 풀어야 한다. 그러나 나는 최근에 DP 문제를 하나 풀어서 그런지, 이 문제를 보고 DP 발상을 했다. N에서 K까지 가는 경우를 모든 고려하는 문제이다. 이동하는 방법은 3가지이다. 1) x2 2) +1 3) -1 N이 5이고 K가 17이라고 가정해보자. 위 그림 같이, 경우의 수가 기하급수적으로 증가하니 DP로 풀기는 어려운 문제이다. 1) x2 2) ..

18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net ◎ 문제풀이 나이트를 이동시켜 체스말을 잡을 때, 나이트의 최소 이동수를 구하는 문제이다. 그래프의 좌표가 주어지고 이동비용이 동일할 때 최소이동수를 구하는 문제이니, BFS 풀이이다. 이 문제를 풀며, 시간초과가 발생했을 때 시간복잡도를 계산해서 문제를 다시 리빌딩하는 능력이 부족함을 깨달았다. 처음에는 잡아야하는 체스말이 3개 주어지면 DFS 탐색도 3번하는 방식으로 풀었다. 그랬더니 시간초과가 발생했다. 시간복잡도를 계산..

18511번: 큰 수 구성하기 첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 www.acmicpc.net ◎ 문제풀이 개인적으로 DFS의 새로운 활용을 본 문제였다. 정수 N과 k개의 9보다 작거나 같은 자연수가 주어졌을 때, k개로 만든 정수 중 N보다 작지만 최대인 정수를 구하는 문제이다. k개의 자연수의 조합으로 만들어진 경우의 수 중 최대인 정수를 구하는 문제이니, 이것도 '탐색' 문제이다. k가 최대 3이고 N은 1억보다 작거나 같으니 최대 8자리 수이다. 그러므로 나올 수 있는 경우의 수는 3⁸, 6561가지이다. 시간제한..

https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net ◎ 문제풀이 그래프에서 싸이클을 찾고 싸이클과 노드 사이의 거리를 구하는 문제이다. 풀이과정은 3가지 STEP으로 진행된다. STEP1) 그래프를 인접리스트로 구현 STEP2) 싸이클 DFS 알고리즘으로 탐색하기 STEP3) 싸이클과 노드사이의 거리를 DFS로 구하기 - 싸이클 DFS 알고리즘으로 탐색하기 싸이클은 DFS, BFS로 탐색이 가능하다. 문제에서 싸이클은 1..

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net ◎ 문제풀이 행렬그래프가 주어지고 싸이클을 찾는 문제이다. 이는 DFS로 접근하면 된다. ◎ 코드 package org.example.dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; //BOJ16929 Two Dots public class Dfs1 { static in..

7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ◎ 문제해결 이동시 비용이 동일하고 목표까지 최단거리를 구하는 문제이니 BFS 알고리즘으로 풀어야 하는 문제이다. ◎ 코드 package org.example.bfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Stri..