자바 프로그래밍/알고리즘(Algorithm) 검색 결과

해당 글 15건

알고리즘 - 그래프 탐색(깊이 우선 탐색 - DFS)

이번 포스팅에서는 그래프 자료구조의 탐색에 대해서 알아보자. 이전 포스팅에서 배열 / 리스트 형태의 자료구조에 대한 탐색 방법을 알아보았으니 관련 포스팅은 아래 링크를 참고 배열 / 리스트 탐색 : 링크 그래프 자료구조 : 링크 너비 우선 탐색 (BFS) : 링크 1. 그래프 탐색 이전 포스팅의 내용을 잠시 복습해보자. 그래프는 기본적으로 각 정점들이 어떠한 연관 관계를 갖고 있는지를 나타내는 자료구조 이다. 그래프는 가장 기본적이고 유연한 구조로 관계를 나타낼 수 있다. 많은 문제들 중 그래프로 해결 가능한 문제가 50% 정도 된다고 이야기하는 엔지니어도 있다. (참고) 해결 가능한 문제들의 예시를 대충 알아보자. 어떠한 것들이 특히 해결이 가능할까? ⓐ 네트워크 : 우리가 사용하는 컴퓨터는 인터넷으로..
자바 프로그래밍/알고리즘(Algorithm) 2020. 12. 8. 23:22

알고리즘 - 그래프 탐색(너비 우선 탐색 - BFS)

이번 포스팅에서는 그래프 자료구조의 탐색에 대해서 알아보자. 이전 포스팅에서 배열 / 리스트 형태의 자료구조에 대한 탐색 방법을 알아보았으니 관련 포스팅은 아래 링크를 참고 배열 / 리스트 탐색 : 링크 그래프 자료구조 : 링크 1. 그래프 탐색 이전 포스팅의 내용을 잠시 복습해보자. 그래프는 기본적으로 각 정점들이 어떠한 연관 관계를 갖고 있는지를 나타내는 자료구조 이다. 그래프는 가장 기본적이고 유연한 구조로 관계를 나타낼 수 있다. 많은 문제들 중 그래프로 해결 가능한 문제가 50% 정도 된다고 이야기하는 엔지니어도 있다. (참고) 해결 가능한 문제들의 예시를 대충 알아보자. 어떠한 것들이 특히 해결이 가능할까? ⓐ 네트워크 : 우리가 사용하는 컴퓨터는 인터넷으로 연결된다. 각 컴퓨터나 네트워크 장..
자바 프로그래밍/알고리즘(Algorithm) 2020. 12. 6. 23:33

알고리즘 - 탐색(선형, 이진, 점프, 보간, 삼진 탐색)

우리는 데이터를 많은 자료구조에 저장할 수 있다. 데이터를 저장하는 이유는 필요할 때 찾아서 연산하고 그 결과를 재사용하는 등 여러 추가 작업을 위한 것이다. 그러한 저장된 데이터를 찾아내기 위해 탐색 알고리즘에 대해 알아보자. 1. 순차 탐색(Sequential Search) 한글 명칭이 정확한지는 모르겠다. 이 방법은 배열이나 리스트 형태의 자료구조에서 순차적으로 앞 또는 뒤에서부터 모든 데이터를 탐색하는 방식이다. 순차 탐색의 예시로는 선형 탐색(Linear Search) 방식이 있다. 말 그대로 반복문을 사용해서 처음부터 끝까지 탐색을 수행하는 방식이다. 코드를 보면 바로 이해할 수 있다. package com.test; public class LinearSearch { public static ..
자바 프로그래밍/알고리즘(Algorithm) 2020. 12. 3. 21:06

알고리즘 - 소수 구하기

1. 개요 소수는 Prime number, 즉 1과 자기 자신 이외에는 약수를 갖지 않는 수를 의미한다. 예를 들면, 2, 3, 5, 7, 11, 13, 17, 19 등의 숫자를 통해 알 수 있다. 이러한 소수를 코드를 통해 찾아낼 수 있다면 어떨까? 이에 대해서는 여러가지 방법이 있다. 그 중 가장 성능이 좋은 방법들까지 천천히 알아보자. 만약, 1~10만 까지의 숫자 중 소수를 모두 찾으라고 하면 성능이 좋지 않다면 시간이 오래 걸릴 것이다. 따라서 좋은 성능으로 소수를 찾는 법도 알아두는 것이 좋다. [방법] ① 1부터 [해당 숫자 / 2] 까지 나누어 나누어지는지 직접 확인하는 것이다. ([] 는 가우스 기호이다.) ② 현재 해당 숫자보다 작은 소수들로만 나누어서 판별한다. ③ 현재 숫자가 K라면..
자바 프로그래밍/알고리즘(Algorithm) 2020. 11. 20. 22:52

알고리즘 - 최대공약수 / 최소공배수

1. 개요 2개의 숫자를 입력받았을 때, 최대공약수 / 최소공배수를 구하는 방법을 알아보자. 최대공약수 GCD(Greatest Common Divisor) 2개의 숫자가 입력되었을 때, 각각이 가지는 약수 중 공통의 값 중에서 가장 큰 값을 말한다. ex) 10과 8의 최대공약수는 2이다. 최소공배수 LCM(Least Common Multiple) 2개의 숫자가 입력되었을 때, 각각이 가지는 배수 중 공통의 값 중에서 가장 작은 값을 말한다. 최소공배수는 두 수의 곱에 최대공약수를 나누면 구할 수 있다. ex) 10과 8의 최소공배수는 40이다. 이를 코드로 어떻게 구현할 수 있을까? 최대공약수를 구할 때, 1부터 시작하여 두 수 중 작은 수에 도달할 때까지 찾아 가장 큰 공약수를 구할 수도 있다. 하지..
자바 프로그래밍/알고리즘(Algorithm) 2020. 11. 19. 22:45

알고리즘 - 표기식(전위 / 중위 / 후위)

1. 개요 수식은 일반적으로 3가지로 표현한다. ① 중위 표기식(In-fix) : 우리가 평상 시 사용하는 표기방식으로 연산자가 중간에 위치한다. 예) a+b ② 전위 표기식(Pre-fix) : 연산자가 앞 쪽에 위치한다. 예) +ab ③ 후위 표기식(Post-fix) : 연산자가 뒤 쪽에 위치한다. 예) ab+ 중위 표기식 개념은 우리가 편리하게 이해할 수 있기 때문에 자주 사용되는 것을 이해할 수 있다. 그러나 다른 방식은 왜 사용될까? 전위, 후위 표기식은 중위 표기식 대비 이점이 있다. 연산자의 우선 순위에 대한 고려를 추가로 하지 않고 전체 방정식을 즉시 해석할 수 있다. 예를 들어, 특정 @, # 이라는 연산자를 정의했다고 하자. 그러면 중위 표기식에서는 이들의 우선 순위를 파악하지 않으면 연..
자바 프로그래밍/알고리즘(Algorithm) 2020. 11. 18. 23:05

알고리즘 - Union-Find(Disjoint-Set 구현하기)

1. Union-Find 란? 이는 Disjoint-Set을 표현할 때 사용되는 자료구조이다. Disjoint-Set이란 공통의 원소가 없는 "상호 배타적"인 부분 집합으로 이루어진 원소에 대한 정보 저장 / 조작을 수행하는 자료구조를 의미한다. 자, 여기서 몇 가지 용어를 이해해 보자. Set - 집합을 의미한다. 원소를 가지며 순서는 고려하지 않는다.(List와의 차이점) Subset - 부분 집합을 의미. 집합 A의 모든 원소가 집합 B에 포함된다면 A를 B의 부분 집합이라고 한다. Superset - 초월 집합을 의미. 집합 A의 모든 원소가 집합 B에 포함된다면 B는 A의 초월 집합이라고 한다. 상호 배타적 집합 - Mutually Disjoint Set. A와 B가 서로 공유하는 원소가 전혀 ..
자바 프로그래밍/알고리즘(Algorithm) 2020. 11. 4. 20:43