전체 글

Lower bound, Upper bound란? 그림을 보면 쉽게 이해할 수 있다. lower bound: 찾고자 하는 값이 처음 나타나는 위치 upper bound: 찾고자 하는 값 바로 뒤 위치 원래 이진탐색 코드 //오름차순 정렬된 arr에서 target값을 찾아 인덱스를 반환하는 함수 private int findIdx(int[] arr, int target) { int start = 0; int end = arr.length; while (start target end ..

정렬관련 골드 문제를 풀다 이진탐색을 구현하는 연습이 부족하다는 걸 느꼈다. (start와 end 인덱스를 어디를 잡아야할 지 헷갈렸음) 그래서 이번 기회에 이진탐색 문제 몇 개를 풀어보려고 한다! 공부할 수록 공부해야할 게 늘어나는 것 같다 ㅎㅎ 이진탐색이란? 리스트를 두 부분으로 나눠 필요한 부분에서만 탐색하도록 제한하여 원소를 찾는 방법이다 ex) [ 1 2 3 4 5 6 7 8 9 ] 와 같이 오름차순으로 정렬된 리스트가 있고 3을 찾아야한다 일단 1~9번째 원소의 중간인 5를 본다 5는 3보다 크니 탐색범위를 1~4로 줄인다 1~4번째 원소의 중간인 2를 본다 2는 3보다 작으니 탐색범위를 3~4로 줄인다 .. 이 과정을 반복하여 3을 찾아냄 이진탐색을 위해서는 정렬이 필수적이며, 평균적으로 순..

이진탐색 관련 문제를 풀던 중, Arrays에 binarySearch 메서드가 있는 걸 발견하였다! 원래는 직접 이진탐색을 구현하여 사용하였지만 컬렉션에서 지원된다면 사용하는 게 더 효율적일 것 같다. 그래서 이번엔 binarySearch 메서드를 알아보려고 한다. 정의 binarySearch 메서드를 타고 들어가보면 이렇게 긴 설명이 있다. Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the r..

실버문제를 어느정도 풀어봤으니 이제 sorting 관련 골드 문제를 풀려고한다! https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 10억까지 정수로 나타내지고, 합은 최대 20억정도가 될 수 있으니 int값에 저장할 수 있음 처음 생각한 풀이(시간초과) 음수값을 저장하는 배열과 양수값을 저장하는 배열을 만들어 정렬한다 인덱스로 비교비교하면서 차이가 0에 가까운 애를 result에 저장한다 양수값이 하나도 없다면 ..

이전글 https://fladi.tistory.com/329 [JAVA] 백준 sorting - 실버모음 1181 단어 정렬(실버5) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 fladi.tistory.com 1302 베스트설러(실버4) https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 ..

int one = Integer.valueOf(String.valueOf('1')); // 뭔가 잘못됐음을 느낌 이전까지 알고리즘 문제를 풀 때 char를 String으로 변경한 후 Integer.valueOf를 사용했는데 뭔가 잘못됐음을 느꼈다. 이번에 정확하게 정리하려고 함 캐릭터형은 정수값으로 관리되기 때문에 바로 Integer로 변경하려고 하면 이상한 값이 나오게된다. '1'이 아스키코드 49 이런식으로 판별되기 때문이다. 그래서 정확하게 형변환해주는 게 중요하다! 1. Character.getNumericValue() 사용 int one = Character.getNumericValue('1'); //1 컬렉션에서 지원하는 문법이다 가장 가독성이 좋은 것 같다. 꼭 외워둬야지 2. ASCII 코..

1181 단어 정렬(실버5) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 저번에 풀었던 문제다! (2달전 쯤) 중복된 단어는 하나만 남기고 제거해야한다는 것에서 set냄새가 난다 정렬을 해야하는 set이라면 treeset을 사용하는 게 좋을 것 같다 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br...

알고리즘 공부 중 내가 정렬에 익숙하지 않다는 걸 알아냈다! comparator도 기억이 잘 안났고, 이름은 오름차순 정렬하면서 성적은 내림차순 정렬하는 등 두 번 이상 정렬하는 것도 헷갈렸다. 그래서 이번에 소팅관련 문제를 싹 풀고 익숙해져보려고 한다! 2757 세수정렬(브론즈4) https://www.acmicpc.net/problem/2752 2752번: 세수정렬 정수 세 개가 주어진다. 이 수는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 수는 모두 다르다. www.acmicpc.net 세 개의 수를 정렬하는 방법을 찾는다 그냥 sort쓰면 될듯 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St..

(저는 추천순으로 문제 풀고있습니당) 1206 [S/W 문제해결 기본] 1일차 - View (D3) https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1&&&&&&&&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이것도 브..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 체스를 안한 지 오래돼서 퀸이 갈 수 있는 곳이 기억안났음. 구글링 해봤다 딱히 규칙이 보이지 않음. visit배열과 백트래킹을 사용해야겠다고 생각함. 1행의 모든 칸에 대해 퀸이 놓였다고 생각하고 다음 놓을 수 있는 자리에 퀸을 놓기 (visit = true) 퀸이 놓인 행은 올킬이니까 다음 행부터 빠르게 찾기(가지치기) 행마다 한 개씩 안놓이면 N개의 queen을 놓을 수 없음 -> 가지치기 풀이 public..