https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 풀이입니다. 우선 문제를 보면 무식한 방식으로 풀어도 될거같다는 느낌이 옵니다. 제한사항을 보면 문자열 길이가 1000이하로 주어졌는데, 반복가능한 문자열 단위는 최대 500입니다. 그 이유는 전체 문자열 길이의 절반을 넘어가면 반복되는 문자열을 통한 압축이 불가능해지기 때문입니다 ex: aaaabb >> 길이 단위를 4로 해도 2aaaa 이런식으로 압축이 불가능합니다. 길이가 ..
https://school.programmers.co.kr/learn/courses/30/lessons/72412 위의 문제에 대한 해설입니다. input으로 들어오는 2개의 vector 에서 각 벡터 안 1개의 string들은 총 5가지 유효한 string 정보를 가지고 있다. parser를 통해 유효한 5개의 string의 string을 추출한 뒤, 마지막에 위치한 점수에 대한 부분은 stoi() 함수를 통해 숫자로 바꾼다. map 자료구조를 통해 앞선 4개의 string들을 하나로 묶어 key 값으로써 사용하고, stoi()를 통해 정수형으로 바꾼 점수 정보를 value로써 추가한다. 이때 고려할 사항은 query에서는 '-' 라는 문자열이 특수성을 가진다는 것이다. '-'는 어떤 것이 와도 상관없..
분리집합 응용문제를 하나 들고 왔습니다. 분리집합에 관한 기본적인 지식은 생략하고 해당 문제의 핵심 아이디어만 아래 코드블럭의 주석에 구체적이게 달아 놓았으니 참고하세요! #include using namespace std; #include int n, m,cnt; int arr[1000000]; int find(int a) { if (arr[a] == a) return a; else return arr[a] = find(arr[a]); } void join(int a, int b) { a = find(a); b = find(b); if (a == b)return; arr[a] = b; //두번째 파라미터가 첫번째 파라미터의 부모가 된다. } int main() { scanf("%d %d", &n, &m..
lis는 10, 20, 10, 30, 20, 50 이런 길이 5의 수열중 10, 20 ,30 ,50 과 같이 계속해서 증가하는 수열들 중, 가장 긴 수열을 찾는 문제다. 우선 lcs는 푸는 방식이 정말 다양한데, 전부 시간 복잡도가 다르다. dp를 통해서 풀게되면 O(N^2) 이고, lower_bound를 통해서 풀게 되면 O(NlogN) 의 시간 복잡도가 발생한다. lis 문제는 시간초과를 가지고 장난을 많이 치기에 lower_bound 방식만 가지고 문제를 풀어보겠다. 자세한건 아래 문제를 보면서 알아보자..! 1.lis 의 길이는? lis의 길이를 구하는 문제로, 위 의 입력의 경우 10,20,30,50 이기에 4가 정답입니다. 흔히 전깃줄 문제로 응용 됩니다. 자세한 건 아래 문제를 확인 해봅시다..
knapsack은 "제한된 자원" 으로 "최적(최대 or 최소) 의 이득" 을 얻는 문제에서 사용된다. 아래는 대표적인 예시 중 하나다. n개의 보석이있다. 이중 1~ n번째 보석중 k 번째 보석의 무게를 w_k, 가격을 c_k 라고 정의한다. 내가 가방에 최대로 담을 수 있는 무게가 w_max일때, 내가 담을 수 있는 최대 가치는? 대충 이런 느낌이지만, knapsack도 상황에 따라 다양한 방식으로 나눠져 있으므로 지금부터 같이 하나하나 알아보자! 1) fractional knapsack - 보석을 쪼개서 가방에 담을 수 있다. >> 그냥 무게당 가치가 높은것들을 우선적으로 가방에 담으면 끝이다. 예를들어 무게3에 가치 9, 무게 2에 가치 4 무게 1에 가치 1인 보석이있다고하면 1번의 무게 1당 ..
우선 백준 1005번을 보고 오자. https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 이 문제에 대한 올바른 문제해결 방법은 '위상정렬' 이다. 위상정렬은 보통 어떤 작업에 순서가 정해져있을 때, 순서를 결정하기 위해 사용하는 알고리즘입니다. 예를들어 스타크래프트에서 어떤 상위 건물을 지으려면, 하위 건물들을 몇가지 지어야 하는 경우가 있는데, 이처럼 어떤 작업 진행전에 해야하는 '순서' 가 존재할시 위상정렬을 사용한다. 위상정렬을 사용하기..
경로를 탐색해나가는 것에 더 나아가, 경로를 저장한 후 출력하라는 문제들이 종종 있다. 오늘은 어떤 경우에, 어떤식으로 경로를 저장해나가는지 케이스 별로 알아보자 1. 다익스트라,벨만포드 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 문제 11779 번을 풀어보며 알아보자. 이 문제는 다익스트라 문제이지만, 벨만포드도 "경로 추적" 은 동일한 메커니즘으로 돌아간다. 혹시 벨만포드로 된 문제를 풀고 싶다면 ..
이 문제가 삼성 코테에 기출 되어서 풀어봤는데, 여러가지 알고리즘이 한 문제에 누적 되어 있어, 풀어보면 좋을 것 같아 자잘한 설명과 함께 코드를 공유하려합니다! 코드에 대한 설명은 주석으로 상세하게 적어놨습니다~ 문제를 처음보면, 딱 "그룹" 이라는 단어가 떠오르면서 자연스럽게 mst(최소 스패닝 트리) 에 관한 문제인 것을 캐치하고 풀어 나갔다. MST에 대해 잘 모른다면, 아래의 글을 참고하자. https://codenme.tistory.com/manage/posts/ Tistory 좀 아는 블로거들의 유용한 이야기 www.tistory.com 문제는 크게 3파트로 나눌 수 있는데 1) 각 섬에 번호를 붙여 저장하기 (섬간의 구분을 위해) 이건 bfs를 통해 구현했다.. 2)섬간의 거리를 구한다. ..
