💻 Computer Science/Algorithm

코딩 문제를 풀면서 문제 풀이 실력을 길러보자 ^!^📌 문제 요약정수 n, k가 주어진다. (1 길이 n의 정수 배열 A가 주어진다.모든 (1, r)구간(0 모든 B[l, r] 값들을 모아 오름차순으로 정렬한 뒤, k번째로 작은 값을 출력해보자.📌 풀이 아이디어O(n^2)의 시간복잡도로 가능한 모든 (l, r)구간을 만들어서 OR 값을 구할 수 있다.각 구간마다 OR 계산하고 리스트에 저장한다.정렬 후 k번째 값을 출력한다.Java codeimport java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nex..

1. 최단 경로 알고리즘이란?최단 경로 알고리즘은 그래프에서 한 정점에서 다른 정점까지 가는 데 필요한 최단 거리를 찾는 알고리즘입니다. 여기서 ‘최단’의 의미는 경로 상의 가중치 합이 가장 작다는 뜻입니다. 예를 들어, 지도에서 두 도시를 최단 거리로 연결하는 방법을 찾는 것이 최단 경로 문제라고 볼 수 있습니다.방금 제가 풀고 있던 이 문제: https://www.acmicpc.net/problem/16928 에서의 '정점'은 게임판의 칸이 될 것이며, 각 칸마다 이동하는 것이 경로를 통해 이동하는 상황이 되는 것입니다. 다만, 이 문제에서는 각 경로의 가중치가 모두 1로 동일한 상황이며, 이 경우에는 어떤 알고리즘으로 푸는 게 적합한지 글의 마지막 부분에 언급하도록 하겠습니다. 2. 대표적인 최단 ..

정렬 알고리즘 문제를 푸는 중에 매우 깔끔한 코드를 발견했습니다.저는 열심히 퀵소트로 문제를 풀었는데, 어떤 분들은 Arrays.sort와 lambda 함수를 사용해서 아주 깔끔한 코드로 풀이를 완성한 것이었죠!!! 저는 그런 식으로 코딩해본 적이 없어서 한 줄씩 뜯어봤는데,사실 '저 코드가 도대체 왜 오름차순 정렬을 하는 코드인거지???' 하는 생각이 계속 들었습니다. 그래서 다시 찾아보면서 이해를 하고 메모를 해두려고 합니당 정렬하는 부분만 작성해둔 예시 코드는 다음과 같습니다.// 예시 코드import java.util.Arrays;public class Main { public static void main(String[] args) { int[] arr1d = new int[]..

이진탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 한다. 정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능하다. 이진탐색 알고리즘이 무엇인지는, 다른 자료들을 통해 이미 충분히 많이 설명되어 있으므로 설명을 생략한다. 사용한 언어는 python이고 재귀를 사용한 방법, if-else문을 사용한 방법 두 가지를 모두 살펴보자. 문제는 찾고자 하는 원소 element가 리스트 안에 존재하면 그 원소의 인덱스를 리턴하고, 없으면 None을 리턴하는 것이다. 1. 재귀 def binary_search(element, lst): mid = len(lst)//2 if not len(lst): return None elif element == lst[mid]: return mid elif el..