Algorithm

[Java] 백준 #1463 1로 만들기

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산 세 가지를 적절히 사용해서 정수 N을 1로 만든다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 연산 사용 횟수의 최솟값 구하기 💡 알고리즘 다이나믹 프로그래밍 💡 접근 RGB거리처럼 모든 케이스의 계산횟수가 동일한 문제가 아니므로, 배열만으로는 해결하기 어려울 것 같다. → 재귀함수를 작성하고, 전역변수를 통해 최솟값을 관리하자. 💡 코드 package DP; import java.io.BufferedReader; imp..

[Algorithm/Java] 다이나믹 프로그래밍 복습

DP문제 해결 과정 = 규칙을 찾아 점화식 세우기 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 처음엔 감이 안잡히므로.. 그냥 몇문제 답을 보고 시작하는게 효율적이다. 💡 ex1. RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 주어진 비용으로 N개의 집을 빨, 초, 파로 칠하는데 N번 집은 N-1, N+1번 집과 색이 같으면 안된다 집을 칠하는 최소..

[Java] 백준 #10825 국영수

https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 학생 N명의 국, 영, 수 점수 학생 성적 정렬하기 국어 점수 감소하는 순서 국어 점수 같으면 → 영어 점수 증가 국어, 영어 같으면 → 수학 점수 감소 모두 같으면 이름 사전순 증가 (모든 대문자는 소문자 앞에) 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다. 💡 알고리즘 정렬 💡 접근 객체를 정렬하는 기준을 만들기 위해 자바에서 제공하는 Comparat..

