Algorithm & Data Structure/문제풀이47

• [Algorithm] 백준 2573 (BOJ 2573) 빙산 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 2573번 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/2573 1. 문제 설명 해당 문제에서 요구하는 바는 단순합니다. 주변에(상하좌우 인접)에 바다가 있으면 바다의 개수만큼 빙산의 높이가 감소하고, 주어진 빙산이 2 덩이로 분리될 때는 최초의 년수를 구해서 출력하면 됩니다. 한 가지 신경 써야 할 부분은 빙산의 높이가 얼마큼 감소하는지를 계산할 때, 이전 빙산이 다 녹아서 바다가 된 경우는 계산에 포함하지 않아야 한다는 점입니다. 실제로는 동시다발적으로 높이가 감소하는 형태이니까요 이 부분만 고려하시면 어렵지 않게 풀 .. Algorithm & Data Structure/문제풀이 2022. 4. 11.

• [Algorithm] 백준 2468(BOJ 2468) 안전 영역 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 2468번 안전영역 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/2468 1. 문제 설명 해당 문제는 BFS순회를 통해 2차원 배열의 상하좌우가 연결되어있는 영역이 최대일 때의 개수를 구하면 되는 문제입니다. 문제에서는 따로 비가 얼마나 내린다라는 명시가 없는데, 지문을 자세히 보면 "내리는 비의 양에 따른 개수를 모두 조사해보면~" 이란 문구가 있는데 이를 통해서 내릴 수 있는 비의 모든 높이를 탐색해보라는 것을 알 수 있습니다. 여기까지 보면 전부 탐색해야 하나 싶으실 텐데, 사실 그렇진 않습니다. 결국 땅이 잠기는 건.. Algorithm & Data Structure/문제풀이 2022. 4. 7.

• [Algorithm] 백준 5014(BOJ 5014) 스타트링크 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 5014번 스타트 링크 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/5014 1. 문제 설명 해당 문제는 내가 현재 있는 층(S)에서 목표로 하는 층(G)으로 이동하기 위해 엘리베이터를 몇 번을 이용해야 하는지를 출력해야 하는 문제입니다. 사실문제가 S, G, U, D 이런 문자들을 서서 읽기가 조금 불편할 뿐이지 BFS를 통해서 아주 쉽게 풀 수 있습니다. 간단한 풀이이므로 글로 설명을 해보자면 다음과 같습니다. 현재 있는 층에서 엘리베이터를 이용해 이동할 수 있는 2가지의 경우를 모두 구합니다. 이동한 층을 모두 방문 .. Algorithm & Data Structure/문제풀이 2022. 4. 5.

• [Algorithm] 백준 2644(BOJ 2644) 촌수계산 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 2644번 촌수 계산 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/2644 1. 문제 설명 문제에서 요구하는 것은 두 사람 간의 촌수를 계산하는 것입니다. 문제 해결을 위해서 DFS, BFS 둘 중 어느 걸로 접근해도 상관은 없습니다. 저는 둘 중에서 BFS를 선호하기 때문에 BFS로 풀었습니다. 그래프 문제를 풀 때처럼 문제에서 주어진 사람 간에는 간선의 길이가 1로 연결되었다고 보고, 인접한(이동 가능한) 노드로 이동한다고 생각하면서 코드를 작성하였습니다. 어려운 문제는 아니므로 바로 코드를 살펴보겠습니다. 2. Jav.. Algorithm & Data Structure/문제풀이 2022. 4. 5.

• [Algorithm] 백준 3085(BOJ 3085) 사탕 게임 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 3085번 사탕 게임 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/3085 1. 문제 설명 이번 문제는 완전 탐색을 사용한 구현 문제입니다. 보드의 크기가 최대 50이므로 완전 탐색으로 모든 경우의 수를 체크해봐도 시간 복잡도 상에서는 문제가 없습니다. 그러므로 인접한 사탕의 색이 다른 경우 사탕끼리 바꾸고, 같은 색으로 연속된 최대의 길이를 구하면 됩니다. 한 가지 주의할 점은 사탕의 위치를 바꾸지 않았을 때가 최대의 길이가 나올 수도 있으므로, 초기 상태에서 최대의 길이를 미리 구해놓고 시작해야 한다는 것입니다. 그 외.. Algorithm & Data Structure/문제풀이 2022. 4. 5.

• [Algorithm] 백준 5639번(BOJ 5639) 이진검색트리 문제풀이! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 5639번 이진 검색 트리 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/5639 1. 문제 설명 해당 문제는 읽어보셔서 아시겠지만 이진 검색 트리를 직접 구현하면 되는 문제입니다. 문제에서는 이진 검색 트리를 전위 순회한 결과를 입력값으로 준다고 말하지만, 생각해보면 그냥 전위 순회 결과든 뭐든 정수를 받아서 내가 구현한 이진 검색 트리에 저장하고 나서 후위 순회를 돌리면 되는 문제입니다. 간단한 문제이므로 코드를 살펴보겠습니다. 2. Java로 문제 풀이 package study.blog.codingknowjam.algo.. Algorithm & Data Structure/문제풀이 2022. 4. 4.

