□ 이론 (26) 썸네일형 리스트형 각 방향으로 이동한 위치 값을 반복문으로 구하는 방법 ▶방향에 따른 이동 위치 값 반복문으로 구하기알고리즘 문제를 해결하다 보면 어떤 좌표에서 4~8방향으로 이동한 위치 값이 필요한 경우가 있습니다.만약 매번 모든 방향으로 이동한 위치 값을 확인해야 한다면 반복문을 통해 구현하는 것이 편리합니다. 예를 들어, 2차원 공간의 (x,y)의 위치에서 상/하/좌/우 네 방향으로 한 칸씩 이동한 위치 값이 필요하다면 (x는 행, y는 열을 나타냅니다!)상 : (x-1, y)하 : (x+1, y)좌 : (x, y-1)우 : (x, y+1) 이렇게 네 개의 위치 값을 구해야 합니다. 이해를 돕기 위해 (3,3)에서 상/하/좌/우 네 방향으로 이동했을 때 위치 좌표값을 나타낸 그림을 그려보았습니다. 이 네 방향의 위치 값을 편하게 구하기 위해서 아래와 같은 방법을 씁니다.. 조합 생성 알고리즘 한번에 정리하기 ▶조합 (Combination)서로 다른 n개의 원소 중에 r개를 순서와 상관 없이 뽑은 것을 조합이라고 합니다. 뽑아낼 수 있는 조합의 모든 경우를 알아내야 하는 문제들이 많습니다.기본적인 구현 문제이지만 공부하지 않으면 어떻게 구현해야 할지 몰라 막막하게 느껴지기도 합니다. 조합을 코드로 구현하기 위해서 재귀 함수에 익숙해질 필요가 있습니다.재귀함수를 이해하기 위해 백준 온라인 저지에서 '피보나치 수를 구하는 문제'나 'N과 M'과 같은 문제들을 풀면서 재귀함수에 익숙해지도록 연습하는 것을 추천합니다. 1234567891011121314151617181920212223242526272829303132333435#include#includeusing namespace std; int n,r;vector.. 그래프(Graph)를 표현하는 방법에 대하여 ▶그래프그래프는 정점들의 집합 V와 간선들의 집합 E로 이루어진 자료구조입니다. ▶그래프 표현 방법그래프를 표현하는 방법으로 인접 행렬과 인접 리스트가 있습니다. 정점의 개수가 N개인 그래프를 인접 행렬로 표현하려면 (N+1) x (N+1) 크기의 2차원 배열이 필요합니다. 무 방향 그래프인 경우에 1번 정점과 2번 정점이 연결되어있다면 (1,2)와 (2,1)에 모두 1을 저장해 두 정점이 연결되었음을 표현합니다. 만약 방향 그래프인 경우에 1번 정점에서 2번 정점으로 화살표가 그려져있다면 (1,2)에만 1을 저장하는 방식입니다. int adj[5][5] = {0,}; // 1번 정점과 2번 정점이 연결된 경우adj[1][2] = 1; adj[2][1] = 1; 정점의 개수가 N개인 그래프를 인접 리스트.. 해싱(Hashing)에 대하여 ▶해싱 (Hashing)해싱은 일종의 데이터 관리 기법이며, 키(key)를 해시값(Hash Value)에 매핑하는 것을 말합니다.해시함수에 의해 키가 해시값으로 변환되며, 해시함수는 인풋으로 키를 받아서 아웃풋으로 해시값을 반환하도록 구현합니다. 해시함수는 다른 두 개의 키에 대해 동일한 해시값을 반환할 수 있습니다.입력 가능한 모든 키에 대해, 키를 유일한 해시값으로 만들어줄수록 좋은 해시함수로 평가받을 수 있습니다. 키를 유일한 해시값으로 변환하는데 O(1)의 시간이 걸린다면,해당 키가 이미 존재하는지 탐색하는 연산을 O(1)의 시간에 처리할 수 있다는 뜻이 되므로 해싱은 상당히 유용하게 사용될 수 있는 기법입니다. HashFunction( key ) → Hash Value ▲ 문자열 타입의 키를 정.. [알고리즘] 시간 복잡도 쉽게 이해하기 ▶시간 복잡도, 이정도는 알고 있어야 한다! 알고리즘을 공부할 때 가장 먼저 나오는 개념이 시간 복잡도입니다. 문제 해결에 있어서 시간 복잡도를 줄이는 방법을 이해하고 활용하는 것이 알고리즘을 배우는 주된 목적이기 때문이죠. 시간 복잡도를 표기할 때 가장 일반적으로 사용되는 것은 빅오(O)-표기법 입니다. 어떤 알고리즘으로 문제를 해결하기 전에 입력 값에 따라 무엇을 어떤 변수로 놓을지 결정하고 난 뒤, 문제를 해결하는데 필요한 연산의 횟수를 식으로 구합니다. 구해진 식에서 최고 차항만을 남깁니다. 그 식에 최악의 입력 크기 값을 대입해보고 그 때에도 충분히 빠른 시간 내에 해결이 가능한지를 판단합니다. 예를들어 1부터 N까지의 누적합을 구하는 문제가 있다고 합시다. N의 범위는 1 로컬 저장소와 원격 저장소(GitHub) 연동하기 ▶로컬 저장소와 원격 저장소(GitHub) 연동하기 1. git bash 실행 2. git config --global user.name "FIRST_NAME LAST_NAME"자신을 나타낼 이름을 입력한다. e.g) git config --global user.name "earthk" 3. git config --global user.email "ID@example.com"깃허브 가입시 사용한 이메일을 입력한다. e.g) git config --global user.email "k94earth@naver.com" 4. cd [절대_경로]폴더 생성할 위치로 이동 e.g) cd ~/Desktop/ 5. git clone [원격저장소_URL] [로컬에_생성할_폴더명]필요한 url은 해당 원격 저장소의 clo.. DBMS란? ▶DBMS(Data Base Management System)데이터베이스의 내용을 정의/조작/제어할 수 있도록 함으로써 모든 사용자나 응용 프로그램들이 데이터베이스를 공유할 수 있도록 관리/운영해주는 소프트웨어 시스템을 말한다. 즉, 사용자와 데이터베이스 간의 중계 역할을 하는 S/W 시스템이다. e.g) 관계형 DBMS : MySQL, MS-SQL, Oracle ▶DBMS의 필수 기능기능 설명 정의 저장될 데이터의 형태, 구조 등 데이터베이스의 저장에 관한 여러가지 사항을 정의 조작 사용자의 요구에 따라 데이터베이스에 저장된 데이터의 검색/갱신/삽입/삭제 등을 지원 제어 데이터의 정확성과 안전성 유지를 위한 관리 기능 제공 (데이터의 무결성 유지, 보안, 병행 수행 제어 등) ▶DBMS의 장/단점장점 .. 삽입 정렬(Insertion sort) ▶삽입 정렬 (Insertion sort)앞에서부터 정렬될 하나의 데이터를 왼쪽으로 비교하며 swap해서 제 자리를 찾아가도록 정렬시키는 방법이다. 정렬될 데이터가 처음부터 제 위치에 있다면 바로 다음 데이터를 확인하게 되므로, 배열에 데이터가 대부분 정렬되어 있는 경우라면 삽입 정렬이 유리하다. 하지만 데이터가 정렬되어 있어야 하고 삽입/삭제가 빈번한 경우 처음부터 set/map에 데이터를 저장하여 사용하는 게 더 효율적이다. int arr[7] = {5,2,7,4,3,6,1}; 이런 배열이 선언되어있고, 이 배열의 원소들을 정렬한다고 해보자. 이해를 돕기 위해 표를 그려보았다. N개의 원소를 순서대로 확인하면서 바로 앞에 자신보다 큰 원소가 있다면 자리를 바꾸는데, 자신의 앞에 자신과 같거나 작은 원.. 이전 1 2 3 4 다음
