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

1. 큰수만들기(Programmers) 사용 알고리즘 : 그리디 오랜만에 그리디 문제를 풀었는데 확실히 그리디는 규칙을 찾아내는것이 필요한것 같다.char 배열은 new String(char)로 문자열로 변경이 가능하다.문제에 대한 접근&생각문자열을 탐색하면서 각 순서마다 큰수를 구해야함 -> 그리디 다른 방법 풀이Stack을 이용해 크기비교를 통해서 가장 큰수가 되는 문자열을 쌓는다. 내 코드 12345678910111213141516171819202122232425262728293031class Solution { public static void main(String[] args) { System.out.println(solution("784542123132813531535156541313", 2)..

가장 먼 노드(Programmers) 사용 알고리즘 : 다익스트라(BFS) BFS, DFS 문제만 풀다보니 잊어버릴꺼 같아서 최단경로 문제를 풀어보았다. 쉬운 문제 였지만 확실히 빠릿하게 풀진 못했다... 다풀고 제출했더니 마지막 두 케이스에서 메모리 초과가 발생했다. 처음에 배열로 해보고 싶어서 배열로 만들었더니 그게 문제가 되었다. int형 배열은 하나당 4Byte 이므로 최대 4Byte * 50000 * 50000 -> 9.31 GB .... 메모리초과가 무조건 발생할 수 밖에 없었다. 문제에 대한 접근&생각 1번 정점부터 각 정점까지의 최단거리 -> 다익스트라 내 코드 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 ..

1. 징검다리(Programmers) 사용 알고리즘 : 이분탐색 이문제는 알고리즘 카테고리를 보고 문제를 풀었는데도 접근방향이 떠오르지 않았다. 무엇을 이분탐색 재료로 쓸지와 문제가 원하는 조건에 대한 로직을 어떻게 여기에 맞게 구현하느냐 핵심인 것 같았다.이 문제를 모르고 봤을때 이분탐색이 떠오를 수 있을까 라는 생각이 들었고 이분탐색도 많이 풀어봐야 겠다.문제에 대한 접근&생각바위를 제거해서 그 사이의 최소값 중 최대값을 구해야함 -> 완전탐색?, 이분탐색?바위 갯수 & 제거 갯수 50000개 -> 이분탐색 ! 내 코드 123456789101112131415161718192021222324252627282930313233343536import java.util.Arrays; public class S..

1. 무선충전(SWExpert) 사용 알고리즘 : DFS, 완전탐색 이문제는 탐색을 어떤 것을 기준으로 하냐에 따라서 상당히 어려울 수 있는 문제다.처음에 접근 방식은 BFS로 BC의 범위에 해당하는 곳에 BC번호를 부여하고 이를 기준으로 비트마스크로 풀려고 했다.비트마스크를 이용하다 보니 속도도 오래 걸리고 Queue 가 계속돌아 메모리도 상당히 커졌다.다른 사람 풀이를 보니 기준을 사람으로 잡고 BC를 완전탐색해서 푼 것을 보고 훨신 쉽구나라는 것을 느꼈다. 문제에 대한 접근&생각유저는 최대 2명, BC는 최대 8개 -> 완전탐색!같은 BC를 사용할 수 있지만 이때는 충전량의 반 -> 결과조건!원하는 결과가 최대합이므로 유저들을 합쳐서 처리 가능-> sum으로 DFS! 내 코드 123456789101..

1. 14502번 연구소(BJO) 사용 알고리즘 : DFS, 완전탐색 예전에 풀었던 문제인데 오랜만에 풀수 있을까 싶어서 다시 풀어보았다. 30분도 안되서 풀고 속도랑 코드량이 많이 줄었다!!궁금해서 BufferedReader랑 Scanner랑 차이가 있을까 싶어서 해봤는데 별로 차이가 없다... n,m이 작은 것도 있지만..Scanner 쓴다고 해서 정답이 시간초과가 나는 경우는 없을 것 같다.( Scanner 가 보기에 더 깔끔...) 문제에 대한 접근&생각벽을 최대 3개 지정할 수 있음 -> 완전탐색!바이러스는 벽을 제외하고 퍼짐 -> DFS! 내 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454..

1. 벽돌깨기(SWExpert) 사용 알고리즘 : DFS, 완전탐색 이 문제를 풀면서 벽돌의 크기만큼 깼을때 다시 돌아오는 경우를 어떻게 처리 해야할지가 가장 어려웠다. 예를 들어 왼쪽으로 깨질때 3 0 8 이면 8이 깨질때 다시 왼쪽으로 가야하는 부분에서 감이 잘안와서 다른포스팅을 참고했다. 위에 저문제를 벽돌크기만큼 반복해서 처리하는 것을 보고 감탄했다. 좀 더 넓게 보는 사고가 필요한 것 같다. 문제에 대한 접근&생각공은 N번 쏠수 있고 쏜데 또 쏠수 있음 -> 완전탐색!벽돌이 깨질떄 상하좌우에 있는 벽돌도 깨짐 -> DFS!벽돌에는 크기가 있어서 크기만큼 깨져야함 -> DFS 반복! 다른 방법 풀이깨지는 벽돌의 수를 DP를 통해 저장하여 마지막에 총개수에서 빼주는 방식 내 코드 1234567891..

1. 11559번 Puyo Puyo(BJO) 사용 알고리즘 : DFS 이 문제는 시뮬레이션이 첨가된 문제인 것 같다는 생각이 들었다. 설명이 보기 어렵게(?)되어 있어 아쉬웠지만 꽤 괜찮은 문제인것 같다.한번에 통과할 수 있게 예외사항, 조건들을 완벽히 파악하는 시간이 필요할 것 같다.문제에 대한 접근&생각같은색깔 뿌요가 4개 이상이면 터진다 -> DFS!뿌요는 아래로 내려온다 -> 중력!한번에 터질 수 있는 경우가 여러개 일경우 한번에 처리 -> 탐색조건! 내 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717..

1. 활주로건설(SWExpert) 사용 알고리즘 : 시뮬레이션2019/02/16 - [공부/Algorithm] - 115. 14890번 경사로와 유사한 문제여서 다시 풀어 봤는데 생각이 잘나지 않았다.다시 참고해서 풀었는데 다시봐도 저런 사고를 할 수 있다는게 신기하고 더 열심히 해야겠다.문제에 대한 접근&생각활주로 가로 세로 모두 확인 해야함 -> 하나의 배열로!경사로는 낮은 곳 높은 곳을 길이만 큼 설치 할 수 있음 -> 처리 조건! 내 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960import java.util.Scanner; public cl..

1. 17135번 캐슬디펜스(BJO) 사용 알고리즘 : 완전탐색 꽤 오래걸려서 풀었다. 입력값을 디버그 하기 쉽지 않은 문제여서 테케가 다 맞으면 틀린부분을 찾기가 힘들었다. 이럴때는 디버그 하지말고 천천히 로직에 문제를 찾아 봐야겠다. (물론 처음에 완벽하게 하는게 가장 중요한듯....)왜그런지 모르겠는데 처음에 이문제를 그냥 BFS로 풀려고 하니 당연히 시간초과가 발생했다. (최대사거리가 10인데..)문제를 풀때 조건들 하나하나를 확실하게 하고 코드를 짜야겠다. 아쉬운건 속도가 좀 느린데 3중반복이 들어가서 그런것 같다. 속도를 줄일 수 있는 부분을 찾아 봐야겠다.문제에 대한 접근&생각궁수는 3명이고 죽일수 있는 적의 최대값을 구해야함 -> 궁수자리 완전탐색!궁수는 사정거리 까지만 적을 죽일 수 있음..

1. 17069번 파이프 옮기기2(BJO) 사용 알고리즘 : DFS, DP 메모제이션, 백트래킹 처음에는 BFS 방식으로 하려고 했는데 BFS 보다는 DFS가 더 나을 것 같았다. 근데 요새 BFS만 쓰다보니 DFS를 구성하는데 헷갈렸다.BFS는 보통 순서가 있는데 이문제는 계속 탐색하면서 백트래킹을 해야했다. 즉 자주쓰는 Order을 만들 수 없었다.이문제를 풀면서 DFS로 전구간 탐색하는 것을 다시 상기 시켰다.. 또 잊어버리면 이코드를 참조 해야겠다.문제에 대한 접근&생각파이프는 3가지 모양이 있고 각각 움직이면서 모양을 바꿀 수 있는 가지수가 정해져 있다 -> 탐색조건!대각선 파이프는 움직일때 해당 칸의 3칸이 비어있어야 한다 -> 종료조건!파이프의 길이는 2고 앞의 위치가 움직인뒤 뒤의 위치는 ..

1. 요리사(SWExpert) 사용 알고리즘 : 완전탐색 생각보다 오래걸렸던 문제.. 조합 만드는 과정에서 로직이 살짝 햇갈렸다. 문제에 대한 접근&생각모든 재료를 사용 -> 완전탐색!시간초과 -> 순열의 경우 중복되는 경우가 발생중복 경우 제거 -> 조합! 내 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263import java.util.Scanner; public class Solution { static int n; static int[][] map; public static void main(String[] args) { /*****..

1. 등산로(SWExpert) 사용 알고리즘 : DFS, DP, 완전탐색 이문제는 푸는데 시간이 많이 걸리지 않았다. 판다 문제유형과 비슷했고 확실하게 어떻게 풀어야하는지 느낌이 와서 그런것 같다.문제에 대한 접근&생각길을 찾아야 한다 -> DFS!최대 팔수 있는 깊이가 주어진다(한번) -> 완전탐색!현 위치보다 낮은데만 갈수 있음 -> DP! 내 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102i..