[Java] 백준 #1158 요세푸스 문제

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1번부터 N번까지 N명의 사람이 원을 이루며 앉아있음 양의정수 K → 순서대로 K번째 사람 제거 → N명이 제거될 때까지 (N, K) 요세푸스 순열 구하기 💡 알고리즘 자료구조, 큐 💡 접근 처음에 중간에 원소가 나가면 인덱스도 하나씩 줄어들어야 하겠구나 라는 잘못된 생각을 해서 큐를 생각해내지 못했다. (규칙만 추가하며 산으로 가던 코드) int idx = K - 1; LinkedList res = new LinkedList(); while(list.size() > 0){ res.add..

[Java] 백준 #1780 종이의 개수

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net N x N 행렬 종이 → 각각 -1, 0, 1 중 하나 저장 규칙에 따라 적절한 크기로 종이 자르기 종이가 모두 같은 수 → 그대로 사용 모두 같은 수 x → 같은 크기의 종이 9개로 자르고 각각의 잘린 종이에 대하여 1번 과정 반복 이와같이 종이를 잘랐을 때 -1, 0, 1로만 채워진 종이의 개수 각각 구하기 N은 3^k꼴, 1 ≤ N ≤ 3^7 💡 알고리즘 분할 정복, 재귀 💡 접근..

[Algorithm/Python] BFS/DFS 이해하기

💡 DFS(Depth First Search) : 깊이 우선 탐색 → 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 미로에 갇혔을 때, 가던 길이 막히면 가장 최근에 있었던 갈림길로 되돌아간다 → 스택 연상 가능 ** 스택에 지나온 경로를 저장하자 ** 탐색 시작 노드를 스택에 push → 방문 처리 스택이 공백이 아니면 하나의 위치를 꺼냄 → 현재 위치 → 방문 처리 꺼낸 현재 위치가 출구 → 탐색 성공 출구가 아니다 → 상하좌우 이웃한 방들을 살펴봄 → 갈 수 있는 모든 방들을 스택에 push → 반복 O(N)의 시간이 소요되고, DFS는 스택을 사용하는 알고리즘 → 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. [구현] graph = [[], [2, 3, 8], [1, ..

[Python] 백준 #18111 마인크래프트

18111번: 마인크래프트 (acmicpc.net) 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업 세로N, 가로M 크기의 집터, 맨 왼쪽 위의 좌표 (0, 0) 좌표 (i, j)의 가장 위에 있는 블록 → 인벤토리 : 1초 인벤토리 → 좌표 (i, j)의 가장 위에 있는 블록 위에 놓음 : 2초 0 ≤ 땅의 높이 ≤ 256 땅을 고르는 데 걸리는 최소시간의 (시간, 높이) 출력 (높이가 가장 높은 답) 💡 알고리즘 구현, 브루트포스 알고리즘 💡 접근 처음..

[Python] 백준 #10989 수 정렬하기 3

10989번: 수 정렬하기 3 (acmicpc.net) 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net N개의 수 오름차순 정렬 N의 범위 (1 ≤ N ≤ 10,000,000), 최대 10,000개 정렬 💡 알고리즘 정렬 💡 접근 퀵 정렬을 사용한 재귀함수로 풀면.. 계속 수정해봐도 메모리 초과가 뜬다. 스터디 자료를 복습하면서, 계수 정렬을 이용해보았다. [계수 정렬] 특정 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 알고리즘 데이터가 양의 정수, 데이터 개수가 N, 데이터의 최대값이 K일 때, 최악의 경우에도 O(N + ..

[Python] 백준 #11866 요세푸스 문제 0

11866번: 요세푸스 문제 0 (acmicpc.net) 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net N명의 사람이 원을 이루며 앉아있음 K번째 사람을 제거 → N명의 사람이 모두 제거될 때까지 계속 제거 원에서 사람들이 제거되는 순서 ↔ (N,K)-요세푸스 순열 💡 알고리즘 구현, 자료구조, 큐 💡 접근 [Python] 백준 #1966 프린터 큐 (tistory.com) 풀다가 이 문제가 생각나서 deque으로 수월하게 해결하였다. → while문으로 카운트를 세면서 조건을 확인하고, 맞다면 result에 저장하고 pop 아니라면 맨 뒤로 보내고 pop 💡 코드 from collection..

[Python] 백준 #7568 덩치

7568번: 덩치 (acmicpc.net) 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 💡 알고리즘 구현, 브루트포스 알고리즘 💡 접근 방법 덩치 (x kg, y cm) A, B의 덩치 (x, y) (p, q) 덩치가 더 크려면 x > p, y > q 덩치 등수 : 자신보다 큰 덩치 사람의 수 + 1 같은 덩치 등수 여러명도 가능 2등이 3명 → 3, 4등 없음 N명의 몸무게, 키를 읽어서 각 사람의 덩치 등수 계산하여 출력 “덩치 등수 : 자신보다 큰 덩치 사람의 수 + 1” 조건에 집중해서..

[Python] 백준 #1966 프린터 큐

1966번: 프린터 큐 (acmicpc.net) 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 💡 알고리즘 자료구조, 큐 💡 접근방법 원소들을 Queue의 가장 뒤에 재배치하고, 가장 앞에 있는 원소는 pop해야한다. → 앞뒤로 pop, append가 자유로운 deque 사용 주어진 예시를 직접 그려보면, 두가지를 신경써서 구현해야 함을 알 수 있다. M번째 수가 몇 번째로 큰 중요도를 갖는가 → deque의 0번째 원소가 max인지 확인 M의 중요도와 같은 중요도가 있는가 → count변수로 해결 💡 코드 f..

[Python] 백준 #11052 카드 구매하기

11052번: 카드 구매하기 (acmicpc.net) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net [알고리즘] DP [접근 방법] N개의 카드 팩이 있고, N개의 카드를 구매하는 상황. D[i] = 카드 i개를 구매하는 최대 비용, dp[k] = 카드 k개가 들어있는 카드팩의 가격 일 때, 카드 i개를 구매하는 최대 비용의 경우의 수는 D[1] + dp[i - 1] D[2] + dp[i - 1] D[3] + dp[i - 3] ... D[i] + dp[0] [코드] 1 2 3 4 5 6 7 8 9 10 11 N = ..