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

1. 점심식사시간(SWExpert) 사용 알고리즘 : 비트마스크. 완전탐색 이거 푸는데 반나절이 걸린 것 같다... 오래 걸린이유가 문제를 잘못이해한데다가 테케가 46개나 통과됬다.예외 사항 찾으려고 손수 최솟값을 구하려고 했는데 정답이 나오지가 않았다. 그래서 예제를 다시해보니 계단이 꽉찾을때 앞사람이 이동 완료하는 시간 +1 아니라 동시에 출발이었다... 문제에 대한 접근&생각계단이 2개, 사람 최대 10명, n 완전탐색!어떤 사람이 어느 계단을 이용할지 판단 -> 비트마스크!한계단에 사람 3명초과 동시이용 불가 -> 결과조건 내 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051..

1. 탈주범검거(SWExpert) 사용 알고리즘 : BFS 문제를 슬쩍보고 에이 간단한 BFS 문제네 하고 풀었는데 호되게 혼났다...문제의 조건들을 확실하게 봐야한다는 교훈을 얻었다. 이문제는 통로가 연결되는 통로인지 아닌지가 중요하다..문제에 대한 접근&생각통로를 시간에 맞춰 탐색 -> BFS!통로가 없는 경우는 0이다, 통로는 연결되어있어야한다. -> 탐색안하는 조건!통로는 7가지가 있고 각각 방향이 다르다 -> 탐색하는 방향!최초 통로도 포함된다 -> 초기값설정!탐색하는 시간이 주어진다 -> 종료조건! 다른 방법 풀이DFS로 해당시간까지 탐색한다. 제일 짧은 코드에서 갈수있는 방향 체크를 하,우,상,좌로 두고 (i+2)%4로 체크하고 나처럼 3차원배열이 아닌 2,1차원을 따로 분리했다. 내 코드 ..

1. 디저트카페(SWExpert) 사용 알고리즘 : DFS, 백트래킹 어떻게 알고리즘으로 그려야 하는지 감이 안잡혀서 어렵게 느껴졌던 문제이다. DFS의 활용 문제중 기본문제가 아닐까 생각이든다. 테트로미노 문제도 그렇고 어떤 도형을 그릴때는 DFS로 하면 될 것 같다.(펜 띠지 않고 그릴수 있는 도형만)문제에 대한 접근&생각도형 그리기 -> DFS!모든 직사각형 영역을 구해야함 -> 백트래킹!디저트가 같을 경우 갈 수 없음 -> 종료 조건 내 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767..

1. 홈 방범 서비스(SWExpert) 사용 알고리즘 : BFS, 완전탐색 처음에 문제를 봤을때 어려워보인다는 생각이 들었는데 잘 생각해보니 답이 풀렸다.이걸 풀고 가장 속도가 낮은 풀이를 봤는데 수학적으로 접근한 것을 보고 놀라웠다... 저 경지에 이르려면 어떤 사고가 필요할까..문제에 대한 접근&생각영역모양이 어디서 많이 본듯함 -> 세포배양문제 풀때 나옴 -> BFS가 거리에 따라 탐색하는 모양이랑 같음 -> BFS!모든 서비스 영역에 대해 홈 방법서비스 영역을 구해야함 -> 완전탐색!전체 모든 배열이 서비스 영역일 수 있음 -> k는 n보다 크게 다른 방법 풀이이 방법도 좌표를 기준으로 하지만 좌표에 대해 모든 홈의 좌표를 탐색한다.수학적으로 해당 좌표에서 홈좌표를 각각 빼서 더하면 영역의 크기를..

벌꿀채취(SWExpert) 사용 알고리즘 : 완전탐색 이 문제는 댓글을 보고 겹치는 구간에 대한 조건이 있었는데 이 조건을 안해야 통과되는 것을 알고 풀었다. 문제에 대한 접근&생각 일꾼은 두명으로 고정됨 -> 완전탐색! 정해진 용량이상 담을 수 없음 -> 종료조건 일꾼은 두명이지만 가져오는 꿀의 양은 같음 -> 두개의 라인만 선택하면됨 두개의 최대값 -> 정렬! 내 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 im..

1. 수영장(SWExpert)완전탐색 문제다른 코드들을 보니 DP로 많이 푸는 것을 보았다. 바로 완전탐색으로 짜는 것보다 DP로 푸는것이 어떨까 생각이 들었다.123456789101112131415161718192021222324252627282930313233343536373839404142434445import java.util.Scanner; public class Solution { static int day; static int month; static int month_three; static int year; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); /*..

1. 줄기세포배양(SWExpert)BFS, 정렬 문제이문제를 풀면서 Integer.compare로 정렬 코드 짤때 코드를 간결하게 짤수 있다는 것을 배웠다..처음에 접근할때 세포가 번식하면 죽는걸로 했는데 알고보니 생명력 만큼 살아있었다.. 이부분은 다른사람 코드를 보고 힌트를 얻었다.Cell의 생명력의 두배만큼 해주면 최대 살수 있는 시간이 되므로 이를 활용하여 문제를 풀었다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586import java.util.Array..

1. 숫자만들기(SWExpert)완전탐색 백트래킹 문제백준에서 풀었던 연산문제와 동일했다. SWExpert는 테스트케이스 형태로 주어지기 때문에 초기화에 신경을 많이 써야한다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263import java.util.Scanner; public class Solution { static int n; static int[] oper = new int[4]; static int[] nums; public static void main(String[] args) { Scanner sc = new Scanner(Sy..

1. 보물상자비밀번호(SWExpert)문자열 처리, 자료구조 문제진법변환하는 메서드를 직접 만들어서 풀었는데 parseInt(문자열,진수) 하면 한줄로 변환하는게 가능했다.. 다른 사람의 코드를 봤는데 TreeSet을 이용해서 약간 놀랐다. 처음에는 나도 Set을 쓰려고 했는데 저장순서가 없어서 쓰지 않았다.생각해보면 저장 순서와는 전혀 관련없는 정렬문제인데 좀 착각한것 같다. TreeSet에 경우 정렬과 검색이 빠르다.(중복저장X)parseInt와 TreeSet을 쓰니 코드의 거의 반을 줄일 수 있었다...123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960..

1. 1937번 욕심쟁이판다(BJO)DP 메모제이션 문제이문제가 DP 메모제이션 기본 문제가 아닐까 생각이 들었다. 일반 BFS는 배열의 크기가 500 이므로 5억번 이상의 연산이 발생한다.여기서 가장 중요한것은 1. 횟수 누적을 위한 재귀, 2. 이미 방문한 지점에 대한 처리 3. 더이상 갈수 없는 경우 처리 이다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283import java.util.Scanner; public class Main { static int n; sta..

1. 1965번 상자넣기(BJO)DP를 이용하는 NlogN LIS문제이문제는 배열의 인덱스를 이용하여 저장 변경을 활용하는 문제이다. JAVA에서는 lowbound가 없어서 이부분을 조심해야 한다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263import java.util.Arrays;import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); i..

1. 균형점(SWExpert)이분탐색 문제이문제는 오차 때문에 애를 먹었다. 하나를 맞추면 다른 하나가 오버플로우 발생하고 또 발생하고 이를 잡는데 시간이 좀 걸렸다.느낀 것은 이분탐색의 횟수를 고정하는 부분, 오차가 문제에서 주어진 것을 쓰는 부분 두가지 생각이 필요하다는 것을 배웠다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980import java.util.Scanner; public class Solution { static double[] pairx; static double..