개발 정보/Algorithm (7) 썸네일형 리스트형 [프로그래머스] 쿠키 구입 온라인 문제풀이 사이트 Programmers의 문제인 '쿠키 구입' 문제. https://programmers.co.kr/learn/courses/30/lessons/49995?language=java 문제는 간단하게 다음과 같다. 1. 정수형 1차원 배열(각 바구니 당 사탕의 개수)이 주어진다. 2. 두 아들에게 같은 양의 쿠키를 선물하려 한다. 3. 첫 번째 아들에게 a번째 ~ b번째 바구니, 두 번째 아들에게 b+1번째 ~ c번째 바구니를 골라 선물한다. 4. 이 때, (a ~ b)의 양 = (b+1 ~ c)의 양이어야 한다. 5. 선물할 수 있는 쿠키의 최대 개수를 구한다. 원 안의 숫자는 각 바구니에 있는 쿠키의 개수이며, 첫 번째 아들에게 2, 3번째 바구니를, 두 번째 아들에게 마지막 바구니.. [프로그래머스] 보행자 천국 (미해결) 온라인 문제풀이 사이트 Programmers의 문제 '보행자 천국' 문제. https://programmers.co.kr/learn/courses/30/lessons/1832?language=java 문제는 간단하게 다음과 같다. 1. m X n 배열이 주어진다. 2. 0은 차량 통행 가능, 1은 차량 통행 불가, 2는 좌회전과 우회전 금지(진입한 방향 기준 직진만 가능) 3. (0, 0) 부터 (m, n)까지 갈 수 있는 경로의 수를 출력한다. 풀이 과정 m과 n의 최댓값이 500이므로, 완전탐색으로 충분히 풀 수 있는 문제이다. result 배열을 만들어 오른쪽과 아래쪽 방향으로 수를 채워 나갈 것이다. 현재 index가 최상단과 가장 좌측일 경우, 진입한 경로가 하나이기 때문에 1로 채운다. 주어진.. [프로그래머스] 추석트래픽 온라인 문제풀이 사이트 Programmers의 문제이자 카카오 개발자 공채 기출인 '추석 트래픽' 문제.https://programmers.co.kr/learn/courses/30/lessons/17676 문제는 간단하게 다음과 같다.1. yyyy-mm-dd hh:mm:ss.000 0.000s 의 형태로 문자열 배열 input이 주어진다.2. hh:mm:ss.000 은 로그가 끝나는 시간. 0.000s는 해당 로그를 처리하는데 필요한 시간이다.3. 임의의 시점부터 1초동안 로그가 중복되는 구간을 파악한다.4. 중복되는 로그 개수 즉, 처리량 중 최댓값을 return 하는 문제이다. 풀이 과정우선 맨 앞의 날짜는 필요 없고, hh:mm:ss.000과 0.000s를 계산 가능한 형태로 가공하는것이 핵심이라고.. [프로그래머스] 스킬트리 온라인 문제풀이 사이트 Programmers의 '스킬트리' 문제.https://programmers.co.kr/learn/courses/30/lessons/49993?language=java 문제는 간단하게 다음과 같다.1. 스킬은 순서대로 배울 수 있다.2. CBD가 입력으로 주어지면, C -> B -> D 순서로 배울 수 있다.3. C를 배우지 않고 B나 D를 먼저 배울 수 없다.4. 즉, 배우려면 앞에서부터 순서대로 배워야 하며 중간을 건너뛸수도 없다. 풀이 과정가장 먼저 떠오른 방법은 Queue를 이용하는 것이다.체크할 대상 문자열 배열(skill_trees)를 Queue에 넣고, 배울 수 있는 스킬 순서(skill)와 비교하는 방법이다.그림으로 표현하면 아래와 같다. 문자열 BACDE의 문자 하.. [알고리즘 Tip] 행렬의 곱셈 갑자기 행렬의 곱셈은 왜? 모 회사 코딩테스트에서 행렬의 곱 성질을 이용해 2차원 배열을 연산하는 문제가 나왔다.이미 행렬의 곱셈 방법은 알고 있었지만, 막상 코드로 구현하려니 단번에 생각나지 않았다.자꾸 코드를 쓰다가 지우고 쓰다가 지우고 하며 '어, 이게 아니네?'라고 생각하기 일쑤였다.그래서 아예 행렬 곱셈 기본 틀을 기억하기 위해 포스팅을 결심했다. 행렬의 곱셈 : 기본 성질 우선 개념부터 다시 정리.1. 앞 행렬의 열의 개수와 뒷 행렬의 행의 개수가 같아야 한다. (ex. 2x3 X 3x4 : 가능 / 2x2 X 3x2 : 불가)2. 정답 행렬은 앞 행렬의 행의 개수 X 뒷 행렬의 열의 개수이다. (ex. 2x3 X 3x4 = 2x4)아래 그림과 같다. 행렬의 곱셈 : 실전 코드 행렬의 곱셈은 .. BFS, DFS BFS와 DFS 개념 BFS (Breadth-First Search) : 너비우선 탐색트리탐색의 Level-order와 동일한 기법으로 탐색. DFS (Depth-First Search) : 깊이우선 탐색트리탐색의 Inorder와 동일한 기법으로 탐색. BFS와 DFS의 기본 코드 형태 (틀) Queue가 Empty일 때까지 loop를 돌려 모든 경우를 탐색한다. 1234567891011121314public void BFS(/* input */){ Queue q = new LinkedList (); q.offer(/* input */); while(!q.isEmpty()){ currentVertex = q.poll(); // 다음.. 다이나믹 프로그래밍 [BOJ] 1149 RGB거리 온라인 알고리즘 문제 풀이에 재미를 붙여가던 중, 처음으로 난관에 부딪힌 문제였다.https://www.acmicpc.net/problem/1149 문제는 간단하게 다음과 같다.1. 개의 집이 일렬로 이루어진 배열 형태의 마을이다. 2. 와 , 와 은 이웃이고, 와 는 이웃이 아니다.3. 각 집은 빨강(R), 초록(G), 파랑(B)의 색 중 하나를 골라 칠한다.4. 이웃한 집은 같은 색으로 칠할 수 없다.5. 모든 집을 칠하는 총 비용이 최솟값이어야 한다.6. 비용은 다음과 같이 주어진다. R 비용 G 비용 B 비용 26 40 83 49 60 57 13 89 99 7. 해당 예제의 정답은 (26) + (57) + (13) = 96이다. 풀이 과정최초 문제 풀이는 단순한 Math.min() 계산을 이용했다.. 이전 1 다음
