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

1. 16988번 Baaaaaaaaaduk2[Easy](BJO)백트래킹 문제바둑돌을 둘때 여러 방이 생기는 경우에 대한 처리만 조심하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192import java.util.Scanner; public class Main { static int n; static int m; static int[][] board; public static void main(String[] args) { Scanne..

1. 16987번 계란으로 계란치기(BJO)백트래킹 문제이문제는 기본 백트래킹 문제지만 꼼꼼한 처리가 필요했다.이미 쥔 달걀이 깨진 경우에 return을 안걸어서 문제가 잇었고 또 이미 다 깨진 경우에 대한 처리를 안해서 92 퍼센트에서 계속 틀렸다.처리해야 될 부분을 따로 적어놓고 확실하게 처리해주어야 겠다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.util.Scanner; public class Main { static int n; static int[] dur; static int[] wei; public static v..

1. 16986번 인싸들의 가위바위보(BJO)시뮬레이션, 완전탐색문제이 문제는 살짝 설명이 부족하여 이유를 찾느라 오래 걸렸다. 지우가 모든 경우를 다내지 않아도 이기면 끝, 명희&민호도 각라운드로 내는것이 아닌 자기차례에 안쓴 것을 낸다.위의 두가지 때문에 테케에서 자꾸 틀리는 일이 발생했다 ...이런 유형의 문제는 어렵진 않지만 문제이해, 규칙 찾는것이 중요하고 시간도 중요하다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596..

1. 16985번 Maaaaaaaaaze(BJO)BFS, 완전탐색 문제항상 2차원만 풀다가 3차원의 완전탐색을 하려니까 상당히 어렵게 느껴졌다.특히 각판의 회전에 대한 완전탐색을 어떻게 접근해야 할지 감이 잡히질 않았다. 이 문제에 대한 블로그 강의를 보면서 풀었는데 풀면서 느낀 점은 하나하나 기능을 분할하면 쉬운 문제인 것 같았다. 4차원 배열은 어떤 문제에 사용될까 궁금 했었는데 이 문제를 통해 확실하게 쓰는 방법, 어디에 쓰이는지 배웠다.또 강의에서 4^5 가지 경우를 4진법을 이용해서 풀었는데 이부분은 다른 곳에서도 자주 쓸수 있을것 같다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849..

1. 배열의 회전 정리123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293 public class Test { static int[][] arr; public static void main(String[] args) { arr = new int[][]{{1,2,3},{4,5,6},{7,8,9}}; int temp[][] = new int[3][3]; for(int i = 0; i (1,0) (0,2) -> (2,0) (0,3) -> (3,0) ..

1. 입국심사(SWExpert)이분탐색 문제이문제를 딱 봤을때 이분탐색 문제일 것이라고 전혀 생각을 못했다. 그리고 N과 M의 크기가 너무커서 완전탐색을 할수가 없었다.N과 M의 크기로 힌트를 얻었어야 했는데 아무리 생각해도 어떻게 풀어야 하는지 감이 잡히질 않았다. 내 생각이 DFS, BFS, 완전탐색에만 머물러 있다는 것을 느낀 문제였고 다각도로 접근할 수 있는 시야를 키워야 겠다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455import java.util.Scanner; public class Solution { static long[] rooms; static lo..

1. K번째 접미어(SWExpert)정렬 문제123456789101112131415161718192021222324252627282930313233import java.util.Collections;import java.util.LinkedList;import java.util.List;import java.util.Scanner;import java.util.stream.Collectors; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); /****************************** * sort를 이용해서 n번째 단어를 찾는다. ****************..

1. 14888번 연산자 끼워넣기(BJO)완전 탐색 문제다른방법이 있을까 생각해봤지만 전형적인 완전탐색 문제다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859import java.util.Scanner; public class Main { static int[] oper; static int[] nums; public static void main(String[] args) { /****************************** * 완전탐색을 이용해서 모든 경우를 * 계산하여 최대값 최소값을 찾는다. *****************************..

1. 16234번 인구이동(BJO)DFS 활용문제2018년 하반기 삼성 코테에 나왔던 문제 유형이다. 그때도 테케까지 풀긴했지만 뒤에서 시간초과가 생겼을것이라 생각한다.DFS와 비트연산을 이용해 풀었는데 생각보다 속도가 느리다. 시간초과는 나지 않았지만 속도를 줄일 방법을 찾아봐야겠다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151..

1. 빠른 휴대전화 키패드 (SWExpert)문제해결능력 문제이 문제를 당연히 완전탐색이라고 생각하고 풀다가 시간초과가 발생했다. 그래서 안들어가는 자리만 판단했는데도 시간초과가 발생했다 1이상 1000 이하의 S 즉 최대 4^1000 경우의 수가 발생한다.(미리 처리해도 무조건 시간 초과가 발생)이걸 생각하지 않고 풀었던 것이 화근이었다. 그에 비해 단어는 1000개에 1000000이하 반대로 찾아가는 것이 더 빠르게 구할 수 있다.알고리즘은 당연히라는 것은 없고 확신이 필요하다는 것을 다시 느꼈다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162..

1. 아기상어(BJO)BFS와 시뮬레이션 문제문제에 조건을 명확하게 파악을 못해서 오래 걸린 문제처음에는 상좌로 탐색해 먹을 수 있는 물고기를 발견한 순간에 바로 먹고 BFS를 종료시키는 방법으로 구현했다.하지만 그렇게 할 경우 큐에 담겨 있을 수 있는 다른 최단거리의 물고기들을 판별할 수가 없었다.그래서 리스트를 만들어서 모든 먹을 수 있는 물고기들을 담고 Sort해서 가장 위에 왼쪽에 있는 물고기를 먹게 만들었다.하지만 이렇게 만들 경우 먼저 탐색한 것이 거리가 더 긴데도 가장 위에 왼쪽에 있어 먹는 경우가 발생했다.그래서 마지막으로 거리정보를 각각 객체에 담아서 거리를 최우선으로 정렬하고 다른 조건들에 대해 정렬해서 구현을 했다.이문제의 핵심은 가장 위에, 왼쪽이 x값이 제일 작고 같으면 y값이 제..

1. 동철이의 일분배(SWExpert)DFS 탐색 문제처음에 모든 경우를 탐색했을때는 시간초과가 발생해서 max값이 될 수 없는 (곱하면 작아지는 확률) 것은 탐색하지 않으니 통과했다.또 6자리 뒤에 0이 안붙으면 fail이 나서 소수점 여섯자리를 다 표시해 주어야 한다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.util.Arrays;import java.util.Scanner;import java.util.stream.Stream; public class Solution { public static boolean[] visited; public st..