알고리즘/백준(BaekJoon)
-
알고리즘: 백준 1697번 숨바꼭질 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 14:40
백준 1697번 링크입니다. 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net bfs를 이용하면 문제가 생각보다 쉽게 풀린다. 최대 가능 인풋이 100000이기 때문에 시간복잡도가 최대 n^2 까지 가능하다고 생각하였다. 최단거리 문제이기도 해서 bfs를 선택하였다. #include #include using namespace std; int visit[100001]; bool check(int x) { //check 함수가 중요한듯! if (x 100001) ret..
-
알고리즘: 백준 2667번 단지번호붙이기 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 22. 11:38
백준 2667번 링크입니다. 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net bfs 너비 우선 탐색을 이용하여 단지수를 찾는다. 방문한 집은 방문처리를 함으로써 반복문을 이용해 모든 집을 방문하면서 방문처리가 되어있는 주택은 패스, 방문하지 않은 집은 bfs를 시행한다. 총 단지수를 받을 house와 방문한 곳을 표시하는 visit을 만들었다. 방문했으면 visit의 해당하는 인덱스에 1을 집어 넣고, 아니면 0을 넣는다. bfs하기 전, 초기 visit[y][x] 값은 house[y][x]가 0 일때 1, ..
-
알고리즘: 백준 1010번 다리놓기 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 19:00
백준 1010번 링크입니다. 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net n개 중에 r개를 고르면 되므로 nCr을 사용하면 간단하다...고 생각했지만 아니였다. 팩토리얼을 다이나믹 프로그래밍으로 구해서 콤비네이션하려 했지만 long long 자료형을 써도 넘어가버려서 다이나믹 프로그래밍과 재귀함수를 이용하였다. nCr = n-1Cr-1 + n-1Cr 을 이용해서 recursive form을 만들어 해결하였다. #include using namespace std; int cache[30][30]; // 다이..
-
알고리즘: 백준 1018번 체스판 다시칠하기(feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 16:28
백준 1018번 링크입니다. 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net B로 시작하는 8 x 8 완성된 체스판을 chess1 W로 시작하는 8 x 8 완성된 체스판을 chess2 내가 입력받을 잘못된 체스판을 wrong_chess라고 하자 wrong_chess의 행과 열을 변화시켜 가면서 chess1과 chess2와 비교한다. chess1과 비교했을 때 잘못된 값의 갯수 = wrong_count1 chess2과 비교했을 때 잘못된 값의 갯수 = wrong_count2일때 두 값중에 더 작은 값을 ..
-
알고리즘: 백준 1037번 약수(feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 14:35
백준 1037번 링크입니다. 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되� www.acmicpc.net 방법 1 #include using namespace std; int main() { int n; int x; int max = -1; int min = 1000000; cin >> n; for (int i = 0; i > x; if (max x) { min = x; } } int answer = min * max; cout n; for (int..
-
알고리즘: 백준 10610번 30 (feat. Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 17:55
백준 10610번 링크입니다. https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 30의 배수가 되기 위한 조건은 어떤수 N이 10의 배수이고 3의 배수인 경우이다. N이 10의 배수가 되기 위한 조건 = N안에 0이 포함되어 있으면 성립 N이 3의 배수가 되기 위한 조건 = N의 모든 자리수를 더했을 때 3의 배수이면 성립 이 두 조건만 성립하면 최대값은 N을 그냥 그대로 내림차순 정렬한 값이다. import sys input = sys.std..
-
알고리즘: 백준 2217번 로프 (feat.Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 16:51
백준 2217번 링크입니다. https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 로프들이 견딜 수 있는 리스트를 만들어 오름차순으로 배열한다. 만약 10, 25, 30가 로프가 버틸 수 있는 최대중량으로 주어진다면 10 x 3 = 30 25 x 2 = 50 30 x 1 = 30 으로 최대 버틸 수 있는 중량은 50이 된다. ropes[i] * (n - i) 들로 이루어진 리스트의 최대 값을 찾으면 되는 것이다. import sys input ..
-
알고리즘: 백준 1932번 회의실 배정 (feat.Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 16:22
백준 1932번 링크입니다. https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 최대 사용할 수 있는 회의의 수를 구하기 위해서는 가장 빨리 회의가 끝나는 순으로 회의를 나열한다. 회의의 끝나는 시간을 오름차순으로 배열한 후 전 회의의 시작시간과 다음 회의의 끝나는 시간을 비교하여 리스트를 담는다. 처음에 2차원 리스트의 두번째 요소만 배열하기 위해서 이중 for문을 사용했지만 O(n) = n^2가 되기 때문에 시간초과가 되었다. 그래서 lambda x: x[1]를 key로 받아 sort 함으로써 문제를 해결하였다. import sys input = sys.stdi..