좀 더 상세한 클래스와 구현 인터페이스는 다음과 같다. Collection Interface Iterator 인터페이스를 상속한 Collection은 가장 기본이 되는 인터페이스로 add(), remove(), size(), contains(), equals(), isEmpty() iterator() 메소드를 가지고 있다. Collection

프로그래머스 요격 시스템 > 비슷한 문제 (백준 1931 회의실 배정) 그리디 알고리즘을 활용한 문제였다. 비슷한 문제인 회의실 배정에서는 회의가 시작하는 시간이 빨라도 늦게 끝나면 최대 회의의 수를 맞출 수 없기 때문에 회의의 종료시간이 중요했다. 이 문제에서는 모든 미사일을 제거해야 했기 때문에, 왼쪽(x = 0)부터 탐색한다는 가정 하에 미사일의 **오른쪽을

String / StringBuffer / StringBuilder의 차이점을 잘 정리한 분이 계셔서 출처를 밝히고 블로그에 정리하고 복습하기로 했다. 출처: https://ifuwanna.tistory.com/221 Java에서 문자열을 다루는 대표적인 클래스로 String, StringBuffer, StringBuilder가 있다. 그러나 연산 횟수가 많아지거나 멀티쓰레드, Race condition 등의 상황이 자주 발생한다면 각 클래스의 특징을 이해하고 상황에 맞는 적절한 클래스를 사용해야 한다. String String 클래스틑 불변(immutable)의 속성을 갖는다. 그래서 String의 객체 두 개를 conacat 하기 위해서 +연산을 활용할 때, 두 스트링이 연결되는 것이 아니라 새로 생성한 String 인스턴스의 메모리 영역을 가리키게 변경되고 처음 선언했던 메모리 영역은 Garbage

백준 17085 십자가 2개 놓기 DFS를 활용해 가능한 경우의 조합을 구하고 완전 탐색을 활용해 해결하는 문제다. 시행 착오를 많이 겪어서 겨우 해결한 문제다. 그 중 제일 시간을 많이 뺏었던 것은 점을 기준으로 가능한 가장 큰 십자가를 만드려고 했던 것이다. 1 X 9보단 5 X 5의 값이 더 크다는 것을 고려해서 십자가가 만들어질 수 있는 모든 경우에 대해서 대비를 했어야 했다. >1. 입력을 boolean 배열로 받아 '#'인 경우는 true로 저장한다.

백준 1525 퍼즐 격자의 크기가 별로 크지 않아 전체 경우의 수는 9!(=362,880)이기 때문에, 완전 탐색임을 금방 알 수 있지만 구현하는 과정이 까다로웠다. 처음엔 DFS를 활용하여 구현했지만, StackOverflow 에러가 발생했다. BFS 탐색을 활용하여 문제를 해결했지만, 격자점의 형태를 이미 방문했는지 확인하는 방법에서 굉장히 고생했다. 처음엔 HashMap에 2차원의 int 배열을 전달했지만, 배열의 메모리 주소를 해쉬 맵에 저장

백준 11724 연결 요소의 개수 Union Find를 활용하는 문제다. 일반적으로 유니온 파인드 문제는 부모를 찾는 함수, 부모가 같은지 확인하는 함수, 부모를 통합하는 함수 3가지를 만들지만 문제가 간단해서 2개의 함수만 만들었다. > 1. 배열에 저장된 값은 해당 인덱스의 부모다 기본값은 자기 자신이지만 부모가 자기 자신이 아니라면, 부모를 찾는다. 두 노드가 부모를 찾았다면 더 작은 값으로 부모를 통합한다.

백준 17135 캐슬 디펜스 DFS를 활용해 조합하고 모든 경우를 확인하는 완전탐색으로 해결했다. 구현하는 과정에서 신경쓸게 많아서 실수도 많았다. > 1. 궁수의 위치는 DFS를 활용해 조합한다. 적의 위치는 ArrayList를 이용해 위치를 저장한다. 같은 적을 쏠 수 있기 때문에 바로 적을 제거하는 것이 아니라 target 배열에 저장 적이 내려오는 것은 궁수의 사거리가 1씩 늘리고, 탐색 범위도 1씩 줄였다(성에 들어와도 리스트에서 제거해야 하기 때문)

