728x90 백준플래38 백준 1044, 팀 선발 개요 문제 링크 플래 3, Bruteforce, Meet in the middle, Bitmasking 위 아래 선택을 절반씩 한 것들의 점수합의 차이가 최소가 되도록 하기 접근 SSP의 Meet in the middle을 쓰는 네 번째 문제, 중간에서 만나기로 머리를 부숴놓는 문제다. 꽤 많이 까다롭고 고민할게 많으니 우선 중간에서 만나기가 무엇인지 SSP 글에서 꼭 숙지하고 읽어보기를 바란다. 우선 브루트포스 방식을 생각해보자. 비트마스킹을 어디에 쓰냐? 하면 두개의 행벡터에서 위를 선택하는 경우 0, 아래를 선택하는 경우를 1이라고 하면 하나의 선택을 36자리 비트로 나타낼 수 있다. 그럼 절반만 아래를 선택해야 하므로 1이 18개인 모든 경우에 대해 따져보면 된다. 엥? next permutati.. 2023. 4. 5. 백준 2727, 2,3 거듭제곱의 합 개요 문제 링크 플래 4, Greedy N을 약수/배수의 관계가 아닌 2,3의 거듭제곱의 합으로 표현하기 접근 그리디, 백트래킹을 잘 활용하면 되는 문제, 만약 재귀함수 내에서 for문을 두 개 쓰고 있다면 하나로 줄일 방법을 잘 생각하면 되고 그게 그리디한 요소가 된다. 문제 검색은 최후의 상황이 아니면 잘 안하는데 많이 답답해서 블로그를 참조했다. 들어가자마자 결합법칙이라는 단어를 보고 아 이거였구나 싶었다. 떠올리기 어렵긴 하지만 좀 더 고민해볼 걸 싶었다. 핵심은 이렇다. 문제를 풀다보면, 약수/배수 관계를 만들지 않기 위해 어떤 두 (a,b)쌍에 대해 a1 2023. 3. 18. 백준 2873, 롤러코스터 개요 문제 링크 플래 3, Greedy 경로의 이득의 총합이 최대가 되도록 경로를 구성해 출력하기 접근 이게 왜 그리디일까 싶은 느낌이 드는데 천천히 이해하다보면 충분히 그리디함을 알 수 있다. 우선 모든 점의 값이 양수이니 최대한 많은 점을 훑는게 이득이다. 홀수×홀수나 홀수×짝수 형태의 맵에서는 모든 점을 돌아볼 수 있다. 그래서 여기까지는 쉽다. 만약 가로가 홀수라면 세로로, 세로가 홀수라면 가로로 지그재그로 움직여줘야 모든 점을 돌 수 있다. 이 부분만 재귀적으로 잘 구현해주면 크게 어렵지 않다. 문제는 짝수 × 짝수 인 경우인데, 이때는 최솟값이 있는 점을 거르고 탐색하는 것이 가장 이득이다. 점을 하나만 걸러도 나머지 모든 점을 지날 수 있기 때문인데, 질문게시판의 수많은 질문들에서도 다루듯이.. 2023. 3. 17. 백준 10803, 정사각형 만들기 개요 문제 링크 플래 3, Greedy, DP N×M크기의 직사각형을 최소 개수의 정사각형으로 나누기 접근 내 하루를 앗아간 그리디 & 메모이제이션 DP문제, 사실 접근은 분할정복에 더 가까운 것 같다. 증명 시도했는데 처참히 털렸다. 시간날 때마다 도전해보고 성공하면 수정하려고 한다. 어디가 그리디인가? 싶을 수 있는데 N이 10000이니까 N^2을 돌리지 않게 하기 위해 그리디를 사용한다. 처음에는 N,M루프를 돌면서 왼쪽 위 정사각형을 하나 만들고 남은 L자 모양의 구간을 두 가지 방법으로 잘라서 최솟값을 구하는 방식으로 진행했다. 그런데 이 방법은 최선이 아니다. L자 모양을 두개의 직사각형으로 자르지 않는 것이 최선이 될 수 있는데, 아래 예시를 보자. N=72, M=35이다. 왼쪽 위 15만큼.. 2023. 3. 17. 백준 1348, 주차장 개요 문제 링크 플래 2, Graph, Bipartite matching, BFS 모든 C가 P로 이동하기 위한 최소 시간 구하기 접근 특이한 이분매칭 문제. 이분매칭을 모른다면 꼭 숙지한 다음 문제를 접근하길 바란다. 안그러면 시작을 할 수 없다. 태그에 이분탐색이 있는데 어떻게 쓰느냐 하면 시간에 대해 쓴다. 시간의 기준은 모든 차의 주차가 되느냐? 하는 것이다. 왜냐? 시간이 0일때를 생각하면 모든 차가 주차가 안된다. 시간이 한 100만쯤 되면 모든 차를 주차할 수 있다. 시간을 계속 늘려가면서 뇌뮬레이션을 돌려보자. 계속 주차가 안되다가 어느 시점부터는 계속 된다. 이 변화하는 지점을 찾아보자는 것이다. 시간을 함수의 입력으로 넣자니 너무 번거롭다. 복잡하게 하지 말고 전역변수로 때려버리자. 이.. 2023. 3. 15. 백준 14398, 피타고라스 수 개요 문제 링크 플래 3, Graph, Bipartite matching, 정수론 서로소인 두 수를 직각삼각형의 빗변이 아닌 두 변이 되도록 짝 지을 때, 가장 많은 짝의 수 구하기 접근 재미진 이분매칭 문제. 이런 새로운 알고리즘은 한 번 배우면 응용이 무궁무진해서 티어올리기 좋다 재미를 더해준다. 이분매칭을 모른다면 꼭 공부하자. 내용을 모르면 시작을 할 수가 없고 브루트포스를 돌려서 200!번의 연산을 하는 수밖에 없다. 소수 쌍 문제와 유사한데, 비슷하게 이분과 매칭에 대해 생각해보자. 이분을 어떻게 해줘야 할까? 이 문제는 엄청 특이하게 현재 집합을 두개로 쪼개지 않고, 복사해버리면 된다. 연결 조건은? 우선 서로소이고, 두 수의 제곱의 합이 어떤 자연수의 제곱이 되면 된다. 즉 sqrt(a×a.. 2023. 3. 15. 백준 1017, 소수 쌍 개요 문제 링크 플래 3, Graph, Bipartite matching, 정수론 모든 두 수를 짝지어 소수를 만들 때, 첫 수와 짝지어지는 수 출력하기 접근 유서깊은 이분매칭 문제. 대체 이게 어떻게 이분매칭일까 싶은데 하나하나 뜯어보면 소름돋는 이분매칭 문제이다. 이분매칭을 모른다면 꼭 무슨 내용인지를 알고 접근하는 것이 좋다. 아니면 시작을 할 수가 없다. 이분이 되는 이유는? 짝수와 홀수를 이분해주면 된다. 매칭이 되는 이유는? 둘을 매칭시켜야 하는데 만약 짝-짝, 홀-홀 매칭이면 그 합이 짝수이기 때문에 소수가 될 수 없다. 따라서 이분, 매칭에서 짝,홀로 이분하고 각각을 매칭해주는 것이 이 문제의 핵심이 된다. 그럼 우선 이분을 해주자. 개인적으로 이걸 구현하는게 제일 헷갈렸다. 처음 들어온 .. 2023. 3. 15. 백준 14433, 한조 대기 중 개요 문제 링크 플래 4, Graph, Bipartite matching 최대한 많은 사람이 트롤픽을 하도록 N명의 사람이 M개의 트롤픽을 할 때 두 팀의 트롤픽 비교하기 접근 이분매칭 을 사용하는 문제. 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. 문제 지문이 길고 복잡해서 이해가 살짝 어려울 수 있는데, 일단 두 팀은 최대로 많은 트롤픽이 나오도록 선택을 하므로 둘 다 최대 유량을 구하는 문제임은 맞다. 그럼 다음은 트롤픽 개수를 비교하는 것인데, 동점이면 안되니까 무조건 첫 팀의 트롤픽이 적어야 한다. N개의 사람 그룹과, M개의 트롤픽 그룹이 있고, 그래프의 모든 연결관계는 사람과 트롤픽을 연결하므로 이분 그래프의 .. 2023. 3. 15. 백준 2191, 들쥐의 탈출 개요 문제 링크 플래 4, Graph, Bipartite matching N마리의 쥐가 M개의 굴에 들어갈 때 시간 내에 들어갈 수 있는 최대 쥐 수 구하기 접근 이분매칭 을 사용하는 문제. 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. 이게 이분매칭인 걸 모르면 좀 많이 답답할만한 문제인데, 핵심은 모든 쥐마다 각자 들어갈 수 있는 구멍을 미리 구해놓는 것이다. 이러면 갑자기 이분매칭 문제로 변한다. 들어갈 수 있는 조건은? 거리가 S×V보다 작으면 된다. N개의 쥐 그룹과, M개의 구멍 그룹이 있고, 그래프의 모든 연결관계는 구멍과 쥐를 연결하므로 이분 그래프의 매칭 문제가 된다. 나머지는 이분매칭을 잘 이해하고 있다면 .. 2023. 3. 15. 백준 17481, 최애 정하기 개요 문제 링크 플래 4, Graph, Bipartite matching N명의 사람이 M명의 최애가 있을 때 최대한 많은 사람이 최애를 선택하게 만들기 접근 이분매칭 을 사용하는 살짝 씹덕틱한 문제. 다른 이분매칭 문제와 마찬가지로 이분매칭을 모르고 있다면 아예 시작을 못하는 문제니까 꼭 개념을 알고 문제에 접근하기 바란다. N개의 사람 그룹과, M개의 최애 그룹이 있고, 그래프의 모든 연결관계는 최애와 사람을 연결하므로 이분 그래프의 매칭 문제가 된다. 엥 그런데 이분매칭은 정수로 하는거 아님? 이럴 때는 고민말고 C++의 미친장점, map을 쓰면 된다. map에는 각 이름의 맞는 index를 저장해둔다. 나머지는 이분매칭을 잘 이해하고 있다면 크게 어렵지 않다. 원하는 최애 중 아직 아무도 선택 안.. 2023. 3. 15. 다음 728x90
