Lang (28) 썸네일형 리스트형 [알고리즘/C++] 요세푸스 순열 문제 Josephus problem # 요세푸스 문제 Josephus problem 요세푸스 문제 Josephus problem 혹은 요세푸스 순열 Josephus permutation 이라고 합니다. 자연수 n, k ( k < n )이 있습니다. n명이 동그랗게 앉아있을 때 임의의 한 명부터 순서를 세어 k번 째 사람을 제외합니다. 다음 사람부터 k번째 사람을 제외합니다. 이렇게 제외되는 사람의 순서가 요세푸스 순열이고, 마지막에 남는 (혹은 제외되는)사람을 구하는 문제가 요세푸스 문제입니다. # 알고리즘 이해 n=5; k=3; 으로 가정합니다. 즉 다섯 명이 모여있고, 세 번째 순서일 때마다 제외합니다. # 코드 예제 #include #include using namespace std; int main(){ int n, k, x, re.. [C#] sealed 한정자 # sealed 클래스에 붙은 한정자 sealed는 다른 클래스가 상속 할 수 없습니다. public class A{} public sealed class B : A {} public class C : B {} // 에러 발생 클래스 B는 A를 상속할 수 있습니다. 클래스 C는 sealed 한정자가 붙은 B를 상속할 수 없습니다. 또한 가상 함수도 봉인하여 재정의할 수 없게 할 수 있습니다. class A{ protected virtual void F() {Consol.WriteLine("this is F() with A"); } } class B : A{ sealed protected override void F() {Consol.WriteLine("this is F() with B"); } } cla.. [알고리즘/C] 등수 매기기 (브루트 포스: brute force) # 문제 여러명의 점수가 배열로 있을 때, 각 점수의 등수를 매겨야 합니다. 점수 배열이 20 40 10 50 30 이렇게 들어오면 등수는 4 2 5 1 3 로 나와야 합니다. # 브루트 포스 : 전체 탐색 알고리즘 int score[5] = {20, 40, 10, 50, 30}; int rank[5] = {1, 1, 1, 1, 1}; for(int i=0; i [C#] out var 파라미터 out은 참조를 통해 인수를 전달하는 키워드입니다. return 으로 반환값을 받지 않기 때문에, 2개 이상의 값도 가져올 수 있습니다. 간단한 사용방법은 아래와 같습니다. 함수 호출부와 함수 정의부에서 out 키워드를 사용해야 합니다. int x, y; Get(out x, out y);// 함수 호출부 Console.WriteLine($"{x}:{y}"); void Get(out int x, out int y) // 함수 정의부 { x = 10; y = 20; } 출력결과 10:20 C# 7부터 더욱 편리해졌습니다. Get(out int x, out int y);// 변수 선언없이 사용 Console.WriteLine($"{x}:{y}"); void Get(out int x, out int y) { x.. [알고리즘] 너비 우선 탐색 Breadth First Search # 문제 설명 아래 그림과 같은 이진트리를 너비 우선 탐색해봅니다. 간선의 정보를 입력받아 처리합니다. 인접 리스트를 이용합니다. queue 자료구조를 직접 구현합니다. 너비 우선 탐색은 시작 노드부터 인접한 노드들을 모두 우선 방문하는 방식의 탐색 방법입니다. 시작 노드인 노드1을 방문 한 후 노드1에 인접한 노드2, 노드3을 방문합니다. 노드2에 인접한 노드4, 노드5를 방문합니다. 노드3에 인접한 노드6, 노드7을 방문합니다. 노드4는 인접한 노드가 없으므로 끝입니다. 노드5 ~ 노드7은 노드4와 같습니다. 다르게 이야기하면 시작 노드부터 간선 한 번에 인접한 노드들을 순회하고, 간선 두 번에 인접한 노드들을 순회하고, 간석 세 번에 인접한 노드들을 순회하는 방식으로 볼 수 있습니다. # 입출력 예.. [C] 자료 구조 # 단일 연결 리스트 Single Linked List # 연결 리스트 각 노드가 데이터와 다음 노드를 가리킬 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료 구조입니다. - 배열과 다른 점 세 개의 데이터가 있는 배열[3]이 있다면 배열[0]부터 배열[2]까지 메모리의 연속된 곳에 자리하게 됩니다. 연결리스트는 각 노드가 각자 생성될 때 할당받은 다른 메모리 주소를 갖습니다. 그래서 다음 노드의 주소를 가리키는 포인터가 필요한 것입니다. - 장단점 데이터의 추가 삭제가 빠릅니다. 시간복잡도 O(1) 특정 위치의 데이터 검색이 오래걸립니다. 시간복잡도 O(n) - 노드 Node 노드에는 각종 데이터 변수와 다음 노드를 가리킬 포인터 변수가 필요합니다. 따라서 여러가지 타입의 집합체인 구조체로 정의합니다. struct Node{// 노드 이름 int val.. [C#] 자주 사용하는 문자열 관련 함수 # 문자열 함수 리스트 함수와 서식 설명 PadLeft(10) 문자열의 길이를 10으로 만들면서 좌측에 공백 만들기 PadRight(15) 문자열의 길이를 15로 만들면서 우측에 공백 만들기 IndexOf("대상 문자열") 가장 먼저 나오는 대상 문자열의 첫 번째 인덱스를 리턴합니다. 없으면 -1 리턴. LastIndexOf("대상 문자열") 가장 마지막에 나오는 대상 문자열의 첫 번째 인덱스를 리턴합니다. 없으면 -1 리턴. IndexOfAny( 문자 배열 ) 문자 배열에 있는 문자를 발견하면 그 인덱스를 리턴합니다. Substring(2, 3) 문자열 2번 인덱스에서부터 3개 문자를 리턴합니다. Contains("x") 문자열 "x"가 포함되어 있으면 true을 리턴합니다. StartsWith("y".. [C++] 컨테이너 어댑터 Stack 컨테이너 어댑터란? 기존 컨테이너의 기능을 제한하거나 변형한 컨테이너를 만들어줍니다. STL의 컨테이너 어댑터 종류. 컨테이너 어댑터 설명 스택 ( stack) LIFO ( Last In First Out ) 나중에 삽입된 요소가 먼저 반환됩니다. 큐 (queue) FIFO ( First In First Out ) 먼저 삽입된 요소가 먼저 반환됩니다. 우선순위 큐 (Priority queue) 우선 순위가 높은 요소를 먼저 반환합니다. # stack의 멤버 함수 멤버 함수 설명 push(x) stack의 상단에 값 x를가진 요소를 추가한다. pop() stack 상단의 요소를 제거한다. top() stack 상단 요소의 값을 읽어 레퍼런스로 리턴한다. size() stack의 사이즈를 리턴합니다. emp.. [C] 포인터 # 함수 포인터의 이해 # 함수 포인터의 정의 함수 포인터는 함수를 가리키는 포인터입니다. 포인터는 메모리상의 주소를 저장하는 변수인데, 함수도 메모리에 존재하며 그 시작 주소가 있으므로 포인터 변수로 가리킬 수 있습니다. 정수형 데이터 타입을 가리키는 정수형 포인터는 정수형 변수의 주소를 가집니다. 하지만 함수는 그 안에 여러 데이터 타입이 있을 수 있기 때문에 좀 더 복잡한 선언 형식이 필요합니다. * 함수포인터의 선언 리턴 타입 (*변수명)(인수의 목록) int func(int x); 라는 함수를 가리키는 함수 포인터를 선언하려면 int (*mypf)(int x); 로 선언해야합니다. - 함수 포인터 선언 방법 함수 선언식에서 1. 함수명을 필요한 변수명으로 바꾸고 2. * 를 붙이고, 3. ( ) 감싸면 됩니다. 여기에.. [C] 문자열 서식 # 이스케이프 시퀀스 # 이스케이프 시퀀스 종류 이스케이프 시퀀스 설명 \n 커서를 한 줄 아래로 내립니다. \a 윈도우 경고음 출력 \b 커서를 한 칸 왼쪽으로 이동합니다. \r 커서를 그 줄의 맨 왼쪽 처음으로 이동합니다. \t 커서를 탭 만큼 오른쪽으로 이동합니다. \" 문자 " 자체를 출력합니다. \' 문자 ' 자체를 출력합니다. \\ 문자 \ 자체를 출력합니다. \? 문자 ? 자체를 출력합니다. \ooo 아스키코드 문자를 8진수로 표현합니다. \xhhh 아스키코드 문자를 16진수로표현합니다. \f 프린터에서 다음 페이지로 이동합니다. 콘솔에서는 특수문자가 출력됩니다. \v 프린터에서 세로 탭으로 이동합니다. 콘솔에서는 특수문자가 출력됩니다. # 예제 #include #include int main() { printf.. 이전 1 2 3 다음