백준 1239 차트 수열을 구한 후에 부분수열들의 합이 50인 개수를 세는 문제였다. 투포인터를 활용하여 합이 50인 부분수열을 찾았고 DFS를 활용하여 수열을 찾았다. N이 작아 중복을 허용해도 크게 문제될 것 같지 않아 중복을 허용했다. 숫자가 커졌다면 HashSet을 활용하여 중복을 제거할 생각이었다. > - DFS를 활용하여 수열을 찾는다. 투포인터를 활용하여 합이 50인 부분수열을 찾는다. 하나의 요소라도 50보다 크다면 알고리즘을 종료한다.

백준 14226 이모티콘 BFS를 활용한 문제다. BFS 탐색이기 때문에 먼저 방문했던 노드가 비용이 더 적을 수 밖에 없다. 즉, DP 리스트가 아니라 방문했던 노드인지만 확인하면 된다. 같은 값을 방문했더라도 값을 복사한 경우는 시간이 1초 증가하기 때문에 방문한 노드와 현재 복사된 값까지 고려해서 boolean 배열을 만들어야 한다. > 1. BFS 탐색이기 때문에 한 번 방문했던 노드를 다시 방문하는 것은 최솟값이 될 수 없다. 현재 값이 target보다 크다면 붙여넣거나, 1을 더할 필요가 없다. 값이 같아도 복사한 값이 다르다면 다른 경우로 보아야 한다. > - taget을 만나면 값을 출력하고 프로그램 종료

백준 13913 숨바꼭질 4 DP와 BFS를 활용해야 한다는 것을 알아도 이것저것 실수해서 푸는데 시간이 걸린 문제다. target값을 찾은 후 비용을 출력하고 부모를 추적하며 찾아간다. > 1. BFS 탐색이기 때문에 한 번 방문했던 노드를 다시 방문하는 것은 최솟값이 될 수 없다. 이미 값이 target보다 크다면 2배를 곱하거나 1을 더할 필요가 없다. K보다 N이 큰 경우, 값이 같아질 때까지 1을 빼야 한다.(메모리 초과 방지) > - 방문했는지 확인할 boolean 배열 isVisit 현재까지 비용을 저장할 int 배열 time 부모를 저장할 int 배열 parent

백준 15486 퇴사2 N의 숫자가 상당히 큰 것을 미루어 보아 완전 탐색은 아니라고 추측할 수 있다. > 1. 완전 탐색은 아니다. 앞에 일어난 사건이 뒤에 일어난 사건에 영향을 준다. 하지만 뒤에서 일어난 사건이 앞에 일어난 사건에 영향을 주진 않는다. 즉, DP로 해결해야한다는 것을 알 수 있다. 조심해야할 점이 있었다. 하루가 걸리는 일은 당일에 일을 끝내고 수당을 챙길 수 있다. 일을 시작할 수 있는 날을 기준으로 수당을 저장하면 마지막 날에 당일 하루만 일하고 수당을 받는 날은 계산이 되지 않는다. 수당을 받는 날을 기준으로 DP를 활용하되, 최대값을 기억하는 변수를 만든다면 해결할 수 있다.

백준 1451 직사각형으로 나누기 신박한 문제풀이 없이 그저 케이스 분류였다(이것도 divide and conquer이라고 할 수 있나?). 누적합을 이용하는 것인가 혼자 오랫동안 삽질했다. 가끔은 이런 단순한 문제도 잊지 않는 것이 좋을 것 같다. > - 직사각형 3개로 직사각형을 나누는 경우는 총 6가지이다. 결과값이 클 것을 예상하고 long 타입을 활용

백준 1720 타일 코드 타일 문제는 DP 문제의 대명사이지만 대칭이라면 같은 타일로 취급해야 하는 문제다. 한 가지 아이디어가 포인트였다. 짝수인 경우와 홀수인 경우를 나누어 풀면 어렵지 않은 문제였다. 기본 DP를 바탕으로 모든 경우를 더한 후에 좌우대칭인 경우를 한 번 더 더하고 2로 나눈다. > 좌우대칭이 되는 경우를 한 번 더 더하고 2로 나눈다.

백준 1034 램프 수의 범위가 50이었고 전체 경우의 수는 2^50으로 완전 탐색으로 해결할 수 없는 문제였다. 모든 경우가 독립적이지 않다고 생각하고 완전 탐색으로 해결하려 했지만, 잘못된 생각이었다. 단순 구현으로 해결하려 한 코드이다. 당연하게도 시간 초과였다. 램프의 특징은 다음과 같다. > 1. 모든 행은 서로 독립적이다 즉, 위 아래 행이 서로 영향을 받지 않는다. 0의 개수뿐만 아니라 위치도 중요하다. 서로 다른 모양의 행이 동시에 조건을 만족할 수 없다. 즉 한 가지 모양의 행만 선택해야 한다. 위 특징들을 토대로 알고리즘을 수정했다. > 1. 완전 탐색은 최대 2^50의 경우로 불가능하다. 모든

