알고리즘
알고리즘28 :: BOJ_2979_트럭주차
알고리즘28 :: BOJ_2979_트럭주차
2019.09.121 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 package backjun모음; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; /* * * 하나의 점으로 본것은 큰 실수 * 범위로 체크 해야 했다. */..
알고리즘27 :: BOJ_17142_연구소3
알고리즘27 :: BOJ_17142_연구소3
2019.09.121 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 12..
알고리즘26 :: BOJ_11729_하노이타워
알고리즘26 :: BOJ_11729_하노이타워
2019.02.28123456789101112131415161718192021#include using namespace std; void func(int a, int b, int n){ if(n==1){ // a에 있는 원판 1개를 b로 옮기기만 하면 됨 cout
알고리즘25 :: BOJ_2017_미로탐색
알고리즘25 :: BOJ_2017_미로탐색
2019.02.281 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 30 31 32 33 #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 string board[102]; // '1'이 파란 칸, '0'이 빨간 칸에 대응 int dist[102][102]; // 해당 칸을 방문했는지 여부를 저장 int n,m; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미 int main(){ ios::sync_with_stdio(0); cin.ti..
알고리즘24 :: BOJ_1926번_그림
알고리즘24 :: BOJ_1926번_그림
2019.02.281 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502]; // 1이 파란 칸, 0이 빨간 칸에 대응 bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장 int n,m; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; // 상하..
알고리즘23 :: 블러드 필 알고리즘 전형적인 예제
알고리즘23 :: 블러드 필 알고리즘 전형적인 예제
2019.02.28#include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502] = {{1,1,1,0,1,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0}, {1,1,1,0,1,0,0,0,0,0}, {1,1,0,0,1,0,0,0,0,0}, {0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응 bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장 int n = 7, m = 10; // n = 행의 수, m = 열의 수 int..
알고리즘22 :: 플러드 필&BOJ_2677_단지번호붙이기
알고리즘22 :: 플러드 필&BOJ_2677_단지번호붙이기
2019.02.28어떤 위치와 연결된 모든 위치를 찾는 알고리즘이다. BOJ :: 2667 단지 번호 붙이기 문제가 대표적이다. 연결요소 를 고려해보면 된다. 단지의 개수와 크기를 구하면 된다. 이차원 배열 상에서 상, 하, 좌, 우 를 고려한 배열이기 때문에 추가적인 자료구조가 필요하지 않다. BOJ_2677_단지번호붙이기가 대표적인 예이다. 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include #include using namespace std; int ..
알고리즘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로 잡고, 현재 값과 ..