본문 바로가기

전체 글

 (140)
[TIL] 99클럽 코테 스터디 15일차 TIL + 백준 13417 카드 문자열 문제 풀이 문제 탐색하기카드를 가져올 때 이미 가져와진 카드 더미의 왼쪽 또는 오른쪽으로 놓을 수 있습니다. 가져온 카드가 카드 더미의 첫 문자보다 사전 순으로 앞에 위치해야 할때는 왼쪽에 카드를 놓고 뒤에 위치해야하면 오른쪽에 카드를 놓으면 됩니다. 이 과정을 반복하면 태욱이가 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 만들 수 있습니다. 이렇게 매 순간 최적의 선택을 해서 해답을 구하는 그리디 알고리즘을 적용하여 풀 수 있었습니다. 문제 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Lin..
[TIL] 99클럽 코테 스터디 14일차 TIL + 백준 14916 거스름돈 문제 풀이 문제 탐색하기거스름돈 동전의 최소로 거슬러주기 위해서는 거슬러 줄 수 있는 동전의 액수 중 제일 큰 액수의 동전을 많이 줄 수록 최소의 개수로 돈을 거슬러 줄 수 있습니다. 이 문제에서는 2원과 5원으로만 돈을 거슬러 줄 수 있으며 최소로 줄 수 있는 동전의 개수를 구하는 문제입니다. 따라서 최대로 거슬러 줄 수 있는 5원의 개수를 먼저 측정하고 거스름돈의 액수와 딱 맞아 떨어지지 않으면 5원의 개수를 하나씩 줄이면서 2원의 개수를 구해가면 되는 문제입니다.  이 문제는 매순간 최적의 선택을 해서 해답에 도달할 수 있는 그리디 알고리즘을 바탕으로 해결책을 생각할 수 있었습니다. Greedy Algorithm(탐욕 알고리즘)이란?그리디 알고리즘은 최적의 해를 구하는 데에 사용되는 근사적인 방법으..
[TIL] 99클럽 코테 스터디 13일차 TIL + 백준 27961 고양이는 많을 수록 좋다. 문제 풀이 문제 탐색하기예제를 확인하다보면 고양이가 1마리가 되고나서 N마리의 고양이를 키우기 위해서 고양이의 수를 2배로 계속 복제하는 카운트를 통해 최소 행동 횟수를 알 수 있습니다.예를 들어 33마리의 고양이를 키우고 싶다면 아래와 같습니다.0 -(생성마법)> 1 -(복제마법)> 2 -(복제마법)> 4 -(복제마법)> 8 -(복제마법)> 16 -(복제마법)> 32 -(복제마법)> 33 복제마법을 사용할 때 계속 2배로 복제하다가 2배로 복제한 수가 원하는 N의 값 보다 커지면 N이 되는 값 만큼 더해주면 됩니다. 마법을 사용하는 횟수를 카운트 하였을 때 마지막 복제 마법의 카운트와 2배 복제한 수가 N의 값보다 커질때의 카운트가 같기때문에 그 복제한 수가 N보다 커질때 while문을 종료하면 됩니다..
[TIL] 99클럽 코테 스터디 12일차 TIL + 백준 7569 토마토 문제 풀이 문제 탐색하기너비우선탐색 알고리즘을 활용하여 문제 풀면 토마토가 모두 익을때까지 며칠이 걸리는 지 구할 수 있습니다.익은 토마토가 있는 위치를 모두 큐에 넣어서  x축 y축 z축 모든 곳의 토마토를 탐색하여 익지 않은 토마토의 위치값을 증가시키며 다시 큐에 담습니다. (토마토는 3단 배열에 담아지게 되는데 익지 않은 토마토를 만났을 때 기존 탐색 노드 위치값 + 1로 위치값을 세팅해주면 됩니다.)이렇게 탐색을 반복하다가 탐색이 모두 끝났을 때 익지 않은 토마토가 하나라도 있으면 -1을 출력하고 모든 토마토가 익었을 때 증가시켰던 토마토의 위치값에서 -1을 한 값을 출력해주면 토마토가 모두 익는 최소 일자를 구할 수 있습니다.  문제 풀이import java.io.BufferedReader;im..
[TIL] 99클럽 코테 스터디 11일차 TIL + 백준 25195 Yes or yes 문제 풀이 문제 탐색하기알고리즘 파악하기곰곰이는 단방향 간선을 따라 이동하는데 이동하지 못하게 되었을 때 투어가 끝난다고 합니다. 투어가 끝나는 경우는 여러가지가 있을 텐데 그 중에서 곰곰이의 팬을 한번도 만나지 않고 투어가 끝났을때가 있는지 판단하면 됩니다.따라서 깊이 우선 탐색 (DFS)을 사용하면 곰곰이의 투어를 하나하나 탐색할 수 있습니다.  재귀호출을 통해서 구현하였는데 다음노드로 넘어가게 되었을 때 곰곰이의 팬이 노드에 존재한다면 "yes" 문자열을 "Yes" 로 변경해줍니다. 재귀호출이 종료되면 다시 탐색을 시작했던 노드로 돌아가게 되는데 이때 돌아간 노드에서의 팬을 만났는지 판단하는 문자열로 리셋해줍니다.  이렇게 탐색을 반복하다가 탐색할 수 있는 노드가 더이상 없고 문자열이 "yes" 로..
[TIL] 99클럽 코테 스터디 10일차 TIL + 백준 18352 특정 거리의 도시 찾기 문제 풀이 문제 탐색하기알고리즘 파악하기각 도시에서 갈 수 있는 도시들을 방문해가면서 처음 시작 도시에서의 거리를 측정해야하는 문제입니다.도시에서 갈 수 있는 모든 도시들을 방문하는 것을 체크하면서 진행하기 위해서는 BFS 알고리즘이 적합하다는 것을 알 수 있습니다. BFS 알고리즘으로 문제 풀이 설계하기너비 우선 탐색(BFS, Breadth-First Search) 이란?그래프 탐색 알고리즘으로, 너비를 우선으로 하여 탐색을 진행합니다. 시작 노드에서 가까운 노드를 우선적으로 탐색하며, 동일 레벨에 있는 노드를 모두 탐색한 후 다음 레벨로 넘어가는 방식입니다. BFS는 일반적으로 큐(Queue) 자료 구조를 사용하여 구현합니다. 따라서 출발지에서 방문할 수 있는 모든 도시를 방문하고 방문하지 않았던 도..
[TIL] 99클럽 코테 스터디 9일차 TIL + 백준 7562 나이트의 이동 문제 풀이문제 탐색하기BFS 알고리즘을 활용하여 풀이 설계하기 너비 우선 탐색(BFS, Breadth-First Search) 이란?그래프 탐색 알고리즘으로, 너비를 우선으로 하여 탐색을 진행합니다. 시작 노드에서 가까운 노드를 우선적으로 탐색하며, 동일 레벨에 있는 노드를 모두 탐색한 후 다음 레벨로 넘어가는 방식입니다. BFS는 일반적으로 큐(Queue) 자료 구조를 사용하여 구현합니다. BFS알고리즘에 대한 기본적인 개념 설명하고 관련 문제는 아래의 게시글에 자세히 나와있습니다.https://coding-babo.tistory.com/152 [TIL] 99클럽 코테 스터디 5일차 TIL + 백준 24444 너비 우선 탐색 1문제 풀이 문제 탐색하기너비 우선 탐색(BFS, Breadth-First S..
[TIL] 99클럽 코테 스터디 8일차 TIL + 백준 2644 촌수계산 문제 풀이 문제 탐색하기DFS 알고리즘을 활용하여 풀이 설계하기깊이 우선 탐색 알고리즘에 대해서는 아래의 게시글에 개념을 설명해두었습니다.https://coding-babo.tistory.com/151 [TIL] 99클럽 코테 스터디 4일차 TIL + 백준 24479 깊이 우선 탐색 1문제 풀이 문제 탐색하기깊이 우선 탐색(DFS, Depth-First Search)그래프 탐색 알고리즘으로, 노드를 탐색할 때 깊이를 우선하여 끝까지 탐색하는 방식입니다. 시작 노드에서 출발하여 갈 수 있는 만coding-babo.tistory.com 촌수를 계산하기 위해서 DFS 알고리즘을 활용하였습니다. 사람을 노드라고 생각하면 방문하는 노드를 배열에 체크하면서 원하는 사람이 나올때까지 탐색을 반복합니다. 재귀호출을 통..

티스토리툴바