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

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) ..

1. 5567번 결혼식처음 접근을 find로 했는데 문제는 들어올때마다 부모 노드가 바뀔 수 있다는 것을 간과 했던것 같다BFS로 처리하고 싸이클이 발생할 경우 무한루프가 발생하는 부분만 처리했다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869public class Main { static int count = 0;/* * 4-10 7-10 3-7 6-8 1-7 1-6 1-5 1-9 2-4 3-8 * 7 6 5 9 * 3 8 10 */ static ArrayList[] aLists; static Queue queue = n..

1. 1068번 트리트리의 단말노드를 찾는 문제트리문제를 접근할때 한쪽에만 자식들이 달려있는 경우를 생각해야 될 것 같다.이진트리인줄 알고 접근했다가 꽤 시간이 걸린문제 이진트리라고 명시가 안되있는 경우 자식이 꼭 2개까지만 있는 경우는 없다.노드가 삭제될때 상위노드의 자식이 하나 뿐이였다면 부모가 단말노드가 된다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374import java.io.BufferedReader;import java.io.IOException;import java.io.InputStrea..