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

1. 가능한시험점수(SWExpert) 사용 알고리즘 : DP 이 문제는 완전탐색을 생각하다가 계산해보니 연산이 너무 많아서 고민하다 힌트를 보고 풀었다.DP의 가장 큰 특징이 누적이니만큼 이러한 문제를 접근할때 어떻게 누적을 해야될지로 접근해보면 좋을것 같다. 문제에 대한 접근&생각모든 점수가 나오는 경우의 수 -> 완전탐색? -> 점수가 100가지 총 2^100 연산 -> 불가능경우의 수를 최소화 -> 점수들은 이전 점수들과 관계가 있음 -> 누적!(DP) 내 코드 1234567891011121314151617181920212223242526272829303132333435363738import java.util.Scanner; public class Solution { public static voi..

1. 1939번 중량제한(BJO) 사용 알고리즘 : BFS, 이분탐색 요즘 이분탐색 카테고리 문제를 풀고있어 이 문제를 봤을때 카테고리 모르고 봤을때 이분탐색을 생각할 수 있을까라는 생각이 들었다. 문제만 보면 그래프 느낌이 들었고 왜 이분탐색일까라는 생각이 많이 들었다.그 이유가 https://www.acmicpc.net/board/view/33835 여기에 잘 나와있었다.오래걸린 이유가 지점에서 다른지점으로 가는데 경로가 여러개 일 수 있다는 조건 때문에 할때마다 정렬하니 메모리초과가 발생했다...이분탐색으로 푼다면 어떤 경로를 사용하든 통과만 하면되는 것이 이 문제의 핵심인 것 같다.문제에 대한 접근&생각a지점에서 b지점까지 운반해야함 -> BFS!옮길 수 있는 최대 무게를 구해야함(운반 거리는 상..

1. 1654번 랜선자르기(BJO) 사용 알고리즘 : 이분탐색 딱 그 갯수에 맟추는 것인 줄 알았는데 그 이상이 되도 상관이 없었다...이분탐색의 경우 연산하면서 int 범위를 벗어나는 경우가 발생하므로 long형을 고려해야하는 것을 깨달았다.문제에 대한 접근&생각랜선길이가 231-1 범위를 가진다 -> 이분탐색!자를수 있는 최대의 길이를 출력 -> 탐색기준!랜선의 길이가 int형의 최대값이므로 여기 까지 탐색해야함 -> int형 대신 long! 내 코드 1234567891011121314151617181920212223242526272829303132333435363738import java.util.Scanner; public class Main { public static void main(Stri..

1. 2805번 나무자르기(BJO) 사용 알고리즘 : 이분탐색 기준 설정까지는 괜찮았는데 답을 구하는 측면에서 나무 자른게 딱 떨어지지 않을때에 대한 처리가 미흡했다.수학적으로 잘못접근해서 조금 오래걸렸다. 루프가 끝날때의 start인덱스를 출력했는데 그렇게 하면 결과조건을 충족하지 못했다.최대의 높이니까 결과조건에 해당될때는 저장하고 그것을 출력하는 부분이 필요했다.문제에 대한 접근&생각정답의 크기(나무높이)가 20000000 넘어감 -> 이분탐색!이분탐색으로 가장 최대의 높이를 찾아야함 -> 결과조건! (루프가 끝나는 순간이 아닌 최대에 도달한 값을 저장해야함) 내 코드 1234567891011121314151617181920212223242526272829303132333435363738394041..

1. 방문길이(Programmers) 사용 알고리즘 : 시뮬레이션 점으로 생각하고 풀다보니 중복에 대한 처리가 안되서 조금 시간이 걸렸던 것 같다. 좌표를 배열로 바꿀때 크기를 칸의 갯수가 아닌 점에 갯수에 맞춰야겠다. 문제에 대한 접근&생각새로갔던 길만 카운트 -> 점으로 잡고 방문 표시 -> 하나의 점에 중복되는 경우 체크하지 못함 중복에 대한 처리 -> 4차원 배열을 이용해 출발 도착 경로 표시 (반대로도) 다른 방법 풀이Set 이나 List를 이용해서 경로를 저장하여 중복을 처리하는 방법이 있었다. 내 코드 12345678910111213141516171819202122232425262728293031323334class Solution { public int solution(String dirs..

기지국설치(Programmers) 사용 알고리즘 : 그리디 코드는 간결하지만 다른 어려운 BFS, DFS 문제들보다 더 어려운 것 같다. 되게 사고력이 필요한 문제 인 것 같다. 다른 코드를 참조해서 풀었는데 이런 부류의 문제들을 많이 풀어봐야 할 것 같다. 인덱스를 이용하지 않고 배열을 만든다던가 하면 시간초과가 발생했다. 시간에 대한 제약이 푸는데 힌트가 될수 도 있을 것 같다. 내 코드 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 class Solution { public int solution(int n, int[] stations, int w) { ..

1. 단속카메라(Programmers) 사용 알고리즘 : 그리디 구현코드는 간단하지만 접근하기가 어려웠던 문제, 확실히 그리디 문제는 많이 풀어봐야 접근 방법이 눈에 보일 것 같다.문제에 대한 접근&생각각각의 자동차에 대한 범위가 주어짐 -> 정렬?단속카메라를 최소로 설치해 모든 자동차를 커버할 수 있는 경우 -> 위치는 여러곳이 될 수 있음 -> 최적의 선택 -> 그리디 내 코드 123456789101112131415161718192021222324252627282930313233343536373839import java.util.Arrays; class Solution { public static void main(String[] args) { System.out.println(solution(new..

1. 구명보트(Programmers) 사용 알고리즘 : 그리디 처음에 풀때는 visited를 이용하여 모든 경우를 확인 했더니 시간초과가 발생했다.곰곰히 생각해보면 visited 필요없이 point를 계속 이동 시켜주면 되는 문제였다. 쉬운문제일수록 효율성에 대해서 생각을 많이 해봐야 겠다. 문제에 대한 접근&생각사람들은 각각 무게가 있고 순서없이 존재한다 -> 정렬!구명보트는 최대 2명 탈 수 있고 제한 무게가 있다 -> 작은 몸무게 + 큰 몸무게를 최선의 선택 -> 그리디 내 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445import java.util.Arrays;import java.util.Li..

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