본문 바로가기

코딩테스트

[백준] 1522 문자열 교환 풀이 java 1. 문제 설명문제 설명2. 접근 방식KEY WORD: Sliding Window, 나머지 연산아이디어를 떠올리기가 어려워서 다른 사람의 풀이 블로그에서 아이디어 부분까지만 봤다.나는 a와 b를 일일히 교환하는데만 집중하고 있었는데, 완전히 잘못된 접근 방식이었다. 그러한 방식으로 풀었을 때, 최소값을 어떻게 찾을 수 있을지 감이 안온다. 문제를 푸는 방식은 다음과 같다. 문자열 내의 a의 개수를 세고, 그 개수를 용량으로 하는 Sliding window를 만든다.문자열의 처음부터, 1번에서 센 슬라이딩 윈도우의 용량만큼 a와 b의 개수를 센다. b의 개수 == 교환이 일어나는 횟수 이다. 현재 a의 개수만큼씩 배열을 확인하고 있고, 거기서 b의 개수를 전부 a로 돌린다면, 연속된 a와 연속된 b가 .. 더보기
이분 탐색 & Upper Bound, Lower Bound 개념 정리 1. Binary-Search란 무엇인가요?정렬된 배열 혹은 List 에서 탐색 구간을 절반씩 줄여가며 특정 값을 찾는 탐색법이다. 다음과 같이 진행 된다.(0) 기본적인 용어는 다음과 같다.target: 찾고자 하는 값, start : 왼쪽 포인터,(index=0에서 시작), end: 오른쪽 포인터(배열 끝에서 시작), mid: 두 값의 중간에 위치한 값(1) mid를 구하고 target 값과 대소관계를 비교한다.(2) mid > target 이면, mid 값이 target값으로 향하도록, end = mid-1 로 탐색 영역을 절반 줄인다.(3) mid target 이면, start = mid +1 이 되도록 하여, 탐색 영역을 절반 줄인다.(4) mid == target 이면 값을 구했으므로, 이분 .. 더보기

티스토리툴바