백준 1124 언더 프라임 처음에 재귀를 활용한 조합으로 문제를 해결하려 했지만 코드가 너무 복잡해져 잘못됨을 느꼈다. 그다음엔 DP를 활용해야겠다 생각했다 주요 아이디어는 다음과 같다. > 1. 에라토스테네스의 체를 활용하여 소수를 구한다. DP 리스트를 만들어 해당하는 수가 소수로 나누어지는지 확인하고 i가 j로 나누어진다면, DP[i] = DP[i / j] + 1이다. 작은 수부터 탐색하기 때문에 값이 벗어나는 경우는 없다. DP에 저장된 소인수 개수는 HashSet을 활용하여 소수인지 확인한다.

백준 1235 효율적인 해킹 DFS와 BFS 두 방법 모두 가능한 문제지만 BFS로 풀었다. ArrayList 배열을 선언했고, 메모리 초과를 방지하기 위해 인접 리스트로 풀었다. DFS와 BFS를 활용할 때는 언제나 DP도 같이 사용할 수 있는지 확인한다. 1가지 문제로 인해서 DP를 활용하기 힘들었다. > 방문한 노드는 계산에서 빼기 때문에, 노드가 겹친 경우 DP로 값을 저장하면 오차가 생길 수 있다. 또한 ArrayList 배열를 초기화하는 방법과 update하는 방식이 중요했다. 또한 BFS 함수를 만들 때, 작은 실수 때문에 시간초과가 났고 실수를 찾기까지 오래 걸렸다. > > 정답 코드

백준 1916번 최소비용 구하기 다익스트라 알고리즘 간단한 다익스트라 알고리즘을 구현하는 문제였지만, 메모리와 시간 제한이 타이트했다. 우선 순위 큐를 활용해서 빠른 시간 내에 문제를 해결해야 했다. 힘들었던 점 문제 설계는 쉬웠지만 아직 자바라는 언어를 다루는데 익숙하지 않아 힘들었다. ArrayList배열을 만들고 초기화는 과정에서 실수했다. 변수에 배열을 선언하는 순간 메모리를 공유하기 때문에 변수에 배열을 선언하지 않고 바로 초기화를 했어야 했다. 또한 배열을 채우는 메소드를 기억하지 못해 직접 반복문을 만들었었다.

String 선언 주요 메소드 > - put(Object key, Object value): 데이터 추가 get(Object Key): 전달된 키에 대응하는 값을 반환. 없다면 boolean이 아닌 null을 반환한다. equals(String s): 문자열이 동일한지 비교 indexOf(String s): 특정 문자열이 시작되는 위치(인덱스) 리턴 contains(String s): 특정 문자열이 포함되어 있는지 여부 리턴 charAt(int idx): 문자열에서 특정 위치의 문자(char) 리턴 replaceAll(String s1, String s2): 특정 문자열을 다른 문자열로 바꿀 때 사용 substring(int start): start부터 특정 부분을 뽑아냄 substring(int start, int end): start부터 end까지 특정 부분

백준 1374 강의실 비슷한 문제인 회의실 배정과는 접근 방법이 달랐다. 회의의 갯수를 최대로 맞춰야 하는 회의실 배정과 달리, 강의실 문제는 모든 회의를 가능하도록 하는 강의실 갯수의 최솟값이었다. 백준 1931 회의실 배정 그렇기 때문에 회의가 종료하는 시간을 기준으로 잡았던 회의실 배정과 달리 강의실은 시작하는 시간을 기준으로 정렬하고 우선순위 큐에 강의실이 끝나는 시간을 넣고 가장 빨리 끝나느 시간에도 강의가 불가

백준 1931 회의실 배정 비슷한 문제인 강의실과는 접근 방법이 조금 달랐다. 백준 1374 강의실 모든 강의를 진행하기 위해서 필요한 강의실 갯수의 최솟값과 달리 하나의 회의실에서 진행할 수 있는 회의의 최댓값이다. 이 문제는 강의실과 달리 사용할 수 있는 회의의 갯수를 최대로 맞춰야 한다.시작하는 시간이 빨라도 늦게 끝나면 최대 회의의 수를 맞출 수 없기 때문에 회의의 종료시간이 중요하게 작용한다. 따라서 회의 종료시간을 기준으로 우선순위 큐를 만들고 해당하는 회의가 종료한