algorithm
-
백준 1543 문서 검색Algorithm/BOJ 2020. 6. 15. 13:31
출처: www.acmicpc.net/problem/1543 분류: 그리디 접근방식 문자열 매칭 문제 입니다. 겹치지 않게 문자열을 찾으면 됩니다. 문서 길이가 2500정도 밖에 안되서 단순 매칭으로도 해결할 수 있는 문제입니다. 문제는 탐색의 시작을 반드시 0번부터 할 필요는 없다는 것이죠. 첫번째부터 탐색한거보다 그 이후부터 탐색을 시작해서 더 경우가 많아지는 반례는 찾지 못했습니다... 앞에서 탐색한 것 때문에 뒤에 문자를 더 찾지 못해 한 개를 손해 보더라도 앞에서 탐색한거랑 쌤쌤으로 개수는 똑같을 것 같은데.... 한 개이상 손해볼 수가 있는지 반례를 잘 찾지 못하겠습니다 😭 실제로도 c++ 같은 다른 분들의 풀이를 보니 그냥 첫번째부터 탐색해서 통과하셨더라구요... 채점 방식이 예전과 달라진 것..
-
BOJ 백준 1449 수리공 항승Algorithm/BOJ 2020. 6. 13. 12:00
출처: www.acmicpc.net/problem/1449 분류: 그리디 접근방식 테이프의 좌 우로 0.5를 남겨둬야 한다고 했으니 테이프 길이 - 1 만큼의 구멍은 한 번에 막을 수 있습니다. 구멍을 막을 때마다 테이프의 길이는 줄어들겠죠. 테이프의 길이보다 구멍까지의 간격이 더 크다면 테이프를 새로 끊어야 합니다. 현재 남은 테이프로 남은 구멍을 메꿀 수 있는지 확인하고 아니면 테이프를 새로 끊어줍니다. 다른 분의 접근법을 보고 알았는데요. 더 쉽게 생각하면 현재 구멍의 위치 + 테이프길이-1 만큼까지 커버가 가능하다는 말이 됩니다. 테이프를 새로 끊을 때 현위치 + 테이프길이-1 까지를 커버 가능한 범위라고 생각하면, 다음 위치가 커버 가능한 범위를 벗어나면 테이프를 새로 끊어주면 됩니다. 해결방법..
-
백준 2437 저울Algorithm/BOJ 2020. 6. 13. 01:53
출처: www.acmicpc.net/problem/2437 분류: 그리디 접근방식 쉬워보였으나, 실제로도 방법만 알면 쉬우나, 쉽지 않았던 문제입니다 😭 추들이 주어질 때 측정할 수 없는 최소값을 구하는 문제입니다. 어떤 경우가 되면 더 이상 무게를 구할 수 없다고 판단할 수 있을까요? 추를 오름차순으로 정렬했을 때, 처음 추의 무게가 2라면, 절대 1은 만들 수가 없습니다. 1, 2 다음에 900이 나온다면? 최대로 3까지 만들 수가 있습니다. 1, 2, 3 다음에 900이 나온다면? 최대로 6까지 만들 수가 있습니다. 그렇다면 이제 다시 생각해볼까요? 저희는 직관적으로 알고 있습니다. 1, 2, 3 다음에 900이 나오면, 이미 900은 너무 큰 숫자니 제치고 그 전의 1, 2, 3가지고 최대를 찾아..
-
BOJ 2352 반도체 설계Algorithm/BOJ 2020. 6. 12. 16:10
출처: www.acmicpc.net/problem/2352 분류: Greedy, LIS 접근방식 포트에 선이 서로 꼬이지 않게 연결하려고 할 때 가장 많이 연결할 수 있는 개수를 찾는 문제입니다. 문제의 예처럼 이렇게 연결되어 있을 때, 왼쪽을 A포트 오른쪽을 B포트라고 생각해보겠습니다. A[1] -- B[4] 포트가 연결되어 있다면 왼쪽에서 A[1]을 제외한 나머지 포트들은 모두 1보다 크기 때문에 B에서 4보다 작은 포트들에는 연결할 수가 없습니다. 다시말해 A[i] 포트 --> B[j] 포트로 연결하려고 할 때 현재까지 B에 연결되어있는 포트 중 가장 큰 녀석보다 작은 경우에는 연결할 수가 없게 됩니다. 즉, 이 경우엔 B에 연결해야 하는 포트들 중에서 연속적으로 증가하는 수의 최대 길이가 몇이야?..
-
Binary Search 이진탐색(2) Lower/Upper boundAlgorithm/Theory 2020. 6. 12. 15:07
이진탐색이 정확히 원하는 값을 찾는 거라면, lower/upper bound는 원하는 값보다 처음으로 크거나 작은 값이 나오는 위치를 찾는 방법으로 중복된 요소나 타겟의 상한 하한을 찾는 경우 등 다양한 방식으로 활용될 수 있습니다. 이진 탐색에서 약간의 변형이 들어간 것으로 이진탐색을 이해하셨다면 어렵지 않게 이해할 수 있습니다. 이진탐색이 궁금하다면? --> 여기로 코드를 보기 전에 lower와 upper의 차이를 간략하게 정리해보고 가겠습니다. lower bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾습니다. upper bound는 타겟보다 처음으로 큰 값이 나오는 위치를 찾습니다. [1, 2, 2, 3, 3, 3, 4, 6] LowerBound(3) --> 3 UpperBound(3)..
-
Binary Search 이진탐색Algorithm/Theory 2020. 6. 12. 12:21
이진탐색 - 배열에서 원하는 원소를 찾는 탐색 방법이다. - 이미 정렬이 되어있는 상태에서만 사용할 수 있다. - 반씩 끊어가며 찾는 방법으로 O(logN) 의 시간복잡도를 갖는다. 이진 탐색은 이미 정렬이 되어있는 배열에서 원하는 원소를 효율적으로 찾을 수 있는 알고리즘입니다. 원리는 간단합니다. 이미 정렬이 되어있는 상태이기 때문에 반을 뚝 짤라서 찾는 원소가 왼쪽인지 오른쪽인지 확인해 아닌 부분은 버립니다. 조금 더 살펴보면, 시작 부분을 low, 끝 부분을 high라고 해볼게요. array = [1, 5, 7, 15, 22, 65, 80, 100] 배열이 이런식으로 있고 65를 찾고 싶다면, 시작할 때 low = 0, hight = 6 (array.count-1) 이고 mid = 3 = (0 + ..
-
BOJ1080 행렬Algorithm/BOJ 2020. 6. 11. 17:31
출처: www.acmicpc.net/problem/1080 분류: Greedy 접근방식 두 형렬에서 한 행렬을 한번에 3x3 만큼씩 뒤집는 연산을 통해 같은 행렬을 만들 수 있는 최소 연산횟수를 구하는 문제입니다. 처음엔 dfs로 무식하게 모든 경우를 다 해봤는데 이럴 경우 엄청난 연산 횟수로 역시 시간초과가 납니다. 그리디 문제인 만큼 그리디하게 풀면 생각보다 쉽게 해결할 수 있습니다. 0,0 부터 시작해서 n-3까지 가면서 해당 지점이 타겟 행렬과 다르다면 뒤집어줍니다. 0,0부터 시작하기 때문에 해당 점에서 뒤집지 않으면 결코 같은 행렬을 만들 수 없습니다. 같다면 그냥 통과하면 되는거고 다를 경우 연산 횟수를 카운트하면서 넘어가주면 됩니다. 이때 몇 가지 경우를 더 생각해줘야 하는데 같은 행렬을 ..
-
Permutation 순열Algorithm/Theory 2020. 6. 11. 12:48
안녕하세요. 문제를 풀다가 순열 관련 부분에서 머리가 터져버려(?) 순열에 대해 공부해보고자 합니다. 순열은 순서가 있는 열, 순서를 가지고 줄세우는 경우의 수 라고 생각하시면 됩니다. 1번과 2번의 사람이 있다면 이 둘을 줄세우는 경우의 수는 1, 2 2, 1 이렇게 2가지 경우가 있겠죠. 1, 2, 3 세 명의 사람이라면 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 이렇게 총 6가지 경우가 있습니다. 맨 앞 자리에 올 수 있는 사람의 수는 3 맨 앞자리가 정해졌다면 그 다음에 올 수 있는 사람의 수는 2 그 다음은 1 즉 순열의 경우의 수는 n! 이 됩니다. 여기까지는 많이들 알고계셨던 내용이겠죠? 이제 이를 코드로 구현하려면 어떻게 해야하는지 살펴보겠습니다...