문제본문 문제 해석 어떠한 수 V(i)에 대해서 몫이 a고 나머지가 r이라면 아래의 수식이 성립한다. V(i) = a(i) * m + r(i) 그리고 V(i-1) 수식을 V(i) 뺀다면 아래와 같은 수식이 된다. V(i) - V(i-1) = (a(i) - a(i-1)) * m + (r(i) - r(i-1)) 자! 문제에서 원하는 답은 N개의 수에 대해서 M으로 나누었을 때 나머지가 같게되는 M을 모두 찾는 것이다. 나머지가 같다는 것은 위 수식에 대입해보면 답은 V(i) - V(i-1)의 숫자를 나머지가 0으로 만드는 M을 찾는 것이다. N개의 수를 오름차순으로 정렬하기 long[] nums = new long[n]; for (int i = 0; i < nums.length; i++) { nums[i] ..
문제 본문 그리디 알고리즘, 탐욕법이라고 불리는 이 알고리즘은 원하는 답을 구하기 위해 모든 경우를 탐색하는 것이 아니라 문제를 해결하는 과정에서 최적이라고 생각하는 과정을 선택하는 알고리즘입니다. 문제 해석 Input: 55-50+40 output: -35 문제를 설명하자면 괄호가 생략된 수식에서 괄호를 집어넣어 최솟값을 만들어라!입니다. 예시로 주어진 입력으로 만들어 낼 수 있는 최솟값의 수식은 55-(50+40)입니다. 여기서 우리가 문제를 풀기위해 적용해야 하는 그리디 알고리즘 괄호를 수식에서 숫자를 제외한 모든 곳에 넣어서 결과를 계산한 후 최소 값을 찾는 것이 아니라 답을 구하기 위한 문제의 최적 방법을 찾는 것이죠. 최소 값을 구하기 위한 최적 방법은 최대한 크게 빼는 것입니다. Input:..
최근 Google Architecture MVP Sample project를 참고하여 MVP를 공부하던 도중 Executor의 클래스를 처음 보게 되었다. 그 후 구글링을 통해 네트워크 IO 통신과 디스크 IO 작업, UI 작업등 Background 작업을 위해 해당 클래스가 사용되었고 kotlin의 coroutine이 출시되기 이전 Thread를 유용하게 사용한 방법이었다. - Executor Inferface import java.util.concurrent interface Executor { void execute(Runnable command); } 구조로만 보면 Runnable 객체를 실행하는 단순한 구조이다. 클래스 자체로 어떤 Background 프로세스가 생성되는 것이 아닌 틀만 제공해준..
문제본문 입력 [물건의 개수] [최대 무게] 4 7 [물건 무게] [물건 가치] 6 13 4 8 3 6 5 12 ________________ 출력 [최대 가치] 14 동적프로그래밍의 대표 문제 불리는 Knapsack 알고리즘은 dp를 사용하여 무게와 가치 두 가지 요소로 가질 수 있는 최대 가치를 구하는 문제 유형이다. 문제 해설 동적프로그래밍은 dp를 어느 부분으로 잡는 지가 관건 인듯하다. Knapsack은 이중 배열로 dp를 설정한다. dp[i][j]라고 가정하면, i번째까지 물건을 집어 넣는 다고 했을 때, 남아있는 무게가 j라면 얻을 수 있는 최대가치를 뜻한다. 해당 알고리즘은 테이블로 과정을 묘사하면 이해가 더 쉽다. 무게 1 2 3 4 5 6 7 1번째 물건 0 0 0 0 0 13 13 2..
문제 본문 동적 프로그래밍이란 동적 프로그래밍 방법은 문제의 해결 과정에서 이전에 구했던 과정을 또 다시 반복하여 실행되는 것을 방지하는 방법으로, 불필요한 코드 실행이 줄어 시간을 단축시킬 수 있습니다. 하지만 O(n)의 메모리가 할당 되어야 합니다. 문제 해설 전깃줄은 백준 사이트에서 LIS(Longest Increasing Subsequence)의 응용으로 분류된 문제입니다. N개의 전깃줄을 겹치지 않게 제거해야 하는 최소 개수의 전깃줄을 구해야 합니다. 문제 설명 그대로 풀려고 해서 방법이 도저히 생각나지 않다가 사람들의 힌트를 보고 깨달았습니다. ㅎ.. 해답은 제거가 아니고 설치입니다. 최소 개수의 전깃줄을 제거하여 겹치지 않게 설치된 남은 전깃줄은 겹치지 않게 설치될 수 있는 최대 전깃줄 입니..
해당 포스팅의 코드와 설명에 오류가 있다면 댓글로 말해주시면 감사하겠습니다. 며칠 전, 출시 된지 꽤 지난 어플이 사용하던 API 서버 호출 오류로 내부 로직이 꼬여 먹통이 되어 버렸다. 해당 프로젝트는 기능 동작만 생각하던 옛날의 내가 Ctrl + c, Ctrl + v를 수행한 중복 코드도 많고 매우 비효율 적으로 구현한 작품. 다시금 스스로 작성한 코드를 보면서 디자인 패턴의 중요성을 느끼고 가장 기초적인 MVC 패턴부터 적용하기로 마음을 먹었다. Model-View-Controller 패턴 프로젝트의 기능과 비례하게 코드의 양이 늘어난다. 디자인 패턴을 적용하지 않은 프로젝트는 Activity 클래스 파일에 모든 코드가 들어가 있고 해당 클래스 파일의 코드의 수는 몇 천줄이 되어 어떤 한 기능을 수..
N사 면접 질문 ArrayList와 LinkedList의 차이점과 장단점은 무엇일까요? 비슷한 성격의 두 List의 차이점 ArrayList와 Linked List는 저장해야하는 객체의 수를 정확히 모를 때 사용하곤 했죠. 원하는 위치에 저장하거나 순차적으로 삭제, 접근할 때 등등 사용하는 입장에서 기능적으로는 비슷한 두 List는 구조적인 설계 측면에서 보면 차이점을 알 수 있습니다. ArrayList ArrayList는 re-size array기반으로 구현된 List 입니다. 내부적으로 크기가 고정인 배열로 이루어져 있고 값이 포화가 될 경우 전보다 더 길이가 긴 배열을 새로 생성하여 이전 값들을 복사하는 방식으로 무한한 객체를 저장하도록 구현한 것입니다. Linked List Linked List는..
문제본문 스도쿠 규칙 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 백트래킹이란 가능하지 않는 집합을 배제하는 완전 탐색(브루트포스)을 의미합니다. 모든 경우의 수를 구하지만 정답이 아닐 확률이 높다면 시도하지 않는 것이죠. 때문에 완전탐색보다 빠른 시간안에 정답을 구현할 수 있습니다. 관련 알고리즘의 흐름과 설명은 참고 링크에 더 자세히 나와 있습니다. 스도쿠 입력 9 x 9 스도쿠판에 0 ~ 9 숫자 값이 들어 있습니다. 빈칸은 여러개 존재할 수 있으며 빈칸은 0으로 표시합니다. 0 3 5 4 6 9 2 7 8 7 8 2 1 0 5 6 0 9 0 6 0 2 7 8 1 3 ..
Github의 저장소 설명, 커밋 메시지에 아이콘을 추가하여 다채롭게 꾸밀 수 있다. emoji 모음 링크 https://gist.github.com/rxaviers/7360908 https://gist.github.com/AliMD/3344523 :money_with_wings: -- 랜덤 로또번호 추첨과 QR 코드 인식 앱 참고 [Github] Github 저장소의 Description・Readme에 아이콘 넣기
문제 본문 하노이 탑의 규칙 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 하노이 탑은 재귀 함수로 구현하는 대표적인 문제입니다. 재귀 함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법입니다.풀고자 하는 문제가 동일한 성격의 작은 문제들로 구성되어 있을 때 사용하면 좋습니다. 하노이 탑의 규칙으로 함수의 성격을 분석해보자 문제: N개의 원판을 1번째에서 3번째로 옮긴다. (1): N - 1개의 원판을 1번째에서 2번째로 옮긴다. (2): N번째 원판을 1번째에서 3번째로 옮긴다. (3): N - 1개의 원판을 2번째에서 3번째로 옮긴다. (1)과 (3) 을 보면 N의 크기만 다를 뿐 성격을..
