본문 바로가기

알고리즘

[알고리즘 자료구조] 연결 리스트 (Linked List) 3. 단순 연결 리스트(Simple Linked List)의 전체 모양 안녕하세요. 이번 포스팅은 단순 연결 리스트(Simple Linked List)의 전체적인 모습을 살펴보도록 하겠습니다. 아래 프로그램 코드는 제가 직접 짠 코드입니다. 딱히 어려운 부분은 없으니 눈으로 코드 한줄 한줄 직접 해석해보세요. 다음 포스팅은 환영 연결 리스트(Circular Linked List)에 대해 알아보도록 하겠습니다. 오류 & 오타 지적 그리고 댓글 환영합니다.버튼 한번 누르시고 가세요. ^^ 더보기
[알고리즘 자료구조] 연결 리스트 (Linked List) 2. 단순 연결 리스트(Simple Linked List)의 기본 뼈대 안녕하세요 이번 포스팅은 리스트중 가장 심플한 단순 연결 리스트(Simple Linked List)에 대해서 포스팅 하도록 하겠습니다. 단순 연결 리스트는 말 그대로 리스트의 종류중 가장 단순한 형태입니다. 데이터를 저장하는 노드(node)와 바로 다음의 노드를 가르키는 링크(link)하나로 구성되어 있습니다. 이해가 가시나요? 그림처럼 단순 연결 리스트는 링크가 각각 다음 노드를 가리키게 됩니다. 하지만 가장 먼저 있는 데이터 A를 누가 가리키냐는 문제 때문에, 리스트의 머리(head)를 만들어야 합니다. head는 일반적으로 전역 변수로 선언되어 어느 부분에서도 접근 가능하고, 소멸되지 않게 합니다. 연결 리스트의 마지막 노드는 무언가를 가리켜야 하는데 마지막을 나타내는 꼬리(tail)을 만들어서 이.. 더보기
[알고리즘 자료구조] 연결 리스트 (Linked List) 1. 연결 리스트란? 안녕하세요 이번에는 자료구조중 하나인 리스트를 포스팅 해보도록 하겠습니다. 일단 리스트에 대해서 알아보기 전, 자료구조라는 것을 대략적으로 설명해드리도록 하겠습니다. 데이터와 데이터를 체계적으로 구조화 한 것이라고 설명할수 있는데요. 예를들어 순차적으로 데이터를 구조화시킨다면 리스트라 하는것이고 데이터를 쌓듯이 구조화 시키면 스택이라 부르는 것입니다. 그럼 그 연결 리스트란 무엇이냐 연결 리스트는 노드(node)와 링크(link)를 구조화 시킨 것을 의미합니다. 여기서 노드(node)는 데이터를 담고있는 그릇이라 생각하시면 되고 링크(link)는 리스트의 순서를 유지할 수 있게 해주는 연결고리라 생각하시면 됩니다. 자 그럼 여기서 생각나는 하나의 의문점이 있는데요 연결 리스트와 배열의 차이점이 대체 무엇.. 더보기
입력된 정수를 반대로 출력하는 프로그램 이번 포스팅에는 입력된 정수를 반대로 출력하는 프로그램을 포스팅하겠습니다. 정수를 반대로 출력하기위해서는 입력된 n을 10으로 나누어 나머지를 구하고, n을 10으로 나누는 수를 대입하면 됩니다. 그리고 이 과정을 계속 반복하면서, n이 0이 되면 반복문을 탈출하면 됩니다. 이해가 잘 안되도 일단 프로그램 코드를 한번 보면 이해 되실겁니다. 오타 오류 지적 환영합니다. 더보기
최대 공약수 찾는 알고리즘(유클리드의 알고리즘(Euclid's algorithm))(개선) 저번에 포스팅한 최대 공약수 찾는 알고리즘은 큰 문제점이 하나 있습니다. 만약 50000과 1의 최대공약수를 구하기 위해서는 무려 50000번의 연산을 해야하기 때문입니다. 그런데 저번 포스팅에 사용한 예시 get_gcd(110.33)에서 뺄셈을 모두 끝내면 (11,33) 이 되는건 다 알 고 계실겁니다. 여기서 자세히 살펴보면 110을 33으로 나누고 나머지가 11이 나온다는걸 발견할 수 있습니다. 즉 11=110%33으로 대체가능하며 이 방법으로 많은 뺄셈 연산을 나머지 연산으로 대체가능합니다. 그렇다면 이번에는 함수를 이렇게 짜봅시다. GCD(a,b)=(a%b,b) 이렇게 불필요한 연산을 삭제함으로써 프로그램을 좀더 능률적이게 만들수 있습니다. 아래 프로그램은 이를 이용한 프로그램입니다. 오타 & .. 더보기
최대 공약수 찾는 알고리즘(유클리드의 알고리즘(Euclid's algorithm)) 최대 공약수는 A=G*aB=G*b 로 표현이 가능합니다. 그렇다면 두 수를 빼보면 A-B=(a-b)G 로 표현이 가능합니다. 그럼 만약 최대 공약수를 구하는 함수 X가 있다고 하면 X(a,b) 와 X(a-b,b) (a>b) 의 값은 같게 나오게 됩니다. 그리고 X(0,b)가 된다면 b가 최대 공약수가 되고 X(a-b,b) (a 더보기
홀수 짝수 구하는 알고리즘 홀수 짝수인지를 구하기 위해서는 2로 나누어서 나머지가 0인지 1인지 알아보면 됩니다. 예를 들어, 5를 2로 나누면 나머지는 1이 됩니다 -> 5%2=1 4를 2로 나누면 나머지는 0이 됩니다 -> 4%2=0 아래 프로그램은 이를 이용한 프로그램입니다. 오타나 지적 부탁드립니다. ^^ 더보기