Problem Solving 썸네일형 리스트형 BOJ 2696 - 중앙값 구하기 문제 링크https://www.acmicpc.net/problem/2696 문제 해결 1. 중앙 값을 구하기 위해서 우선 순위 큐(Priority Queue) 2개를 사용한다. 2. 중앙 값을 변수 val에 저장한다. 그리고 val과 새로 주어진 값의 크기를 비교한다. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 9177 - 단어 섞기 문제 링크https://www.acmicpc.net/problem/9177 문제 해결 1. DP 문제. DP[i][j] = 처음 문자열의 i 인덱스까지와 두 번째 문자열의 j 인덱스까지 섞어서 만든 문자열이 비교할 문자열과 일치하는 가에 대한 값 저장. 주의할 점 || 생각해볼 점 1. 비교할 문자열의 처음부터 차례대로 비교하면 될 것이라고 생각하기 쉽다. 하지만 만약 처음 문자열과 두 번째 문자열이 같은 문자를 가진다면 어느 것을 골라야할 지 명확해지지 않는다. 그러므로 DP를 사용해서 문제를 해결해야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 9370 - 미확인 도착지 문제 링크https://www.acmicpc.net/problem/9370 문제 해결 1. 최단 거리를 구하는 문제. 2. 시작점과 도착점이 될 수 있는 후보 점들이 주어진다. 도착점이 되기 위해선, 반드시 g와 h 사이의 간선을 지나야한다. 3. dist1[i] = 시작점으로부터 모든 점까지의 최단 거리. dist2[i] = dist1[g]와 dist1[h] 중 가까운 점 g 또는 h로부터 모든 점까지의 최단 거리 4. 도착점이 될 수 있는 점 t가 있을 때, dist1[t] == dist1[min(dist1[g],dist1[h])인 점] + dist2[t] 이 되는 t를 오름차순으로 출력 주의할 점 || 생각해볼 점 1. testcase마다 graph를 초기화시키는 과정에서 실수가 있었다. 항상 조심.. 더보기 BOJ 2787 - 흔한 수열 문제 문제 링크https://www.acmicpc.net/problem/2787 문제 해결 1. 수열을 복원하기 전, chk[i][j] = i번 째 자리에 숫자 j가 위치할 지에 대한 check. 1이면 j가 i번 째에 있을 수 없음을 나타낸다. 2. 들어갈 수 있는 수들을 vector에 넣고 이분 매칭을 통해서 최대 매칭 수를 구한다. 3. 매칭 수가 N과 같다면 매칭된 수열을 출력. 그렇지 않다면 -1을 출력한다. 주의할 점 || 생각해볼 점 1. 이분 매칭을 통해서 문제를 해결할 수 있음을 알 수 있었다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 11568 - 민균이의 계략 문제 링크https://www.acmicpc.net/problem/11568 문제 해결 1. 전형적인 LIS 문제 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 codeground practice - 최소 신장 트리 문제 링크로그인을 해야만 볼 수 있다. 문제 해결 1. 신장 트리를 만들되, 선택된 간선들의 중간 값이 가장 최소가 되는 신장 트리를 만들어야한다. 말이 복잡하지만 결국은 MST를 구하는 문제다. 왜냐면 간선들의 중간 값은 가중치가 작은 간선들이 많을 수록 작아지기 때문이다. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1102 - 발전소 문제 링크https://www.acmicpc.net/problem/1102 문제 해결 1. bitmask DP 를 이용해서 문제 해결. dp[i] = i는 켜져있는 공장들과의 or 연산값 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 14497 - 주난의 난(難) 문제 링크https://www.acmicpc.net/problem/14497 문제 해결 1. flood fill 문제다. ① 시작점을 origin_queue에 넣는다. 그 다음 temp_queue를 하나 만든다.② '1' 이라면 temp_queue에 넣고, 아니라면 origin_queue에 넣는다.③ origin_queue가 비면 temp_queue를 origin_queue로 바꾸고 count++. ④ 끝 점과 만나면 끝낸다. 주의할 점 || 생각해볼 점 1. 시간 복잡도는 참고 - bfs를 이용한 flood fill 구현 : https://www.quora.com/How-do-I-implement-flood-fill-using-BFS-Would-the-algorithm-be-faster ※ 정확하고 부.. 더보기 BOJ 14502 - 연구소 문제 링크https://www.acmicpc.net/problem/14502 문제 해결 1. DFS를 이용해서 문제 해결. 0과 2의 row, column 인덱스를 저장하고 3중 for문을 활용해서 문제 해결. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1166 - 선물 문제 링크https://www.acmicpc.net/problem/1166 문제 해결 1. 기본적인 파라메트릭 서치를 이용한 문제다. 주의할 점 || 생각해볼 점 1. solve 함수를 구현할 때, 무작정 주어진 L, W, H를 곱해서 해결하면 안된다. 각 변수 당 최대 이기 때문이다. 2. while(right-left>1e-10) 를 사용하는 것에 조심하자. 경우에 따라선 right-left가 항상 1e-10일 수 있다. 3. 16 byte를 표현할 수 있는 long double 을 사용했다. 이번 문제에선 8 byte를 표현할 수 있는 double을 사용하지 않는다. 참고 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 2 3 4 5 6 7 ··· 9 다음
