공부(2018~2019) - 스킨변경전

1. 1766번 문제집우선순위 큐를 이용한 위상정렬 문제가중치와 정점으로 정렬을 하려고 했는데 생각해보니 정점으로만 위상정렬을 하면되는 간단한 문제였다.선수과목이 있는데 가나다 순으로 과목을 이수하라는 의미와 같다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java...

1. 15683번 감시삼성 코딩테스트 문제, DFS + 백트레킹을 사용하여 구현했다.어렵다기 보다는 복잡한게 많다. 복붙으로 만들어 중간 중간에 고쳐주질 않으니까 틀리는 부분이 많았다.그리고 실수했는데도 어떻게 또 맞아들어가서 기본 테스트케이스가 통과해버리니까 찾는데 너무 오래 걸렸던거 같다.주의할점은 2차원 배열은 그냥 클론해서 사용하면 주소값을 참조하는 것과 다른 없어지는 부분 조심해야 할 것 같다.CCTV의 좌표를 저장하고 dfs로 모든 경우의 수를 체크하여 풀었다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707..

1. 14889번 스타트와 링크DFS와 백트래킹 문제 , 문제를 이해하는 것이 중요한 것 같다. 13 34 41 하면 같은 팀이 되는 줄 알았는데 그게 아니라 전부 다 해주어야 했다. 백트래킹은 반복문 밖에서 설정 해주어야 한다는 것을 기억하자..123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100import java.io.BufferedReader;import java.io.IOException;import java..

1. 13458번 시험감독문제에 대한 이해를 잘했는지에 대한 문제인 것 같다.무조건 int형으로 하려고 하지말고 long형에 대한 부분도 생각을 해야 할 것 같다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static long count = 0; public static void main(String[] args) throws N..

1. 3745번 오름세배열이 주어지면 그 배열의 증가하는 부분 수열의 길이를 구하는 문제O(N^2)에 경우는 쉽게 이해했지만 N log(N) 푸는것은 쉽지 않았다.이 알고리즘은 LIS(Longest increasing subsequence) 이다.주어진 input 값이 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181..

1. 1764번 듣보잡문자열 문제, 푸는 방법이 여러개가 있을 것 같았다. 처음에 단순히 모두 비교를 했는데 시간초과가 나왔다.500000가 모두 4999900까지 같고 뒤에만 다르면 500000*500000을 해야되는데 처음부터 문제를 정독하는 것이 중요한 것 같다.바이너리서치를 생각하지 못한 것은 아직 많이 부족하다는 걸 다시 느끼게 되었다.이 문제는 Map을 활용할 수 있는지에 대한 것이라고 생각된다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889..

1. 3986번 좋은 단어Stack 기본문제, 문제를 이해하지 못해서 상당히 시간이 걸렸다. 처음에 단순히 영역 구하는 문제인 줄 알고 DFS로 접근했다.번외로 테스트케이스가 하나밖에 없어서 몰랐는데 단어길이가 제 각각이었고 그러다 보니 Array 예외가 자꾸 발생했다.제각각인 라인을 잡을때는 배열과 Input을 따로 두는 것이 좋을 것 같다.본론으로 돌아와서 이 문제는 문자열이 주어지고 문자를 지워나가는 문제이다. ABBA -> BB를 지우고 AA를 지운다 이 표현을 단어위로 묶은다는 표현을 해서 이해가 안됬던 것 같다. 알고리즘에서 기본적으로 문제 이해 가장 중요한 것 같다.Stack을 이용해서 넣고 지우고를 반복해서 비어있으면 좋은단어 아니면 아닌단어로 풀이하였다.1234567891011121314..

1. 10988번 팰린드롬인지 확인하기간단한 배열문제123456789101112131415161718192021import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); int len = input.length()/2; for(int i ..

1. 15685번 드래곤커브상반기 삼성전자 오후에 봤었던 문제이다. 당시에 손도 못댔고 지금도 접근법이 감이 안잡혀서 힌트를 보고 풀었다.드래곤커브에 규칙이 있는데 방향을 누적하여 이전 세대까지 누적된 거에 역순으로 +1 씩 해주면 그 다음세대의 방향을 알 수 있었다.처음에 점에 대한 규칙으로만 하려고 하니 점에 대한 규칙이 너무 복잡하고 계속 늘어나기 때문에 할 수가 없었다.시뮬레이션으로 분류된 문제인데 이런 류의 문제는 여러 부분에 대한 규칙을 따져보아야 하는 것 같다.특히 이렇게 누적되는 문제는 하나를 기준으로 하는 게 좋을 것 같다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051..

1. 1149번 RGB거리DP문제 문제별 0.5초 밖에 주지 않는 것을 보고 DP로 풀어야한다는 것을 알았는데 생각보다 식세우기가 쉽지 않은 문제DP를 어느정도 파악했다고 생각했는데 DP 생각보다 더 다양한 것 같다. 그동안 푼 문제들은 bottom up 이나 top down 방식으로 풀었는데 이거는 임의의 기준점을 세워서 푸는 문제라 생각된다.힌트를 보고도 못푼 이유가 맨처음집에서 R을 선택 , G를 선택, B를 선택 하는 경우로 접근하려고 했는데 이 경우는 맨처음집에서 R을 선택해서 그리디하게 식을 만들어 보았다.dp[i+1][0] = Math.min(arr[i][1], arr[i][2]) + dp[i-1][0]; 문제점은 i-1번째가 기준이 되기 때문에 dp[0]에 들어가는 것이 중복될 수 있다.i..

1. 5719번 거의 최단경로최단경로가 아닌 경로들만 사용해서 최단경로를 만드는 문제처음에 단순하게 다익스트라로 최단경로를 구하고 그 경로만 사용하지 못하게 해서 다시 다익스트라를 돌리면 될 것 같았다.문제는 최단경로가 여러개 있을 때 중복경로가 존재 할 수 있다. 1->2 -> 4 ->5 일때 1 -> 2 -> 3 ->5 이렇게 최단경로가 될 수도 있다75프로에서 틀리는데 수정이 필요하고 코드도 다익스트라를 너무 부르는 것 같아서 수정이 필요하다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677..

1. 1507번 궁금한 민호플로이드 워셜 알고리즘을 반대로 이용하는 문제이미 최단경로가 주어져 있고 이를 이용해서 도로를 구하려면 반대로 거쳐가는 경로를 없애주면 된다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static boolean visited[]; public static void main(String[] args) ..