출저 : https://www.acmicpc.net/problem/2579 "DP 쓸 때, dp값과 map에 값을 활용해보자.." 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int N; static int[] dp; static int[] map; public static void main(String[] args) throws IOException{ BufferedReader br = n..
출저 : https://www.acmicpc.net/problem/1149 "DP" 어려웠다. 기초적인 dp문제라고 했는데 왜 이리 어려웠지...ㅎㅎ dp[x] = dp[x-1] + min(x) ; 까지는 생각을 하고, 해답을 봤다. 그리고 최초 dp[0] 가 R,G,B 일 때를 모두 체크하기위해 dp[x][3] 배열을 만들어 해당 dp 값을 이용한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringToken..
출저 : https://www.acmicpc.net/problem/1003 "DP" 12345678910111213141516171819202122232425262728293031323334353637import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int T,N; static int z, o; static int dp[][]; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader b..
출저 : https://www.acmicpc.net/problem/15685 "아이디어가 필요한 구현문제" 삼성 기출 문제. 각 세대를 더해 갈 수록 기존에 찍었던 선들을 모두 왼쪽으로 돌려서 다시 그려준다. 초기에 생각만 잘하면 쉽게 풀릴 문제 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Lis..
출저 : https://www.acmicpc.net/problem/1932 "DP, bottom-up / DP라고 무조건 재귀 생각하지말자." 알고리즘은 삼각형의 맨 밑부분부터 시작해서 dp 갱신을 시작한다. 처음에 재귀로 구현했는데 시간초과가 났다. dp 값을 비교해서 기존 dp 값보다 작으면 탐색하지 못하게 하였는데??? 라고 생각했다. dp 값이 나중에 큰 값으로 갱신된다면, 이전 까지 탐색 경로들은 그냥 지나칠 거임.. 따라서 해당 지점에 가능한 가장 큰 값이 맨 나중에 갱신되는 데이터가 주어졌다면 아마 dp 값 비교를 통한 가지치기는 적용 안될듯. 1234567891011121314151617181920212223242526272829303132333435363738394041424344impo..
출저 : https://www.acmicpc.net/problem/10026 "BFS " Red를 Green 으로 바꾸고 같은 색상 끼리 BFS를 돌려 구역을 구한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182import java.awt.Point;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import ja..
출저 : https://www.acmicpc.net/problem/15684 "브루트포스" 기존에 있는 사다리에 가능한 가로축을 모두 탐색해보는 브루트 포스 문제이다. 그럼 사다리를 배열에 어떻게 표현할까? 풀이에서 배열에 1로 체크된 값은 해당 위치에서 오른쪽으로 사다리가 존재한다고 생각하는 것이다. 따라서 인접한 열에 1 이 있지 않도록 가능한 모든 경우를 체크한다. 이렇게 생각하고 실제 탐색할때는 내 위치와 내 왼쪽 위치를 탐색한다. 1. 내 위치에 1이 있다. 오른쪽 사다리로 가라.2. 내 왼쪽에 1이 있다. 왼쪽 사다리로 가라 위와같이 경우의 수를 만들고 실제로 사다리를 타봐서 체크한다.. 12345678910111213141516171819202122232425262728293031323334..
출저 : https://www.acmicpc.net/problem/15683 "구현, 브루트 포스" 아래와 같이 구현했다. 삼성 기출 문제. 특정 위치에 있는 CCTV가 종류별로 있는데, 이를 4방향으로 돌려가며 사각지대 0의 개수를 최소로 줄이는 경우를 찾는 것이다. 아래 풀이에서는 각 CCTV 마다 한 방향만을 설정해주었는데, 회전 가능한 4방향에 대해서 다 정의해 준다면, 2번 CCTV 는 2회, 5번 CCTV는 1회로 횟수를 더욱 줄일 수 있다. 근데 나는 귀찮아서 그냥 4방향 다 돌렸따.... 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616..
출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn "구현... 다시보자! 꾸에에에엑" 다시보자... 왜 이런 생각을 못했을까. 처음에 그냥 브루트 포스로 전체 경우의 수를 재귀로 다 돌려보았다. 시간 초과. 풀이 참고해서 풀었따. 알고리즘은 아래와 같다. 1. 각 배점을 받을 때마다 최대값을 갱신한다.2. 갱신된 최대값 ~ 0 까지 탐색하며, 만약 이전에 이미 맞았던 점수가 있다면 이 점수에 내가 방금 입력받은 점수를 더해준 값도 체크한다.3. true 로 체크된 값들의 개수를 센다. 12345678910111213141516171819202122232425262728293031..
출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD&categoryId=AV15MeBKAOgCFAYD&categoryType=CODE"이분 탐색 과 double.. 100~200 번만 돌리자." 이분 탐색을 통해 문제를 풀어야 한다. 근데 제한 없이 돌리다 보니 stackoverflow... 아래와 같은 게시물을 봄... 결론만 말하자면 double형을 가지고 이분 탐색을 할 경우 100~200 번 까지만 돌리도록 한다는 것이다. (https://www.acmicpc.net/blog/view/37) 1234567891011121314151617181920212223242526272..
- Total
- Today
- Yesterday