일단 씻고 나가자

이것도 푸는 데 진짜 한참 걸렸다.문제 자체는 쉬워서 호기롭게 도전했지만 정확성만 맞히는 데에도 한참 걸렸다.기본기가 중요하다고 느낀 문제.   문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  Problem간략하게 DB를 만들고, 문제에 주어지는 쿼리를 날려보라 이거다.문제는 설명할 것이 없고, 효율성까지 따졌을 때 크게 대두되는 문제는 다음과 같다. 어떤 식으로 DB를 만들 것인가?와일드 카드 ( - ) 가 나왔을 때 어떻게 검색..

계속 이해를 고민했던 부분인데 비로소 명확히 이해가 되어 정리겸 포스팅한다.최대한 직관적인 이해 및 코드로 설명한다. 헷갈리는 부분만 보고 싶은 사람, 혹은 정리만 필요한 사람은 포스트의 가장 하단 부분으로 이동하자.     직관적인 설명먼저, Java는 명확한 언어이기 때문에 어물쩍 넘어가는 걸 싫어한다.따라서 배열이든 컬렉션(List 등)이든, 꼭 한 종류만 담아야 한다.이를 머릿속에 넣고 시작한다.   예시를 보자.당신은 이사를 위해 이삿짐을 트럭에 담고 있다.이삿짐은 음식, 가구, 전자기기등 다양하다. 트럭 = 배열 or 컬렉션 / 이삿짐 = 객체    Java 라는 친구는 하나의 트럭에 하나의 종류밖에 못 담게 한다고 했다.만약 종류가 다른 세 물건을 하나의 트럭에 담는다면 Java 는 불같이 ..

`마나커 알고리즘` 이란문자열 내의 회문을 빠른 속도로 판별해주는 알고리즘이다. 문자열의 개별 문자에서 양쪽 방향으로 전체 탐색을 하는 방법이 아닌,기존에 탐색했던 값을 저장하여 활용하는 dp 성격을 띄는 알고리즘이다.    원리먼저 알고리즘을 설명하기 앞서 회문의 성격에 대해 생각해보자.  회문의 성질은 다음과 같다.중간 문자를 기준하여, 같은 거리만큼 떨어진 문자는 같다.회문 내부에 회문이 존재할 수 있다.하나의 글자도 회문이 된다. 회문 검사를 더 빠른 방식으로 하기 위해선아무래도 2번 조건인 회문 내부의 회문을 검사하여 응용하는 방식이 유용해 보인다.  이때 주의해야 할 것이,보통 회문 내부의 회문이라면, 아래 예시처럼 특정 포인트를 기점으로 두 개의 같은 회문이 반복되는 케이스만을 생각하게 된다..

`누적합/구간합 알고리즘` 이란 배열에서 특정 구간의 합을 한 번의 계산으로 처리할 수 있는 기법이다. 배열이 주어지고, n만큼 연속된 구간의 합을 m번 질문한다면,일반적으론 for(0 ~ n) * m 의 방식을 활용하여 n * m 의 속도가 나오지만,누적합을 활용하면 매 질문당 한 번의 연산으로 m의 속도만이 필요하다. 일반적인 일차원 배열에서의 활용법,이차원 배열에까지 확장한 활용법과,누적합 활용을 위한 배열 세팅 방법까지 알아보자.    원리 다음 도형에서 색칠된 칸의 개수는 몇 개인가?      V  V  V  V     손으로 세어서 4칸이다.   그런데 만약 이런 푯말이 있다고 가정하자.    처음부터여기까지4칸   처음부터여기까지8칸       V  V  V  V     이 상황에서도 손으로..

새로운 마나커 알고리즘(Manacher Algorithm)에 대해 학습할 수 있었다.직관적인 이해가 어려웠던 알고리즘.   문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  Problem문제는 간단하다. 주어진 문자열 내에서 가장 긴 회문의 길이를 도출하는 문제.회문(palindrome)은 중간 글자를 기점으로 양쪽이 똑같은 문자열을 말한다.즉, 문자열이 "banana"로 주어진다면 b [ a n a n a ] = 5 를 도출하면 되..

