Develog
로그인

06/30 선형 알고리즘

심지태
∙∙조회 5

선형 알고리즘과 비선형 알고리즘의 차이

선형 알고리즘은 데이터를 한 줄로 보고 순서대로 처리하는 방식이고,
비선형 알고리즘은 트리나 그래프처럼 여러 갈래로 연결된 데이터를 관계에 따라 처리하는 방식이다.

선형 알고리즘
데이터가 일렬로 나열된 구조에서 처음부터 끝까지 순차적으로 처리하는 알고리즘이다.
배열, 리스트, 스택, 큐 같은 선형 자료구조에서 자주 사용된다.

알고리즘설명
선형 탐색배열을 처음부터 끝까지 하나씩 확인
순차 출력리스트의 모든 요소를 차례대로 출력
스택 처리가장 위의 요소부터 순서대로 처리
큐 처리먼저 들어온 요소부터 순서대로 처리

비선형 알고리즘
데이터가 일렬로 나열되지 않고 계층, 분기, 연결 관계를 가지는 구조에서 처리하는 알고리즘이다.
트리, 그래프 같은 비선형 자료구조에서 자주 사용된다.

알고리즘설명
DFS한 방향으로 깊게 탐색
BFS가까운 노드부터 넓게 탐색
트리 순회전위, 중위, 후위 순회
최단 경로 탐색그래프에서 가장 짧은 경로 탐색

알고리즘 짤 때 종이나 그림판에 적어가면서 하는 것이 아주 좋음

-> ★슈도코드(의사코드)의 습관화

 

IEnumerable

스택, 큐 도 순회 가능

컬렉션을 foreach로 순회할 수 있게 해주는 가장 기본적인 인터페이스이다.

인덱스 접근이나 Add, Remove 같은 수정 기능은 제공하지 않고,

데이터를 하나씩 읽는 순회 용도로 사용된다.

List, Array, HashSet 등 다양한 컬렉션과 호환되기 때문에

단순히 읽기만 할 때 사용하면 메서드의 범용성이 높아진다.

 

IList

인덱스를 가진 목록 형태의 컬렉션을 나타내는 인터페이스이다.

foreach 순회뿐만 아니라 Count와 인덱스 접근을 이용한 for문 순회가 가능하며,

Add, Remove, Insert 같은 요소 수정 기능도 제공한다.

List 처럼 순서와 인덱스가 필요한 컬렉션을 다룰 때 사용한다.

확장 메서드 Extension Method

확장 메서드는 기존 클래스의 코드를 직접 수정하지 않고도,

마치 그 클래스에 원래 있던 메서드처럼 사용할 수 있게 해주는 문법입니다.

예를 들어 string 클래스에 직접 코드를 추가할 수는 없지만, 확장 메서드를 만들면 이렇게 사용할 수 있습니다.

확장 메서드 예시

public static class StringExtension

{

csharp
public static string ToUpperFirst(this string str)

{

    if (string.IsNullOrEmpty(str))

        return str;

    return char.ToUpper(str[0]) + str.Substring(1);

}

}

사용:

string text = "hello";

string result = text.ToUpperFirst();

Console.WriteLine(result); // Hello

확장메서드 조건

조건설명
static 클래스 안에 있어야 함확장 메서드는 반드시 static class 내부에 선언해야 함
static 메서드여야 함메서드 자체도 반드시 static이어야 함
첫 번째 매개변수에 this가 있어야 함어떤 타입을 확장할지 지정함
this 매개변수는 첫 번째에만 올 수 있음두 번째 이후 매개변수에는 this 사용 불가
접근 가능한 namespace에 있어야 함해당 확장 메서드가 있는 namespace를 using해야 사용 가능