알고리즘 (12) 리스트형 [알고리즘] TopCoder 알고리즘 트레이닝(1) 보호되어 있는 글입니다. [알고리즘] 파스칼의 삼각형 [문제] 아래 그림과 같은 규칙성을 가진다고 할 때, 열번호와 행번호를 주면 해당 번호에 위치한 수를 리턴하는 함수를 제작하시오(행과 열번호는 0부터 시작) 11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1... 입력: 행번호, 열번호출력: 해당행, 열에 위치한 값 ex) 입력: 2 1, 출력: 2 [풀이] 파스칼의 삼각형이라는 유명한 문제이다. 규칙성을 보면,1) 각 행의 첫번째와 제일 마지막 수는 12) 1번 규칙 이외의 값들에 대해서는 바로 윗 행의 같은 열값과 왼쪽열값의 합 위 두가지 규칙성을 보면, 특히 두번째 규칙성을 보면 점화식형태로 되어 있고, 따라서 재귀호출을 쓰면 쉽게 구현이 되겠다. (최적의 구현방법이라는 것은 아니다) private s.. [알고리즘] 행렬 경로 문제 N x N개의 방에 임의의 양수가 들어있습니다. 왼쪽 위에서 출발해서 맨 오른쪽 아래로 이동하려 할 때, 지나치는 방들의 숫자의 합이 최대가 되는 경로를 택했을 때 나오는 최댓값을 구하시오. (단, 이동은 오른쪽 혹은 아래쪽으로만 가능하고, 위로 혹은 왼쪽으로 이동이 불가하고, 대각선으로의 이동도 불가능 합니다.) - 입력 첫째 줄에 테스트의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다. 첫째 줄에 가로칸의 개수 N이 주어진다. 그리고 그 다음줄부터 N개의 행값이 주어진다. 예) 1 4 6 7 12 5 5 3 11 18 7 17 3 3 8 10 14 9 - 출력 최적의 경로로 이동했을 때, 경로상의 값들을 더한 값을 출력한다. 예) 1번 테스트의 경우 더한 최댓값이 68인 경우 # 1:.. [알고리즘] 자료구조 배열과 문자열배열에 대한 질문이나 문자열에 대한 질문들은 서로 바꿀 수 있습니다. 다시 말해, 배열에 관한 것들은 문자열에 대한 문제로 바꿔 출제할 수도 있으며, 그 반대도 가능합니다. 해시 테이블해시 테이블은 효율적인 탐색을 위한 자료구조로서 키(Key)를 값(Value)에 대응시킵니다. 해시 테이블을 아주 간단히 구현하는 경우, 배열과 해시 함수만 있으면 됩니다. 객체와 키를 해시 테이블에 넣게 되면 우선 해시 함수가 키를 정수값으로 대응시키는데, 이 정수값이 배열의 인덱스로 쓰입니다. 객체는 배열의 해당 인덱스 위치에 저장됩니다. 하지만 이렇게 구현해서는 제대로 동작하지 않을 것입니다. 모든 가능한 키에 대해서 해시 함수가 계산해 내는 정수값이 유일해야 하기 때문입니다. 유일성이 보장되지 않을 경우.. [알고리즘] 비선형구조의 탐색, 그래프의 구현 비선형구조의 탐색 비선형 구조란, i번째 원소를 탐색한 다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 다음에 탐색할 수 있는 원소가 여러 개 존재하는 구조. 일반적으로 트리나 그래프 형태로 자료를 구성할 수 있을 때 해당됩니다. 이러한 트리나 그래프 형태의 모든 정점(값/데이터)을 탐색하는 것을 비선형구조의 탐색이라고 생각할 수 있습니다. 비선형구조는 탐색해야할 데이터가 순차적으로 구성되어있지 않습니다. 단순한 반복으로 탐색할 수가 없기 때문에 스택(stack)이나 큐(queue)와 같은 자료구조를 활용해 탐색할 방법과 순서를 만들어 탐색하는 것이 일반적입니다. 비선형구조의 대표적인 예 : 트리, 그래프 데이터가 저장되어있는 곳: 정점(vertex) / 노드(node)데이터들을 연결시키는 사이의.. 이전 1 2 3 다음
