안 쓰던 블로그

문제 풀 때마다 맨날 헷갈려서 정리했음 1. 일반 배열 내림차순 정렬 #include #include using namespace std; int n, a[10]; bool compare2(const int&x, const int&y) { return x > y; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } sort(a, a + n, compare2); for (int i = 0; i < n; i++) { printf("%d\n", a[i]); } } 2. vector 오름차순 정렬 #include #include #include using namespace std; int n; vector a(5)..

배열 C언어 자료형 중 int, double 등과 달리 char은 문자를 표현하는 변수입니다. char형은 독립적으로 이용되기도 하지만 문자열을 조작할 수 있는 배열로도 많이 이용됩니다. 배열은 '변수의 집합'으로, 여러 개의 데이터를 동시에 저장하고 조작할 수 있습니다. 배열은 선언 방식에 따라 1차원이나 2, 3차원 등의 다차원 배열로 나누어집니다. 1차원 배열로 예를 들자면, char a[5]; 이렇게 선언하면 a변수는 5문자를 담을 수 있는 문자열 변수가 됩니다. 이외에도 int a[3]; //정수형 변수 3개를 담을 수 있는 배열 double a[33]; //부동소수형 변수 33개를 담을 수 있는 배열 등이 있습니다. 1. 1차원 배열 #include int main() { char a[6] =..

탐욕 알고리즘이란? 탐욕법이란 이름 그대로 ‘눈 앞에 보이는 최선’을 탐욕적으로 선택하는 것을 반복하는 알고리즘 설계 패러다임 중 하나입니다. 탐욕법을 이용한 일고리즘을 탐욕 알고리즘, 그리디 알고리즘이라고 합니다. 전체를 여러 조각으로 나눠서 각 단계마다 답의 일부를 만들어 간다는 점에서 완전 탐색과 비슷하지만, 모든 선택지를 보는 완전 탐색과 달리 탐욕 알고리즘은 지금 당장 가장 좋은 해답을 선택합니다. 탐욕 알고리즘의 대표적인 문제로는 각 물건의 무게와 가치가 주어졌을 때, 가방에 가치가 높은 물건을 최대한 많이 담는 경우를 찾는 배낭 문제(Knapsack problem)이 있습니다. 탐욕 알고리즘의 한계 탐욕 알고리즘은 매 순간 가장 좋은 선택지만 고르기 때문에 전체적으로 봤을 때 더 좋은 선택지..

알고리즘 문제풀이란? Hello World! 알고리즘 세계에 오신 것을 환영합니다. 알고리즘이란 용어는 ‘문제를 해결하기 위한 절차나 방법’을 의미하는 포괄적인 단어입니다. 소프트웨어가 어떻게 돌아가는지부터 암호, 기계학습, 심지어는 ‘계란 샌드위치를 만드는 과정’도 알고리즘이라고 할 수 있습니다. 우리 소학회에서는 그중에서 프로그래밍에서 사용하는 알고리즘(자료구조, 그래프, 문자열 등)을 문제를 풀면서 트레이닝하는 ‘문제풀이’ 부분을 다룰 것입니다. 알고리즘 문제풀이는 크게 네 가지 단계로 나누어집니다. (1)문제를 읽고 (2)입력을 받아서 (3) 계산하고 출력합니다. 이번 주에 할 내용은(1) 번과알고리즘 문제풀이의 가장 기본적인 단계, 입력과 출력입니다. 정수 입력과 출력 백준뿐만 아니라 거의 대부..

완전 탐색이란? 번호 자물쇠를 푸는 가장 단순한 방법이 무엇일까요? 바로 모든 경우의 수를 넣어보는 것입니다. 아주 간단한 원리지만 자릿수가 늘어날 때마다 경우의 수는 기하급수적으로 많아지기 때문에 평범한 사람의 머리로는 빠르게 풀어내지 못합니다. 하지만 컴퓨터는 가능합니다. 컴퓨터의 빠른 계산 능력을 이용하여 모든 경우의 수를 전부 탐색하는 방법, 바로 완전 탐색 입니다. 완전탐색은 답을 무조건 찾아낼 수 있지만 시간이 최고로 많이 듭니다. 시간이 많이 들면 시간 제한이 문제가 됩니다. 모든 문제는 위와 같이 시간과 메모리 제한이 주어지는데, 그렇기 때문에 완전 탐색을 하더라도 시간 제한 안에 풀 수 있는 적은 탐색 범위가 주어졌을 때 사용 가능한 알고리즘입니다. 완전 탐색의 종류 완전 탐색에는 어떤 ..

깊이 우선 탐색 = DFS트리의 순회와 같이 모든 정점들을 순서에 따라 방문하는 알고리즘을 탐색 알고리즘이라 합니다. 탐색 중에 가장 널리 쓰는 것이 깊이 / 너비 우선 탐색입니다. 일단 깊이 우선 탐색부터 하겠습니다. DFS는 한 마디로 >현재 정점과 인접한 간선을 보고 안 간 곳을 따라가다 갈 곳이 없으면 돌아가는 탐색< 입니다. 동작 과정은 이러합니다.이런 그래프가 있을 때 a-b-f-h 로 들어가고 h에서 b로 가야 되는데 이미 방문한 노드라 무시되고 f로 돌아갑니다.g-f-b-c-d-c-e까지 하고 e에서 a로 가야 되는데 역시 방문한 노드라 무시됩니다. c-b-a 순으로 돌아가면 탐색이 끝납니다. 코드는 재귀함수로 간단히 할 수 있습니다. chk배열은 정점을 방문했는지 체크하는 배열map배열이..

그래프 개념큐와 스택은 대개 선형으로 구성된 자료를 프로그램으로 표현하기 위해 고안되었고, 앞 발표에서 다룬 트리는 선형으로 표현하기 힘든 구조인 계층 구조를 표현하기 위해 고안된 자료 구조입니다. 그러나 그래프는 부모 자식 관계에 제약이 없기 때문에 좀 더 일반적이고 현실 세계의 문제를 푸는 데 유용하게 사용됩니다. 현실 세계의 문제는 보통 도로망, 사람 관계, 웹사이트 링크 관계 등등이 있습니다. 그래프 정의>어떤 자료나 개념을 표현하는 정점들의 집합과 정점을 연결하는 간선들의 집합으로 구성된 자료 구조무방향 그래프간선에 방향성이 없다화살표가 없는 간선들로 이루어져 있으며 순서가 없다 커플 >방향 그래프각 간선에 방향이 있는 그래프 짝사랑, 일방 통행 도로 >루프 그래프한 노드에서 출발한 간선이 다시..