티스토리

milktea_good

검색하기

블로그 홈

milktea_good

goodmilktea.tistory.com/m

IT에 관한 다양한 정보를 공유하는 블로그입니다.

구독자: 4

방명록 방문하기

반응형

주요 글 목록

기본정렬 선택, 버블, 삽입, 쉘, 퀵, 합병, 힙, 계수, 기수 정렬 모두 오름차순을 기준으로 정렬 1. 선택 정렬 첫번째 원소부터 마지막 원소까지 정렬을 한다고 했을때 전체 배열 중 가장 작은 원소를 찾아 첫번째 원소부터 순서대로 교환해가며 최솟값을 차례대로 넣는 정렬이라고 할 수 있다. 그래서 총 n번, 나머지 원소들 n-1, n-2, n-3, ... 개의 원소와 비교하게 되므로 시간복잡도는 O(n^2)이다. 2. 버블 정렬 거품이 수중위로 올라가는 것처럼 인덱스를 첫번째에서 마지막으로 이동하는 도중 해당 위치에서의 값이 다음 인덱스의 값보다 크면 교환하여 값이 큰 원소를 마지막으로 계속해서 밀어내는 정렬 방법이라고 할 수 있다. 즉 마지막위치에 최댓값을 쌓아가는 방식으로 정렬한다. 시간복잡도는 O(n^2).. 공감수 0 댓글수 0 2020. 6. 11.
오목 AI 제작 - MIN_MAX 전략을 통한 필승 수 구현 탐색을 적용시킨 오목 AI를 구현해보고 싶어서 3일동안 AI 제작을 진행하게 됐습니다. 먼저 19*19 바둑판 맵을 다 탐색을 하여 돌의 연결상태를 확인한 후 각 돌의 연결 상황마다 가중치를 부여했습니다. 그 후 Search 함수를 통해 탐색 과정에서 AI끼리 각자 가지치기 방식으로 최적의 수를 두어나갑니다. 탐색 중 상대방이 이기는 경우가 발생 하면 return 하여 가지가 갈라지는 분기점으로 돌아가 재 탐색을 시작합니다. 그렇게 탐색하는 도중 자신의 AI가 이기는 상황이 발생하면 맨 처음 좌표값을 저장한 후 그 이후부터는 모든 상황에 대해 return하여 탐색을 종료시켜 제작하였습니다. 최대 깊이 탐색은 현재 시점으로부터 30수까지 설정해 놓았습니다. 그 이유는 웬만하면 승부가 나는 시점까지 도달하고.. 공감수 4 댓글수 2 2020. 4. 26.
최소공통조상 (LCA, Lowest Common Ancestor) 최소공통조상은 트리에서 말 그대로 가장 가까운 공통 조상을 뜻한다. 참고링크: https://www.crocus.co.kr/660 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor) 알고리즘이란? LCA 알고리즘이란 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다. 예를들어 다음.. www.crocus.co.kr 코드로 구현시 핵심은 먼저 조상의 max_depth 지정이다. 이때 이 max_depth는 2^depth번째 조상을 구하기 위한 변수이기 때문에 조상을 구하는 최대 깊이는 log2(노드 최대 개수)를 올림한 값이 된다. 예를들어 노드 최대 개수가 3이.. 공감수 0 댓글수 0 2020. 1. 26.
Union-Find, 최소신장 트리 (MST, Minimum Spanning Tree) 최소신장트리는 그래프에서 일부 간선을 선택해서 만든 트리이다. 이때 간선의 개수는 노드의 개수가 n개라고 했을 때 n-1개가 된다. 간선을 선택하는 방법은 greedy 한 방법으로 가장 최소의 비용이 드는 간선을 선택하고 이미 선택이 돼 있는 2개의 노드를 선택하지 않는 조건을 지켜가며 트리를 구성하게 된다. 참고 링크: https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 관련 예제 백준: 1922 네트워크 연결 https://www.a.. 공감수 0 댓글수 0 2020. 1. 26.
위상정렬 (topological sorting) 참고: https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html [알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 위상 정렬(Topological Sort)을 이용한 기본적인 해결 방법 위상정렬 순서 1. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다. 초기에 간선의 수가 0인 모든 정점을 큐에 삽입 2. 선택된 정점과 여기에 부속된 모든 간선을 삭제 선택된 정점을 큐에서 삭제 선택된 정점에 부속된.. 공감수 0 댓글수 0 2020. 1. 26.
순열과 조합 조합 출력 문제 출처:https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 소스코드 순열 출력 문제 출처:https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다. www.acmicpc.net 소스코드 공감수 0 댓글수 0 2020. 1. 12.
확장 유클리드 호제법 유클리드 호제법을 활용하여 최대공약수를 구할 수 있다. 그리고 유클리드 호제법을 응용하여 일차방정식의 해를 쉽게 구할 수 있는 방법이 확장 유클리드 호제법 방법이다. ax + by = c 라는 방정식이 있다고 하자. 1. 좌변과 우변의 공약수가 있는 경우 약분을 하고, 우변의 값이 gcd(a,b)의 배수인 경우 gcd(a,b)로 변경한 후 해를 구한다. 그래서 gcd(a,b)가 서로소인 경우 우변을 1로 놓을 수 있다. 반대로 예를들어 162x+42y=19의 경우 19가 gcd(162,42)=6의 배수가 아니므로 해가 존재하지 않는다. a,b,c가 입력값으로 주어져 있다고 하자 먼저 확장 유클리드 호제법을 적용하기 전에 gcd(a,b)의 값이 1이라면 그렇다면 먼저 방정식을 ax + by =1 로 변환 .. 공감수 0 댓글수 0 2020. 1. 12.
트라이 (Trie) 출처: https://www.crocus.co.kr/1053 [Crocus] 트라이(Trie) 자료구조 목차 1. 트라이(Trie)란? 2. 트라이(Trie) 이해하기 3. 트라이(Trie)의 단점 4. 트라이(Trie) 접목하기 5. 트라이(Trie) 문제 풀어보기 트라이(Trie)란? 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합.. www.crocus.co.kr 트라이 (Trie)란? 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 트리 자료구조이며, 우리가 원하는 원소를 찾는 작업을 O(n)에 (단어길이 만에) 해결 할 수 있는 자료구조이다. 알파벳을 저장하려면 Trie 구조체 안에 Trie* next[26] 과 같이 포인터배열로 정의 할 수 있다. 그리고 f.. 공감수 0 댓글수 0 2020. 1. 12.
세그먼트 트리 (segment - tree) 세그먼트 트리는 해당 포스트에 설명이 잘 돼있다. 출처: http://isukorea.com/blog/home/waylight3/216 세그먼트 트리(Segment Tree) / 인덱스 트리(Index Tree) :: 강의/IT/알고리즘 :: ISU 블로그 void update_range(int node, int begin, int end, int left, int right, int diff) { update_lazy(node, begin, end); if (end 공감수 1 댓글수 0 2020. 1. 12.
최소, 최대 힙 (min & max heap) 출처:https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 자료구조 ‘힙(heap)’이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이.. 공감수 0 댓글수 0 2020. 1. 12.
이진 트리 (Binary Tree)와 순회 트리의 구성 요소 노드 트리를 구성하고 있는 각각의 요소 간선(edge) 트리를 구성하기 위해 노드와 노드를 연결한 선 루트노드 트리 구조에서 최상위에 있는 노드 단말노드(Terminal node) 하위에 다른 노드가 연결돼 있지 않은 노드 비단말노드, 외부노드(Internal node) 단말 노드를 제외한 모든 노드, 루트노드 포함 Binary tree (이진트리) 루트를 중심으로 두개의 서브트리로 나눠지고 그 두개의 서브트리도 모두 이진트리여야 한다. -> 재귀적인 정의 Full binary tree (포화이진트리) 모든 level이 꽉 찬이진트리 Complete Binary tree (완전이진트리) 위에서 아래로, 왼쪽에서 오른쪽 순서대로 차곡차곡 채워진 이진트리 순회 방식 전위 순회 전위 순회(p.. 공감수 0 댓글수 0 2020. 1. 12.
큐 (Queue) 큐는 First In First Out 구조이다. 기본 동작으로는 push,pop,size,empty 등이 있다. 이 기본 동작원리는 다음 문제를 통해 구현하였다. 출처:https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 소스코드 공감수 0 댓글수 0 2020. 1. 12.
스택 (Stack) 스택은 Last In First Out 구조이다. 기본 동작으로 push, pop, empty, size, top 등의 연산이 있고 다음 소스코드를 통해 어떻게 스택이 동작되는지 보자. 다음은 스택의 동작 구현에 관한 기본적인 문제이다. 출처:https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 소스코드 또한 스택을 활용하는 대표적인 문제는 괄호계산기이다. 다음 문제를 보자 출처:https://w.. 공감수 0 댓글수 0 2020. 1. 12.
합병정렬 (MergeSort) 합병정렬은 대표적인 분할 정복 알고리즘이다. start==end가 되기 직전까지 분할을 계속 하다가 즉 start,start+1,// end-1,end 와 같이 분할이 단일범위까지 진행되다가 다시 이 단일 범위서부터 분할했던 경로 그대로 역순으로 되돌아가며 정복을 하는 알고리즘이다. 분할 정복을 하는 순서는 항상 다음을 따른다. mid=(start+end)/2를 기준으로 start~mid 부분인 좌측 부분의 분할이 먼저 이루어지고 그다음 mid+1~end까지 분할이 이루어진 후 합병이 시작된다. 즉 큰 틀로보면 왼쪽분할 - 오른쪽분할 - 정복 순서를 원자단위에서부터 차례차례 수행해 나가는 구조이다. 그리고 이를 그림으로 그려보면 다음과 같다. 원자단위로 왼쪽부터 분할 해 나간 후 오른쪽부분을 분할하고 정.. 공감수 0 댓글수 0 2020. 1. 12.
투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) 알고리즘 설명 출처: https://m.blog.naver.com/kks227/220795165570 투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09) 조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다.첫 번째로 소개해드릴 기법은 투 포인터(tw... blog.naver.com 투포인터 혹은 스라이딩 윈도우 기법은 연속적인 구간의 합이나 경우의 수를 구할때 매우 유용하다. 처음에 두개의 포인트 P1,P2를 설정하고 예를들어 배열의 구간 합이 특정 값을 만족할때 그 값을 만족하는 구간의 수를 구하는 문제가 있다. 이떄 배열이 모두 양수라고 가정을 하면 p2가 커질수록 합은 계속 증가하게 된다. 그래서 만약 합이 커.. 공감수 0 댓글수 0 2020. 1. 12.
이분탐색 (Binary Search) 이분탐색 알고리즘 참고:https://wootool.tistory.com/62 [알고리즘] 이분 탐색 이분 탐색 탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식입니다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠릅니다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐.. wootool.tistory.com 이분탐색 알고리즘은 주어진 범위 내에서 구하고자 하는 값을 절반씩 줄여나가며 탐색하는 알고리즘이다. 따라서 탐색하는데 걸리는 시간은 1/2씩 좁혀나가므로 O(logN)이 된다. 알고리즘에 대한 상세한 설명은 문제와 소스코드를 분석하며 보자. 백준: 2805 나무자르기 https://www.acmicpc.net/problem/2805 2805번: 나무.. 공감수 0 댓글수 0 2020. 1. 12.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.