개발자로 살아남기

더블릿의 배송 문제는 다음과 같이 해결한다. 위와 같은 경우입니다. 답은 150인데, 현재 소스는 120을 출력하고 있습니다. 즉, 처음 선택할때 1 6 40에 해당하는 40에서 30만큼을 선택하기 때문에 끝날때까지 택배 가방(님이 가방으로 표현하셔서 그렇게 얘기하겠습니다 ㅋ) 용량이 30으로 밖에 유지될 수 없어서 중간에 크게 옮겨실어나를수 있음에도 불구하고 계속 용량 30밖에 못사용하는거죠. 그럼 어떻게 하냐... s에서 택배꾸러미를 받아서 e에서 택배를 내려놓는다고 할때 s에서부터 e-1까지 해당 택배꾸러미를 계속 들고 있어야 합니다. (e는 내려놓는곳이니까 제외하죠) 해당 택배꾸러미의 용량을 w라고 하면 s부터 e까지는 택배를 기본 여유용량 C에서 w만큼 뺀 것입니다. 즉, 예를 들면 원래 가방용..

문제 바로가기 저울 문제는 물건의 비교값이 있는 부분을 X 축 기준으로는 작은값, Y축 기준으로는 큰값로 생각하고 배열을 DFS로 확인하여 값을 알 수 있는 데이터를 비교한다. 단방향 간선 그래프, DFS, 이미 방문한 곳은 방문하지 않는다. 이것이 요점사항 인 것 같다.

최백준님의 나는 어떻게 알고리즘을 공부했을까? 설명자료 - 질문하고- 설명하고- 모르면 정답을 찾아보고- 정답을 이해하는 것도 내 실력 나는 어떻게 알고리즘을 공부했을까? + 신기한 방법으로 문제 풀어보기 from Baekjoon Choi

더블릿, 자리배정 알고리즘 문제 순서대로 이동하면서 값을 매겨서 자리를 확인한다.

줄세우기 알고리즘 해결방법은 다음과 같다. 줄을 세울때 맨 앞과 맨뒤로만 보낼수 있기 때문에, 순서대로 읽어 가면서 정렬이 되어 있는 상태의 숫자는 옮기지 않아도 된다. 정렬이 되어 있지 않은 데이터중 1은 맨앞으로 옮기고, 나머지는 순서대로 맨뒤로 옮기면 자동으로 정렬이 되게 된다. 5, 2, 4, 1, 3의 경우 2, 3은 순서대로 정렬이 되기 때문에 이를 제외한 나머지 값을 옮기게 되므로 5-2 = 3으로 3번 움직여야 한다. 5, 2, 3, 4, 7, 1, 6의 경우 2, 3, 4는 순서대로 정렬 되기 때문에 이를 제외한 나머지 값을 옮기게 되므로 7-3 = 4로 4번 움직여야 한다. 이를 처리하는 코드는 다음과 같다.

아래의 예제는 '프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략' 이라는 책의 미리보기에서 확인할 수 있는 내용이다. 이를 통해 효율적인 알고리즘을 구성하면 수행시간이 얼마나 짧아 질 수 있는 가를 확인할 수 있다. { -7, 4, -3, 6, 3, -8, 3, 4 } 에서 최대의 합을 갖는 구간을 찾아서, 최대의 합을 출력하는 문제이다. 책의 예제를 Java 로 수정하면 아래와 같다. 알고리즘 구성에 따라 for 문을 한번만 사용하고서 답을 찾을 수도 있다. 이렇게 효율적인 알고리즘을 구성하는 것은 무엇보다 중요하다. package algorithm; public class EfficientMaxSum { static int[] array = { -7, 4, -3, 6, 3, -8, 3, 4 }; ..

정보 올림피아드 문제 해결을 위한 공부를 위해서 여러 자료를 찾던 중 발견한 한국정보화 진흥원의 자료이다. 아래의 링크에 들어가면 초급, 중급, 고급 문제해결을 위한 기본자료들이 있다. 문제에 대한 접근을 어떻게 해야 할지 알 있을 것 같다. - 문제 해결을 위한 창의적 알고리즘 초급- 문제 해결을 위한 창의적 알고리즘 중급- 문제 해결을 위한 창의적 알고리즘 상급 https://www.digitalculture.or.kr/koi/StudyBook.do

1. 배열의 인덱스에 적합한 값으로 -1씩 처리(배열은 0부터 시작)2. 몇번을 반복하면 기존의 값이 현재 위치로 되돌아 오는지 확인후 Set 에 저장- 중복값 자동 제거- 오름차순 정렬3. Set의 마지막 값을 배수로 키우면서 각 값들의 최소공배수를 확인 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1516&sca=2020

순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산을 말한다. 1, 2, 3 이라는 숫자의 집합이 있을 때, 다음과 같이 뒤섞는 연산이다. 1,2,3 1,3,2 2,1,3 2,3,1 3,2,1 3,1,2 자바에서는 재귀연산을 이용해 해결할 수 있다. 기준점(pivot)이 되는 배열의 인덱스를 제공하면, 해당 인덱스의 뒤쪽에 있는 값들과 위치를 변경후 기준점을 다음의 위치로 옮겨 다시 호출하는 순서로 진행한다. 아래와 같이 배열을 이용하는 방법과 문자열을 이용하는 방법이 있다. * 순열은 문자열의 길이이 따라 n! 로 시간이 걸리게 된다. 문자열의 길이가 20, 30 개가 된다면 시간이 굉장히 오래 걸리게 된다. http://gorakgarak.tistory.com/522 http://stacko..

ArrayList 를 이용한 깊이 우선탐색, 너비우선 탐색 구현은 다음과 같다.

버블정렬(거품정렬) 시간복잡도가 n의 제곱으로 늘어나기 때문에 시간이 굉장히 오래 걸린다. 정렬에 걸리는 시간은 오래 걸리지만 알고리즘이 단순하기 때문에 자주 사용된다. 알고리즘은 다음과 같다. 배열의 n번과 n+1번을 비교하여 n번이 더 크면 둘을 바꾼다. 즉 더 큰값을 뒤로 돌린다. 이를 반복하여 가장 큰값을 맨뒤로 보내고 이를 처음부터 마지막의 앞까지 반복하여 정렬을 진행한다. https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.1.1 https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC