알고리즘
알고리즘20 :: Graph Search
알고리즘20 :: Graph Search
2019.02.27* 그래프 탐색모든 시작점 x에서 모든 정점을 1번씩 하는것을 의미한다. * 깊이 우선 탐색 vs 너비우선탐색 깊이는 갈수있을때까지 진행하고 못가면 뒤로백 합니다. 너비는 한정점에서 갈수있는걸 동시에긴다. 어떤 순서로 방문하는가가 중요한데, Dfs는 보통 스택을 이용하고, 이 목적은 모든 정점을 한번씩 방문한다. 가 가장 핵심 포인트다. Check 배열이 필요하다. 순서는 상관없다. 스택에 쌓인다. 그러면, 1 - 2 - 3 - 4 - 5 - 5에서 더이상 갈수있는게없음 스택 이용 기록중 전정점4로 돌아감 -6 방문을 6까지 하고 스택이비면 탐색 종료한다. Dfs는 재귀함수를 쓴다. 스택으로 구현할 수 도 있다. dfs를 인접리스트로 구현하게 되면 존재하는 간선만 저장하게 되는데,반면에, 시간복잡도는 인..
알고리즘19 :: Graph(bfs)
알고리즘19 :: Graph(bfs)
2019.02.27그래프는 정점과 간선으로 이루어진다. 경로는 간선으로 이루어져있으며 이동할수있다. 최단경로가 경로중 가장 짧은것을 의미 가중치가 제일 작은것이 최단경로다 사이클은 시작점 = 도착점 방향이 있으면 역으로 갈수없다. 방향이없으면 간선은 방향이없다. 양방향이다. 방향없는그래프는 저장할수없어서 가는방향, 오는방향을 저장한다. 루프는 돌아오는것 가중치는 간선에 값이있는것이다. 가중치가없으면 1이다. 차수는 연결되어있는 간선의수 방향그래프는 인디그리, 아웃디그리를 나눠서 계산한다. *그래프 저장방법? 정점과 간선을 저장한다. 정점은 개수를 저장하면된다. 간선은 어떤간선이 있는지 다 저장해야한다. 어떤 정점 x와 연결된간선을 효율적으로 찾기위해서 저장한다. *인접행렬 1이면 간선이 있고 0은 간선이 없음 방향이없으면..
알고리즘17 :: BOJ_3053_택시기하학
알고리즘17 :: BOJ_3053_택시기하학
2019.02.26이 문제는 우리가 일반적으로 아는 원의 넓이 구하는 방법가 문제에서 제시하고 있는 택시 기하학이란 정의로 원의 넓이를 구하는 것이다. 원의 넓이야 PI * R^2 을 하면 된다. https://librewiki.net/wiki/%ED%83%9D%EC%8B%9C_%EA%B8%B0%ED%95%98%ED%95%99 에 따르면 택시 기하학은 정사각형 이라고 한다. 따라서, 위 그림처럼 원 안에 정사각형을 둔 형태를 고려해 봤을때 지름 2R 은 정사각형의 대각선이랑 같게 된다. root(2) * 정사각형 한 변의 길이 = 대각선의 길이 라는 공식을 가져와서 보면 이식을 풀었을때 정사각형의 넓이는 2*R^2 이 되는것을 알 수 있다. 기하학에 대한 식견을 넓힐 수 있는 문제였던거 같다. 1 2 3 4 5 6 7 8..
알고리즘16 :: BOJ_13241_최소공배수
알고리즘16 :: BOJ_13241_최소공배수
2019.02.25단순히 최소공배수를 구하는 문제였다. 다만, 두 수가 서로소 일경우는 if(b==1)이 없이는 무한루프가 돌 수 있기 때문에 b==1 이란 블락을 하나 생성하여 추가해줬다. 최소 공배수는 알다싶이, (a*b)%gcd 로 계산할 수 있다. 주의할 점은 문제에서 언급한대로 값이 크기 때문에 long long int를 사용해야 했었다. (...처음에 서로소를 찾는 문제인줄 알고 에라토스 테네스 체를 구현하고 있었는데, 다시 보니까 전혀 아니더라카더라) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include using namespace std; const int MAX = 1000000; int prime[MAX]; int pn; b..
알고리즘15 :: BOJ_1107_리모컨
알고리즘15 :: BOJ_1107_리모컨
2019.02.25이 문제는 입력으로 주어지는 수에 대해서 완전탐색, 즉 브루트포스 를 통해 해결할 수 있는 문제다. 리모컨으로 누를 수 있는 수는 0~9 까지이다. 이때 입력받는 채널은 최대 500,000인데 고장난 버튼을 고려하면 1,000,000이되어야 한다. 버튼이 6빼고 전부 고장났다고 생각해보면 입력받은 채널은 500,000 일때 66666 500,000 666,666 66666에서 500,000 을 +버튼을 누르는것보다 666,666 에서 -버튼을 누르는것이 비용적으로 덜들게된다. 접근방법은 다음과 같다. 1. 처음 시작 버튼 100번에서 +로 증가할수 있는 횟수를 파악한다. 2. 완전탐색을 진행하면서 고장나지 않은 버튼으로 입력받은 채널각각의 숫자와 몇개가 일치하는지 개수를 length로 잡고, 현재 값과 ..
알고리즘14 :: BOJ_1057_토너먼트
알고리즘14 :: BOJ_1057_토너먼트
2019.02.25이 문제를 풀때 짝수, 홀수를 정확하게 찾아내고 싶어서 블로그들을 찾아봤는데, 이런 방법이 있었다. NUM = NUM / 2 + NUM % 2; 처음에 생각한 아이디어는 다음과 같다. 테스트케이스 16 8 9 의 경우 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16이면 여기서 홀수 일경우 +1 을 더해준다. 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16가 된다. 여기서 /2 를 해주게 되면 다음 순번을 확인할 수 있게 된다. 1 2 3 4 5 6 7 8 여기서도 +1을 더해준다. 2 2 4 4 6 6 8 8 마찬가지로 /2를 해주게 되면 다음 순번을 확인할 수 있다. 1 2 3 4 결국 이렇게 WINNER까지 올라가게 된다. 이때 조건을 형성하여 반복문을 빠..
알고리즘13 :: BOJ_2293_동전1
알고리즘13 :: BOJ_2293_동전1
2019.02.23DP가 어렵다고 느끼는 이유는 점화식을 세워야 한다. 이 문제는!! DP를 연습하기 좋은 문제지 않나 생각해본다. 위 두 블로그를 통해서 방법은 같지만 서로 다른 점화식을 확인할 수 있었다. 요약하자면 다음과 같다. 문제에서는 k원이라고 주어졌지만, 테스트 케이스 10원으로 예시로 든다면 1원 부터 테스트 케이스(원) 까지 만들 수 있는 방법을 전부 고려해보는것이 가장 첫 번째 스텝인것 같다. 이때 입력으로 주어진 동전을 고려해 봐야 하는데 테스트 케이스로 주어진 1원, 2원 그리고 5원을 고려해보자. 1원으로 1~10원을 만들 수 있는 방법은 각각 1원은 1가지 방법 2원도 1가지 방법 ... 10원도 한가지 방법이다. 1원으로 뭔 짓을 해봤자 1가지 방법밖에 나올 수 없다. 2원으로 1~10원을 만들..
알고리즘12 :: BOJ_2577_숫자의개수
알고리즘12 :: BOJ_2577_숫자의개수
2019.02.23핵심 포인트 : % 와 / % 는 1234567 이 있으면 10으로 % 시 7 을 획득할 수 있다. / 는 1234567 이 있으면 123456 을 획득할 수 있다. 이때 10으로 계속 % 반복하게 되면 순서대로 7 6 5 4 3 2 1 을 얻을 수 있게 된다. 여기서! 배열을 이용해서 각 배열의 index를 활용해서 0~9 까지지만 1~10으로 인지하여 각 index의 값을 추출하면 숫자마다 몇번 나타났는지 알 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; int main(void){ int a = 3, cnt = 0, total=1; int arr[3], arr2[10]={}; memset(arr, fa..
알고리즘11 :: BOJ_더하기사이클_1110번
알고리즘11 :: BOJ_더하기사이클_1110번
2019.01.05C++로 작성한 코드입니다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include #include using namespace std; int main() { int c; int temp, count=0; int temp_A, temp_B, temp_C; cin >> c; temp = c; while (temp != c || count == 0) { temp_A = temp % 10; //1의 자리 temp_B = temp / 10; //10의 자리 temp_C = (temp_A + temp_B) % 10; temp = (temp_A * 10) + temp_C; count++; ..
알고리즘10 :: 쇠막대기
알고리즘10 :: 쇠막대기
2019.01.04123456789101112131415161718192021222324#include #include #include #include using namespace std; int solution(string str) { vector st; int result = 0; for(int i=0; i
알고리즘이란?
알고리즘이란?
2018.12.26알고리즘이란? 문제를 해결하기 위한 여러 동작들의 모임입니다. 이를 해결하기 위해 수학적이고 논리적으로 정의된 계산 단계에 따라 원하는 출력을 하는 절차를 거칩니다. 통상적으로 알고리즘은 입력과 출력을 갖고 있습니다. 오류가 존재하면 안되는 점(명확성) 그리고 메모리의 가용영역을 고려하여 효율적인 알고리즘을 작서앻야 합니다. 하나의 알고리즘을 예로 들어보겠습니다. 하기 알고리즘은 최대 공약수를 구하는 알고리즘입니다. 최대 공약수라 함은 손으로 쉽게 구할 수 있지만 코드화 하여 알고리즘을 통해 구할 수 있는 부분도 있습니다. 본 알고리즘 로직은 큰 수에서 작은 수를 빼는 가정을 두 수 중 하나가 0이 될 때까지 반복하면, 0이 아닌 수가 최대공약수입니다. 1 2 3 4 5 6 7 algorithm gcd(..