DevBoi

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 우선 해당 문제는 이분 탐색의 종류중에서, 약간 응용 버전인, Parameter Search이다. 어떤 배열의 값들은 알수없으나, 정렬이 되어있는 경우 사용할수 있고, 특정 조건들을 만족하는 답중에서, 최대 or 최소를 구할때 사용한다. 아래와 같은 구조로 해당 문제의 기준을 세웠다. 1. 정답 범위, int 자료형은 2억까지이므로, 20억의 연산과정값이 발..

이분탐색 ? 정렬이 보장되어있는 배열에서, 이분을 하면서 탐색하는기법 이분탐색은 전형적인 변수 세팅을 사용한다. 왼쪽, 오른쪽의 포인터 두개를 가지고 시작한다. 항상 가운데의 인덱스를 보고, 해당 인덱스와 , 타겟을 비교하고, 해당 비교를 통해 포인터 L 혹은 R을 비교하면서 포인터를 이동시킨다. https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 이분탐색에 대한 예제이다. 쉽게말하면, 한 집합을..

https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 해당은 간단하다. 문자열을 int로 받아서, 새로운 배열에 넣어주고, 해당 배열을 역순출력해주면 된다.

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 대표적인 정렬이다. 객체 object로 받아서, 해당 object가 Comparable에 대한 걸 impl하게 하고, 해당 compareTo를 오버라이드해서 객체의 비교조건을 구현, 해당 객체를 비교해주면, 끝난다. foreach가 돌때, 객체의 특정 이름만 필요하기 때문에, word의 이름만 출력해준다.

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net ATM 풀이이다. 간단하게, 정렬을 하고, foreach로 부분합을 구하는 것이다. 부분합을 구한뒤에, 다음 each가 돌기전에 list에 add를 해주고, 마지막에 List의 값을 다 합해주면 된다. list2.indexOf(object) 를 사용해서, 해당 인덱스를 구하는 방법이 있다. 인덱스가 필요할때는, 전통적인 for문이 최적화가 되어있어, 빠르기때문에 해당 방법으로 돌려주면 좋고 인덱스를 굳이 사용해야하는지에 대한 ..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 해당 관련되서는, 퀵정렬을 사용해서 풀었다. 퀵정렬은 처음 값을 pivot으로 놓고, 재귀를 통해서 무한히, pivot보다 작으면 오른쪽 , 크면 왼쪽 배열로정렬하는 것이다. 그러면 그 안에서도 정렬이 필요하기 때문에, 재귀로 구현한다. 해당 안에서 정렬을 하고 왼쪽 pivot 오른쪽 으로 addAll을 통해, 배열을 합친다. 해당 방법으로 합치게 되면, 정렬 된 배열을 만들 수있다. (재귀로 한다면) 소스 참고

해당, 관련되서는 간단하다. 모든 정렬에 대한 공식? 같은 것들이 있는데 그것중 하나는 특정 node나 class를 선언하고 comparable을 impl하고, 내부에서 compareTo를 오버라이드 하는 것이다. 해당 과 같이 구현하면, 단순히 이름,국,영,수를 받아서 비교 및 정렬을 할수 있다. compateTo를 구현하게 되면 sort를 했을때 특정 sort기준? 을 정할수있다.

1. 카운팅 정렬 1. 숫자가 등장한 횟수 를 다른 한가지의 배열에 넣는다 2. 다른 한가지의 배열의 누적합으로 값을 update해준다. 3. 기존 숫자들이 있던 배열 마지막부터, 새로 생성한 배열을 보면서, 정렬 index를 찾는다 ex. 4가 5번 등장하면, arr[5] =4 이런식으로 (만약 중복되는 값이 있어, index에 값이 이미있다면, -1 을 해준다.) 이해가 잘되는 애니메이션 링크 https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html Counting Sort This is an animation of the counting sort algorithm found in CLR's Algorithms ..

스프링 부트와 스프링의 차이 간단하게 추후 공부용으로 정리를 해보자 1. 불필요한 설정? 개발자가 설정할 부분이 줄어든다 Spring 은 xml 지옥과도 같은, web.xml 부터 servlet.xml applicationContext.xml 등과같은 필터, 리스터, 디펜던시 설정 팩토리설정 뷰 리졸버 설정 버전 설정을 다 일일히 해줘야한다. 하지만 spring boot는 버전관리도 스프링부트가 해주기 때문에 호환되는 라이브러리에 대한 종속성 버전 같은걸 개발자가 신경쓸 필요가 없다. starter 의존성 한줄로 많은걸 자동 설정해준다. 2. 내장형 톰캣을 사용한다. 스프링부트는 내장형 톰캣을 사용하고있어서 별도 톰캣설정을 하지않아도 바로 서버를 실행해서 코드를 짤수있다. 또한 환경설정 및 인프라적인 요..

브루트 포스 부분 수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제는 생각 보다 심플하다. 재귀를 두가지 방식으로 넘겨주면된다. 다만 재귀를 넘길때, 몇번째의 row의 값을 넘기면서, value값을 같이 넘기고, 해당 값을 비교하여, answer을 추가해준다. 해당 재귀를 넘길때는 value를 지금 값과 합친값, 그리고 합치지 않은 값의 두가지 방식으로 넘긴다.