• [Algorithm] 백준 1655번(BOJ 1655) 가운데를 말해요 (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 1655번 가운데를 말해요 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/1655 1. 문제 설명 문제에서 요구하는 바는 숫자가 하나씩 추가가 될 때, 현재까지 나온 숫자들 중에서 중간값을 출력하면 됩니다. 숫자의 개수가 홀수면 중간값이 1개이고, 짝수인 경우는 중간값이 없기 때문에 중간에 있는 두 수중에서 작은 수를 출력하면 됩니다. 문제를 해결하기 위한 가장 간단한 방법은 정수가 추가될 때마다 배열을 정렬해서 중간에 있는 값을 출력하는 것입니다. 그러나 이러한 방식으로 접근을 하게 되면 시간 초과 판정을 받게 됩니다. 문.. Algorithm & Data Structure/문제풀이 2022. 4. 4.

• [Algorithm] 백준 1107(BOJ 1107) 리모컨 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 1107번 리모컨 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/1107 1. 문제 설명 해당 문제는 모든 경우의 수를 확인해서 풀어야 하는 완전 탐색, 브루트 포스 유형의 문제입니다. 실제로 문제를 풀다 보면 경우의 수를 하나씩 놓치게 되는데 생각보다 고려해야 할 사항이 많습니다. 특별한 알고리즘보다는 경우의 수만 잘 확인하면 풀리는 문제이므로 막상 풀면 어렵지 않았다고 생각하실 겁니다. 먼저 문제에서 요구하는 사항은 현재 채널은 100번이며 이동해야 할 채널까지 리모컨 버튼을 얼마나 최소로 클릭할 수 있느냐입니다. 문제를.. Algorithm & Data Structure/문제풀이 2021. 11. 26.

• [Algorithm] 백준 17142(BOJ 17142) 연구소 3 문제풀이! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 17142번 연구소 3 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/17142 1. 문제 설명 해당 문제는 많이 풀어봤던 BFS문제를 응용해서 풀면 되는 문제입니다. 기본적으로 문제에서 요구하는 바는 바이러스가 가장 빨리 퍼지는 최소의 시간을 구하는 것이기 때문에, 주어진 바이러스에서 활성 바이러스를 선택하는 모든 경우의 수를 고려해야 합니다. 모든 경우의 수마다 BFS를 수행하여 가장 빨리 바이러스가 퍼졌을 때를 찾으면 되는 문제입니다. 해당 요구사항을 구현할 때 주의할 점은 다음과 같습니다. 비활성 바이러스는 활성 바이.. Algorithm & Data Structure/문제풀이 2021. 11. 14.

• [Algorithm] 백준 14500(BOJ 14500) 테트로미노 문제풀이!! (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 14500번 테트로미노 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/14500 1. 문제 설명 해당 문제를 풀고 나서 다른 분들의 풀이를 보니 BFS나 DFS를 활용해서 푸시는 분들도 있었고 테트로미노의 모양 전부를 체크해서 문제를 푸는 분들도 있었습니다. 저는 탐색 알고리즘보다는 19개 모양에 대해서 모두 탐색해서 값을 구하는 방법으로 구현했습니다. 테트로미노 모양을 보면 긴 막대와 정사각형 모양을 제외하고는 모두 공통된 형태에 포함됩니다. 예를 들어 2개의 행과 3개의 열로 이루어진 직사각형에서 첫 행의 1,2번 열의 .. Algorithm & Data Structure/문제풀이 2021. 10. 28.

• [Algorithm] 백준 4095번(BOJ 4095) 최대 정사각형 문제풀이!!(Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 4095번 최대 정사각형 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/4095 1. 문제 설명 해당 문제는 다이내믹 프로그래밍 유형으로 문제를 풀기 위해서 점화식을 도출해야 합니다. 사실 대부분의 DP문제가 점화식만 도출하면 코드 작성은 간단한데, 이번 문제도 다르지 않습니다. 주어진 2차원 배열의 최대 정사각형의 크기를 map[i][j]로 가정하면 점화식은 다음과 같습니다. map[i][j] = min(map[i-1][j-1], map[i-1][j], map[i][j-1]) + 1 즉, 2차원 배열의 좌측 대각선, 좌측,.. Algorithm & Data Structure/문제풀이 2021. 10. 19.

• [Algorithm] 백준 16235(BOJ 16235) 나무 재테크 문제 풀이!! (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 16235번 나무 재테크 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/16235 1. 문제 설명 해당 문제는 구현 문제로써 주어진 내용에 맞게 구현하면 풀 수 있습니다. 문제에서 시간이 다른 문제에 비해 넉넉하지 않은 편이기 때문에, 코드를 구현할 때 주의해야 합니다. 해당 문제를 풀면서 몇 번 시간 초과 판정을 받았는데 다음과 같은 부분이었습니다. List를 사용해서 구현을 한다면 매 년마다 정렬을 하지는 말 것 ArrayList의 경우 remove() 할 때, 내부의 배열의 갱신될 수 있으므로 주의할 것 LinkedLi.. Algorithm & Data Structure/문제풀이 2021. 10. 9.