본문 바로가기

분류 전체보기

 (84)
브루트포스[2] - 재귀 함수 브루트포스 재귀함수를 사용하는 예제 문제풀이  재귀함수는 아래 4가지를 먼저 생각하고 알고리즘을 작성하는게 좋다.1. 인자구성2. 정답을 찾음3. 불가능한 경우4. 다음 경우 호출더보기어떤 재귀함수의 호출이 이전과 영향을 받지 않을 경우 다이나믹으로 바꿀수 있다. 부분수열 : 앞의 정보가 뒤의 정보에 영향을 주므로 다이나믹이 아님 다이나믹 : 앞의 정보를 몰라도 뒤의 정보 풀이가 가능한 경우.재귀 문제 풀이 6603 로또 : www.acmicpc.net/problem/96631 . 재귀 인자dfs(a : 입력으로 주어진 수, index : 선택할지 말지 결정할 인덱스, cnt : 현재까지 포함한 수의 개수2.  정답을 찾은 경우cnt ==63. 불가능한 경우index>=a.size4. 다음경우//선택lo..
브루트포스[3]:백트레킹(backtracking) 알고리즘 중 하나인 백트레킹 설명과 문제풀이. 백트레킹(backtracking, 퇴각검샘) 백트레킹은 유망성 검사를 만족하는 경우 모든 조합의 수를 살펴보는 것이다. 유망성 검사를 만족하지 않은 경우 많은 부분 조합들을 배제할 수 있고 모든 경우의 수를 모두 찾는 것보다 훨씬 빠르고 풀이 시간이 단축된다. 구현방법은 DFS와 같은 구조이지만 유망성 점검을 하냐 안하냐로 구분된다. 어떤 노드의 유망성 점검후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. 브루트포스는 모든 방법을 만드는 것이나, 백트레킹은 아무리 해봤자 의미가 없다 싶을 때 호출을 중단하는 것. 백트레킹 알고리즘의 설명에 관해서 매우 설명이 잘되있는 블로그가 있기 때문에 참고하면 좋을 것 같다! idea-sk..
비트마스크(BitMask) 비트마스크를 활용한 테크닉과 기법 비트마스크 자체는 알고리즘이 아니지만 다른 알고리즘과 같이 사용되어 어렵게 느껴질 수가 있다. 비트마스크(BitMask) 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법 이를 활용하면 비트연산을 통해 삽입,삭제,조회 등이 간단해짐 시간복잡도 O(1)으로 더 빠른 연산이 가능 메모리를 적게 사용함 비트 연산 AND (&) OR (|) XOR (^) SHIFT (>>,> n; for (int i = 0; i > a[i]; } for (int i = 0; i < (1 maps[i][j]; if (maps[i][j] == 'R') { r.first = i; r.second = j; } if (maps[i][j] == 'B') { b.firs..
[서평]내가 미래를 앞서가는 이유[未來に先回りする思考法] - 사토 카츠아키 요즈음 책 읽기 시작해서 간단하게 메모만 하다가 좀 더 기록을 남기고 이해하고 싶어 서평을 쓰게 되었다. 책을 읽고 지식을 실제로 내가 알 수 있는 건 반의 반도 안된다고 생각하지만 내용을 정리하고 다시 읽어보며 좀 더 이해할 수 있으면 좋겠다. 1. 테크놀로지 진화의 패턴 테크놀로지의 3가지 '본질' : 1. 인간의 확장 2. 인간에 대한 교육 3. 손바닥에서 우주로 현재 우리가 말하는 인공지능은 대부분 약한 인공지능이다. 이는 '인간의 정신이란 무엇인가?'라는 질문은 너무 어려워서 풀 수 없기 때문에, 결과적으로 인간과 같은 능력을 보여주면 그것을 '인공지능'이라 불러도 된다는 현실적인 입장이다. 인간은 패턴의 집합체 얼굴은 인식하는 카메라와 같이, 카메라에서 클라우드로 가는 과정은 눈(오감, 기계로..
트리(Tree) 트리 : 사이클이 없는 그래프, 정점의 개수 : V, 간선의 개수 : V-1 루트가 있는 그래프 : 루트를 1번이라고 하며, 루트부터 아래로 방향을 정할 수 있다.부모(Parent)자식(Children)단말 정점(Leaf Node, Terminal Node) : 자식이 없는 노드형제(sibling) : 같은 부모를 가지는 노드깊이(Depth) : 루트에서 부터 거리(루트의 깊이는 0 or 1로 표기가능)높이(Height) : 깊이중 가장 큰값조상(Ancestor) : 자기자신을 포함하여 루트와 이어지는 노드자손(Descendent) : 조상과 반대트리의 지름(Diamater) : 트리에 존재하는 모든 경로 중에서 가장 긴 것의 길이 - 2번의 탐색으로 구할 수 있다. - 1. 루트에서 모든 정점까지의 거..
그래프(Graph) 그래프(Graph) : 정의 구성 : 정점(Vertex), 간선(Edge) G = (V, E) 경로(Path) 사이클(Cycle) 단순 경로와 단순 사이클(Simple Path and Simple Cycle) : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클(일반적인 경우) 방향 있는 그래프(Directed Graph) 방향 없는 그래프(Undirected Graph,) : 양방향 그래프(Bidirection Graph) 간선 여러개(Multiple Edge) 루프(Loop) 가중치(Weight) 차수(Degree) 연결요소(Connected Component) 이분그래프(Bipartite Graph) : DFS또는 BFS 탐색으로 이분 그래프인지 아닌지 확인가능 플러드 필(Floo..
정렬(Sorting), Stable_Sorting youtu.be/kPRA0W1kECg 정렬 알고리즘을 소리로 표현한 영상이다. 정렬 방법은 30가지가 넘는 여러가지가 있다., 정렬 알고리즘의 종류로는 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬, 병합 정렬, ...... 등 여러가지가 있지만, 알고리즘 문제풀이에서 주로 사용하는 것들은 정렬시간이 O(NlogN)이 걸리는 정렬을 사용한다. 정렬을 직접 구현하는 것보다는 STL에 있는 sort를 사용하는 것이 좋다.
수학 1. 나머지 연산 2. 최대공약수와 최소공배수 3. 소수 4. 에라토스테네스의 체 5. 골든바흐의 추측 6. 관련문제 수학문제 복습! 1. 나머지 연산(Modular Arithmetic) 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제가 등장한다. 더보기 예를 들어, 다이나믹 문제를 풀때 경우의 수가 너무 큰경우 int값이나 long 값을 넘어서, 값을 처리를 하기 위해서 큰 정수값(big integer)을 구현하기 보다는 몇으로 나눈 나머지를 처리하라는 문제가 많다. (A+B) mod M = ((A mod M) + (B mod M)) mod M (AXB) mod M = ((A mod M) X (B mod M)) mod M 나누기의 경우에는 성립하..

티스토리툴바