2024. 06. 24 월요일 - [Java] String을 LocalDateTime 및 LocalTime으로 바꾸는 방법?: String str = “10:00”이라 할 때,DateTimeFormatter formatter = DateTimeFormatter.ofPattern(“mm:ss”);LocalTime time = LocalTime.parse(str, formatter);이때 LocalDateTime, LocalDate 등으로 바꿀 수 있지만, 각각의 포맷에 맞는 패턴을 모두 사용해야 한다. 즉, 위의 경우에는 LocalTime이었기 때문에 “mm:ss”라는 패턴을 성공적으로 파싱하지만, LocalDateTime에 적용할 경우 에러를 낸다. 단, parse 메서드 이용 등의 형태는 동일하다.  ..

2024. 06. 19 수요일 - dp로 부분합의 최대를 구하는 알고리즘?: 기존 배열의 크기만큼 dp 배열을 잡아놓고, dp[0] = 기존 배열[0]으로 초기화 후,for문 (i=1)을 돌며 dp[i] = Math.max(dp[i-1] + 배열[i], 배열[i]) 계산하고 매 순간 max 값을 갱신해주면 된다. 이는 이전까지 계산한 max값 보다 현재 나 스스로의 값이 더 크다면 내 스스로 값으로 초기화하고, 그 값을 또 다른 새로운 부분합의 시작점으로 잡는 원리이다.  - [Effective Java] volatile 키워드란? singleton의 동시성을 보장하는 효율적인 방법?: Java는 일반적으로 성능 향상을 위해 메인 메모리로부터 읽어온 값을 CPU 캐시에 저장하고 사용한다. 하지만 멀티 쓰..

2024. 06. 18 화요일 - [Java] Arrays.asList() 인자로 int[] 와 Integer[]을 각각 넣었을 때 차이?: Arrays.asList()는 T... array 형태로 되어 있기에 객체만을 받을 수 있다. 따라서 Integer[]는 객체 원소를 list로 바꾸어주지만 int[]는 그 자체 배열 객체 하나만을 인식하여 변환한다.  - 이진탐색의 Lower/Upper Bound 설명? 차이? 알고리즘?: 탐색 배열에서 중복된 값이 있을 때, 찾고자 하는 값이 중복된 값 중 하나일 경우, 중복된 값 중 가장 먼저 오는 자리를 구하는 것이 Lower Bound,중복된 값 중 가장 나중에 오는 자리를 구하는 것이 Upper Bound이다. 알고리즘은 이진탐색과 같게 min, max와..

2024. 06. 17 월요일 - [Effective Java] HashMap의 내부 구조 원리, 동시성을 해결하기 위한 구현체?: HashMap은 정수인 key를 활용하여 해싱 후 해당 위치에 값을 저장하는 구조로 되어 있다.이때 값의 자료구조(배열)를 버킷이라 하며, HashMap은 내부적으로 Node 객체로 가지고 있다. 용량의 75% 이상이 되면 해시 충돌의 가능성이 커지는데, 따라서 용량의 75%가 넘어가는 경우 내부적으로 HashMap의 총용량을 늘린다. 이럼에도 충돌은 피할 수 없는데, 충돌 초기에는 Node 객체의 next 주소를 활용하다가 일정 횟수가 넘어가면 Red-Black tree의 형태로 구조를 바꾼다.(추가로 Map.putIfAbsent() 보다 if(Map.get() == nu..

2023. 06. 13 목요일 - 슬라이딩 윈도우로 각 구간의 최댓값을 구하는 방법?: Deque를 사용한다. 구간의 너비를 k라고 할 때, 각 원소를 index와 값으로 묶는다.(Deque에 index만 저장하여 값의 비교는 원소[index]의 방법도 있다) 다음과 같은 규칙으로 알고리즘을 작성한다.1. Deque의 peekFirst의 index가 현재 구간의 index 범위보다 벗어난 경우 제거한다.(ex. k = 3인 상황에서, index가 4일 때 Deque의 peekFirst에 1이 들어가 있을 땐 제거)2. 새로 들어올 원소가 Deque의 peekLast보다 작은지 검사하며,역순으로 작은 값을 모두 제거 (pollLast)한다.3. 새로 들어온 원소를 offerLast한다.4. 매 순간의 최댓..