취업을 준비하며 정리하는 컴퓨터 지식/Problem Solving (33) 썸네일형 리스트형 [ProblemSolving] 백준 10026번 적록색약 문제풀이 백준 10026번 적록색약 문제풀이입니다. 문제 해설은 링크를 확인하면 된다. 문제 해설 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 해당 문제는 그래프 탐색 유형의 문제로 'G'를 'R'로 보는 적록색약인 사람이 보는 구역의 수와 적록색약이 아닌 사람이 보는 구역의 수를 구해야 한다. 해당 문제를 해결하기 위해서는 다음의 과정을 수행해야 한다. colorData는 입력받은 색 정보이다. colorData에서 BFS를 수행한다. 수행하면서 연산의 끝에 'G'를 'R'로 바꿔준다. 모든 'G'가 'R'.. [ProblemSolving] 백준 1744번 수 묶기 문제풀이 백준 1744번 수 묶기 문제풀이에 대해서 알아보겠다. 문제 해설은 다음의 링크를 확인하면 된다. 문제 해설 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 해당 문제는 그리드 유형의 문제로 최적을 방법을 고민해야 한다. 해당 문제를 해결하기 위해서는 3가지 조건을 충족하면서 계산을 해야 한다. 2 이상의 숫자는 오름차순 정렬하여 곱한다. 1은 더한다. 음수는 내림차순 정렬하여 곱한다. 위의 조건을 만족하기 위해서는 숫자를 입력받을 때 양의 정수, 1, 음의 정수를 따로 처리해줘야 한다. 다음의 조건을 만족.. [ProblemSolving] 백준 7576번 토마토 문제풀이 아직 많은 문제를 접해보지는 않았지만 BFS, DFS 탐색을 사용하는 문제들이 재미있다. 그래서 오늘도 그래프 탐색을 사용한 '토마토' 문제를 가져왔다. 문제 해설은 링크를 확인해주기 바랍니다. 백준 7576번 토마토 문제 해설 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 해당 문제는 익은 토마토가 위치한 부분 전부를 큐에 우선 넣어준 후에 BFS 탐색을 실행시키는 방식으로 해결이 가능하다. 과정은 다음과 같다. 토마토의 정보를 가지고 있는 배열은 data라고 하겠다. data에서 익은 토.. [Problem Solving] 백준 1916번 최소비용 구하기 문제풀이 백준 1916번 최소비용 구하기 문제 해설 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 모든 도시의 이동 비용이 양의 정수이고, 시작 지점에 대한 정보도 있으므로 해당 문제는 다익스트라 알고리즘을 활용하여 해결하면 된다. 다익스트라 알고리즘에 대한 설명은 다음을 참조하면 된다. 다익스트라 알고리즘 개념, 다익스트라 알고리즘 실습 다익스트라 알고리즘을 활용하여 코드를 작성하면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19.. [Problem Solving] 백준 1092번 배 문제풀이 백준 1092번 그리디 문제에 대한 풀이를 알아보겠습니다. 문제 해설은 링크를 연결해두었으니 확인하시기 바랍니다. 백준 1092번 배 문제 해설 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 물건을 옮기는데 최적의 방법은 가장 무거운 것을 들 수 있는 크레인이 가장 무거운 박스를 옮기는 것이다. 방법은 다음과 같다. 각 크레인과 박스를 무게에 맞게 내림차순 정렬시켜준다. 크레인이 들 수 있는 가장 무거운 박스를 옮긴다. 모든 크레인에 대해서 해결했다면 시간을 1 올려준다. 2의 과정을 반복한.. [ProblemSolving] 백준 2589번 보물섬 문제풀이 백준 2589번 BFS 문제에 대한 풀이를 알아보겠습니다. 문제 해설은 링크를 연결해두었으니 확인하시면 됩니다. 백준 2589번 보물섬 문제 해설 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 보물이 있는 위치는 서로 간에 최단 거리로 이동했을 때 가장 이동 시간이 긴 육지 2곳에 있습니다. 가장 긴 이동 시간을 가진 육지를 찾는 방법은 각각의 육지에서 다른 육지로의 거리들을 비교하여 최댓값을 저장하는 방식을 활용하면 될 것입니다. 따라서 해당 문제는 브루트 포스와 너비 우선 탐색을 이용하여 해결할 수 있습니다.. [ProblemSolving] 백준 2667번, 프로그래머스 64061번 문제풀이 백준 2667번 DFS 문제와 프로그래머스 64061번 구현 문제에 대한 풀이를 작성하겠다. 각각의 문제 해설은 링크를 연결해두었으니 확인하면 된다. 백준 2667번 단지번호붙이기 (DFS) 문제 해설 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 단지의 수를 세어야 하기 때문에 깊이 우선 탐색을 사용하여 구현하면 된다. 깊이 우선 탐색의 과정은 다음과 같다. 아파트가 있고, 아직 방문하지 않은 곳을 탐색한다. 방문 처리를 하고, 아파트의 수를 세어준다. 왼쪽, 오른쪽, 위, 아래의 방향으로 가상으로 이동한다.. [ProblemSolving] 프로그래머스 60057번 문자열 압축 문제풀이 모든 경우의 수를 탐색하여 정답을 도출하는 완전 탐색 유형의 문제이다. 다음은 문제를 풀 수 있는 사이트 링크이다. 프로그래머스 60057번 문제 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 길이가 n인 문자열을 입력받아 문자열 단위를 나누어서 같은 문자열이 몇 개씩 나왔는지 확인하는 문제이다. 여기서 중요한 점은 문자열 단위를 나눌 때 n//2+1 이상으로 나누면 같은 문자열이 나오지 않으므로 n//2+1까지의 문자열 단위에 대해서만 탐색을 시행하는 것이 좋다. "aabbaccc"를 이용하여 설명해.. 이전 1 2 3 4 5 다음
