공부공간

www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각�� www.acmicpc.net 직원그룹과 해야할일그룹 두 그룹간에 매칭을 시켜주는 전형적인 이분매칭 문제이다. 1 ) 현재를 이을것인지? 2 ) 이어진 현재를 바꿔서 나를 이을것인지? 의 두가지를 구현하면되는데, 재귀함수로 구현할 수 있다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.ut..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 미로의 방문체크를 N^2 으로하면서 최단경로를 Deque로 계산한다. package algorithm; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.StringTokenizer; public class 미로만들기 { public static void m..

https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해� www.acmicpc.net 각 소가 원하는 축사가 존재한다 ( 존재하지 않을수도 있음 ) 일단은 배정후 변경하는 이분매칭알고리즘을 사용하자. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; class Main { public static int m,..

https://www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net 이분 매칭의경우 네트워크플로우에서 최대유량이 1인간선으로 이루어진 네트워크중 A/B집합 두개로 나뉘어서 최대유량을 구하는 문제이다. 하지만 에드몬드카프로 구현하기보다는 DFS를 활용하여, 앞선 매칭을 바꿀수있는지? 에대한 재귀함수를 정의한다. 이해가 안되면 아래 강의를 추천한다. 뭔가 이분매칭의경우, "두 집합간 최대한 매칭을 시킨다" 라는 느낌이 온다. https://blog.naver.co..

https://www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위� www.acmicpc.net 주말동안의 PS주제는 포드-풀커슨알고리즘과 이분 매칭이였다. https://coderkoo.tistory.com/4 네트워크플로우(Network flow) - 포드 풀커슨(Ford-Fulkerson) 알고리즘 네트워크 플로우란(Network flow)? 그래프의 경로의 길이가 아닌, ‘용량’의 관점에서 바라보는 시점. Ex) 인터넷으로 영화를 다운받고 있는데 파일 원격지에서 얼마나..

싸피에서 PS와 개인블로그를 꾸준하게 한결과 플레기로 승급하였다. 하지만 플래티넘문제를 막 풀수있는건 절대아니다.. 작년 10월즘에 NLP교육과정에서 알고리즘을 처음시작했었는데.. 벌써 1년이지났다 당분간 PS판을 떠나 자소서에 올인하는걸루..ㅎㅎ

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 세용액의 합이 0 이 가까운 것은 고르기 위해서, 정렬후 앞쪽부터 O(n)만큼 순차탐색을 하도록하자. 세개의 포인터를 사용해야하기때문에, 하나는 고정시키고 두개를돌려주자 5000^2으로 충분하다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java...

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 모든점에서 나타날수있는 경우(대칭,회전)의 경우의수를 확인해주고 최댓값을 구하면된다. 시간복잡도 20*500*500으로 충분하다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 테트로미노 { public static int map[][],n,m..