목록알고리즘 (26)
Seung's Learning Record
연결 리스트란? 연결 리스트란 쉽게 말해 원소를 저장할 때, 그 다음 원소의 위치를 같이 저장하는 선형 자료구조이며, 이때 원소들은 붙어있지 않고 흩어져있다. 연결 리스트를 사용했을때의 주요 시간 복잡도는 다음과 같다. k번째 원소를 확인/변경하기 위해서는 O(k)가 필요함 => 해당 연산을 반복 수행해야하는 경우, 연결 리스트보다 배열이 효율적(배열은 O(1)) 임의의 위치에 원소를 추가/제거는 O(1)이 필요함 => 해당 연산을 반복 수행해야하는 경우, 배열보다 연결 리스트가 효율적(배열은 O(N)) 연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. 단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 구조 이중 연결 리스트 - 각 원소가 자신의 이..
해당 문제를 풀기 위해 필요한 사전 지식으로는 아스키코드와 배열정도일 것이다. 당장에 구글에만 쳐봐도 정답 코드가 넘쳐난다. 그러던중 바킹독님의 풀이가 유독 눈에 띄어서 정리할 겸 가져와봤다. #include #include using namespace std; int main(void){ int arr[26]={0}; string s; cin >> s; for(auto c : s) arr[c-'a']++; for(auto i : arr) cout
알고리즘과 자료구조를 공부하기에 앞서 필수가 되는 지식 중 하나인 시간 복잡도와 공간 복잡도에 대해 정리해보자 복잡도 복잡도란 쉽게 말해 알고리즘의 성능과 효율성을 나타내는 척도이다. 복잡도를 나타내는 표기법으로는 O(빅오), Ω(오메가), Θ(세타)등이 있고, 주로 빅오 표기법과 세타 표기법이 많이 사용된다. 복잡도에는 수행 시간을 평가할 수 있는 시간 복잡도와 사용 공간을 평가할 수 있는 공간 복잡도가 있다. 시간 복잡도(Time Complexity) 시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다. 알고리즘의 성능 평가는 아래와 같은 case를 나누어 평가한다. CASE 설명 최선의 경우 (Best Case) 최적의 입력 상태에서 작업을 완료하는데 걸린 연산 횟수가 ..
브루트 포스? 브루트 포스(brute force)의 사전적 의미는 '무식한 힘'이다. 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 '해가 하나 이상 존재한다.'는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 복잡한 알고리즘없이 빠르고 쉽게 구현이 가능하다는 장점이 있지만, 알고리즘의 실행시간이 오래걸리며 메모리 효율성이 떨어진다는 단점이 있다. 종류 선형 구조 : 순차탐색 비선형 구조 : 백트래킹, DFS, BFS 선형 구조 - 순차탐색 순차 탐색(Sequential Search)는 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로..
문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 일단 이 문제를 처음 본 후 나는 머야 쉽네 하고 엄청난 자신감으로 for문을 써내려갔고 기특하게도 ' 맞았습니다!! '라는 문구가 나를 반겨줬다. 아래는 내가 작성한 코드이다. import java.io.*; import java.util.Scanner; public class NUM2609 { public static void main(String[] args) throws ..
문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다. 예제 입력 1 복사 5 1 2 1..