프로그래밍(TA, AA)/알고리즘 (18) 리스트형 [수학] 인수분해 정리 수학1 공부를 다시하고 있습니다. 기본 개념 정리부터 다시 파고 있는데요. 그동안 공식만 외워서 수학을 했었다는것이 굉장히 후회 스럽습니다. 개념을 다시 파다보니 저는 그동안 공부를 했던게 아니라는 걸 절실히 느꼈습니다. 암기형 학습이였던건데, 그런 학습에는 한계가 있기 마련입니다. 서술 관련 강의를 수강하고 있는데, 수1범위에서 개념 정리하 필요한 부분을 여기 포스팅에 찬찬히 정리해 나가겠습니다. 인수분해대수론과 대수학에서, 인수 분해는 곱이 정의된 집합내의 어떤 원소를 다른 원소들의 곱으로 표현하는 것을 가리킵니다. 특히, 정수집합에서 어떤 주어진 정수를 소수들의 곱으로 표현하는 것을 소인수 분해라고 부릅니다. 따라서 소인수 분해는 인수분해의 일종이 됩니다. 일반적으로는 한 다항식을 두 개 이상의 인.. [알고리즘] 비선형구조의 탐색, 그래프의 구현 비선형구조의 탐색 비선형 구조란, i번째 원소를 탐색한 다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 다음에 탐색할 수 있는 원소가 여러 개 존재하는 구조. 일반적으로 트리나 그래프 형태로 자료를 구성할 수 있을 때 해당됩니다. 이러한 트리나 그래프 형태의 모든 정점(값/데이터)을 탐색하는 것을 비선형구조의 탐색이라고 생각할 수 있습니다. 비선형구조는 탐색해야할 데이터가 순차적으로 구성되어있지 않습니다. 단순한 반복으로 탐색할 수가 없기 때문에 스택(stack)이나 큐(queue)와 같은 자료구조를 활용해 탐색할 방법과 순서를 만들어 탐색하는 것이 일반적입니다. 비선형구조의 대표적인 예 : 트리, 그래프 데이터가 저장되어있는 곳: 정점(vertex) / 노드(node)데이터들을 연결시키는 사이의.. [알고리즘] 깊이우선 탐색, 너비우선 탐색 깊이우선 탐색 트리나 그래프와 같은 비선형구조는 어떤 문제 상황이나 가능한 답들과 그 관계들로 생각할 수 있습니다. 깊이우선 탐색(Depth First Search)은 어떤 정점을 방문한 후, 그 정점에 연결된 다른 정범으로 파고 들어가는 형태의 탐색 방법입니다. 깊이 우선 탐색은 가능한 가장 깊이 들어갔다가 더이상 파고들어갈 수 없을때 이전상태로 복귀하고 파고들어가고 나오고를 반복하는 형태입니다. 반면, 너비우선 탐색방법은 어떤 방점에서 연결된 가장 빠른 정점들을 방문한 후에 다시 같은 방법들을 연결된 순서들을 다시 방문해 나가는 방법입니다. 깊이우선 탐색 (Depth First Search) : 어떤 정점을 방문하여 확인한 후 그 정점과 연결된 정점들 중에서 우선 순위가 가장 빠른 하나를 선택해 방문.. [알고리즘] Lower bound, Upper bound Lower bound선형구조의 부분탐색법인 이분탐색은 찾고자 하는 값이 없으면(맨 마지막 값) 탐색 실패! 하지만, lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치입니다. lower bound의 경우에는 같은 원소가 여러개 있더라도 상관없습니다. 찾고자 하는 값 이상의 값이 처음 나타나는 위치를 찾아내기 위해, 이분탐색 방법에서의 조건을 조금 변경하면 됩니다. [문제] n개로 이루어진 정수 집합에서 원하는 수 k이상인 수가 처음으로 등장하는 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어 있으며(이분 탐색 가능), 같은 수가 여러개 존재할 수 있다. 입력) 첫 줄에 한 정수 n이 입력된다. 둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다. 셋째 줄에는 찾고자 하는 값 k.. [알고리즘] 정보과학과 문제, 선형구조의 탐색 프로그래밍 언어를 활용해 해결 가능한, 정보과학의 문제 이해와 기본적인 문제 해결 방법인 선형탐색 방법을 이해를 목표로 본 포스팅을 작성합니다. 1. 정보과학과 문제 정보과학에서 다루어지는 문제? 계산문제(computational problem) 계산 가능한 문제 계산 불가능한 문제 1. N이하의 자연 수 중 짝수의 갯수는? 2. 폐구간 [a, b]에서 소수는 존재하는가? 3. N개의 원소를 가지는 집한 S의 원소를 오름차순으로 나열하고, 그 최댓값을 구하시오. 4. N개의 원소로 이루어진 집합의 부분집합들 중 그 원소의 합이 k인 부분집합이 존재하는가? 5. 좌표평면 상에 N개의 점의 한 점에서 출발하여 모든 점을 지나고 출발점으로 돌아오는 경로의 길이 중 가장 짧은 길이는 얼마인가? 1. 우리반 학생.. 이전 1 2 3 4 다음
