CordCat

백트래킹은 조합 탐색과 같은 문제에서 해를 찾는 도중에 해가 될 수 없는 경우를 미리 파악하여 탐색을 중단하고 다른 경로를 탐색하는 효율적인 기법입니다. 이번 글에서는 백트래킹 알고리즘의 개념과 구현 방법, 그리고 실제 문제를 해결하는 과정을 예시를 통해 알아보겠습니다. 1. 백트래킹 알고리즘이란? 백트래킹은 문제의 조건에 따라 탐색해야 하는 모든 경우의 수를 시도하면서 해를 찾는 알고리즘입니다. 주로 DFS(깊이 우선 탐색)와 함께 사용되며, 재귀 함수를 통해 구현됩니다. 백트래킹은 가능한 경우의 수를 줄여나가면서 해를 찾는 방법으로, 탐색 과정에서 불필요한 경로를 배제하여 실행 속도를 향상할 수 있습니다. 2. 문제 설명 이제 실제로 백트래킹을 사용하여 해결할 문제를 살펴보겠습니다. 주어진 조건에 따..

문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는?를 출력한다. package codingTest.bronze; import java.util.*; import java.util.stream.Collectors; public class Bj1157 { public static void main(String[] args) { Scanner sc..

https://www.acmicpc.net/problem/9095 6개 211111 2311 2 두 개 -> 22111 5! / (2!*3!) 2 3개 -> 2221 4!/3! 4 3 하나 -> 31111 5! / 4! 3 두개 -> 331 3! / 2! 2 하나 + 3 하나 -> 2311 4!/2! -> 12 2 두개 + 3 하나 -> 223 3 이런 식으로 경우의 수를 나눠 순열조합으로 풀 수 있을 거라 생각을 해서 아래와 같이 문제를 풀었다. 순열을 이용한 풀이 import java.util.*; public cl..

우선순위 큐(Priority Queue)는 개발자가 자주 활용하는 자료구조 중 하나입니다. 이번에는 우선순위 큐에 대해 자세히 알아보고, 실제로 어떻게 사용되는지 예시 코드를 통해 살펴보겠습니다. 우선순위 큐는 요소들을 우선순위에 따라 정렬하여 저장하는 자료구조입니다. 일반적인 큐와 달리 요소들이 저장될 때 우선순위에 따라 정렬되므로, 가장 우선순위가 높은 요소에 먼저 접근할 수 있습니다. 우선순위는 개발자가 지정한 기준에 따라 결정됩니다. 예를 들어, 다익스트라 알고리즘에서 최단 경로를 찾는 과정에서 우선순위 큐를 사용할 수 있습니다. 출발지에서 각 노드까지의 최단 거리를 계산할 때, 우선순위 큐를 활용하여 현재까지의 최단 거리를 기준으로 노드를 선택하고 처리할 수 있습니다. 아래는 우선순위 큐를 활용..

DP는 다양한 문제에서 사용되는 효율적인 알고리즘 기법 중 하나이다. 코딩테스트 문제를 풀다가 최단 경로 문제에 DP의 필요성을 알게 돼서 DP에 대해 정리해 본다. 최단 경로 문제는 출발지에서 도착지까지 가는 경로 중 가장 짧은 경로를 찾는 문제로, 다익스트라 알고리즘과 벨만-포드 알고리즘이 대표적인 예시이다. DP 배열은 중복 계산을 피하기 위해 사용되며, 최단 경로 문제에서는 각 노드까지의 최단 거리를 저장하는 역할을 하고, 각 노드까지의 최단 거리를 DP 배열에 저장하면 다음 계산에서 이전 계산 결과를 활용하여 중복 계산을 피할 수 있다. 아래는 최단 경로 문제를 DP 배열로 해결하는 다익스트라 알고리즘을 사용하여 출발지에서 각 노드까지의 최단 거리를 구하는 예시 코드이다. import java...

팩토리얼 값에서 0의 개수 구하기 주어진 숫자 n에 대한 팩토리얼 값에서 처음 0이 아닌 숫자가 나왔을 때 그전까지의 0의 개수를 구하는 문제입니다. 내가 생각한 방법 n에 대한 팩토리얼 값을 계산한 뒤, 이를 문자열로 변환하여 맨 뒤에서부터 0이 아닌 숫자가 처음 나오는 인덱스를 찾고, 이를 전체 문자열 길이에서 빼주면 0의 개수를 구할 수 있을 것이라 생각했습니다. 따라서 다음과 같이 코드를 작성해 보았습니다. static int getFactorialNum(int num) { int result = 1; for(int i=2; i= 0; i--) { if(strFactNum.charAt(i) != '0') { n1 = i; break; } } result = (strFactNum.length() -..