전체 글

0x00 정의와 표현법 정의 그래프란 정점과 간선으로 이루어진 자료구조를 말한다. 차수는 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수이다. 그래프는 네비게이션에서 최단 경로 찾기, 혹은 구글 같은 검색엔진에서 랭킹 정하기와 같이 뭔가 원소 사이의 연결 관계를 설정해야 하는 상황에서 유용하게 활용될 수 있는 자료구조이다. 간선 그래프의 간선에는 방향성이 있을 수 있다. 왼쪽처럼 방향성이 없다면 무방향 그래프라고 하고 방향성이 있다면 방향 그래프라고 한다. 간선에 방향성이 있다는건 마치 일방통행 도로를 생각하면 된다. 방향 그래프에서도 차수라는 개념이 있는데 자기에게서 나가는 간선의 개수는 outdegree(차출 차수)이고 들어오는 개수는 indegree(진입 차수)이다. 그래프의 종류 사이클이란 ..

0x00 정의와 성질 트리는 위 그림처럼 계층 구조를 가지고 있고, 제일 꼭대기를 제외하고 각 동그라미들은 위로 딱 1개와 연결되어있는 구조 각 원소는 정점 or 노드 라고 부름 트리의 제일 꼭대기 정점을 루트(Root)라고 부름 제일 말단에서 아래로 뻗은게 없는 정점을 리프(Leaf)라고 부름 정점과 정점을 연결하는 선을 간선이라고 부름 간선으로 연결된 위 아래의 관계를 부모 자식 관계라고 부름(ex.3번 정점과 7,8번 정점은 부모 자식 관계) 어떤 한 정점에 대해 그 밑에 있는 정점과 간선만을 모은 트리를 서브트리라고 함 트리의 높이는 위 아래로 뻗어있는 정도를 나타냄 이진 트리,,, 각 노드의 자식이 2개 이하인 트리를 말한다. 자식이 2개 이하이기 때문에 자식을 왼쪽 자식과 오른쪽 자식으로 구분..

0x00 알고리즘 설명 자료구조로 위 트리는 상태공간트리라고 부른다. 0x01 연습 문제 1 - N과 M BOJ 15649번: N과 M(1) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include using namespace std; int n,m; int arr[10]; bool isused[10]; void func(int k){ // 현재 k개까지 수를 택했음. if(k == m){ // m개를 모두 택했으면 for(int i = 0; i < m; i++) cout m; func(0); } 0x..

0x00 알고리즘 설명 0x01 연습문제 1 - 거듭제곱 BOJ 1629번: 곱셈 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 첫 번째는, 수의 범위이다.제한사항을 보면 입력이 2,147,483,647까지다. 입력부터 20억이 넘어가기 때문에 20억^20억long long int 자료형을 아득히 넘어간다. 그렇기 때문에 지수를 한 번에 곱해서 구해서는 안된다.자료형을 넘지 않도록 지수를 분할하여 곱하여야 한다. 두 번째는 시간복잡도이다.그럼 한 번씩 곱할 때마다 나머지를 구하면 되지 않을까? 이러면 시간복잡도가 O(n)이 되는데,해당 문제의 시간제한이 0.5초로 시간초과..

1. 적 개체 여러개를 백터배열로 구현 2. 총알 구현 2.1 bullet.h와 bullet.cpp로 구조를 만듦 2.2 방향을 일단 오른쪽 방향으로 쭉 발사하게 구현 GIt Hub https://github.com/KangSukW00/DribbleTheSpaceship.git

Day2까지 구현한 내용들을 player, enemy로 나눠서 클래스화 시켰음 GIT주소 https://github.com/KangSukW00/DribbleTheSpaceship/tree/8c03431c25a3b8a21040ac3cb35ac1f6d50139fe/Day3

1.동적할당과 메모리 누수 확인 2.적우주선이 플레이어를 따라가게 하기 3. 적우주선 위치값을 스택에서 힙메모리로 변환시키기 #define _CRTDBG_MAP_ALLOC #include #include #ifdef _DEBUG #define DBG_NEW new ( _NORMAL_BLOCK , __FILE__ , __LINE__) #else #define DBG_NEW new #endif #include #include void UpdatePlayerPosition(sf::Vector2f& playerPossition) { bool dPressed = sf::Keyboard::isKeyPressed(sf::Keyboard::D); bool aPressed = sf::Keyboard::isKeyPress..

0x00 DFS DFS( Depth First Search) : 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 방문여부확인을 스택을이용한다 BFS( Breadth First Search) : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 방문여부확인을 큐를이용한다 0x01 예시 0x02 BFS vs DFS DFS는 한 방향으로 막힐때 까지 쭉 직진을 하는것처럼 보인다. BFS, DFS 모두 순회하면서 체크하는 알고리즘이긴 하나 BFS에서 유용하게 썻던 "현재 보는 칸으로부터 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다"는 성질이 DFS에서는 성립하지 않는다. 그래서 거리를 계산할 때에는 DFS를 사용할 수 없다. 결국 앞으로 다차원 배열에서 순..