알고리즘
-
[백준] 1992번 : 쿼드트리 - 자바(JAVA)알고리즘/백준 2022. 3. 29. 00:01
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 해석 2차원 배열에 0과 1로 이루어져 있는데 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리라는 방법이 존재한다. 주어진 영상이 모두 0으로만 되어 있으면 압축결과는 "0"이 되고 모두 1로만 되어 있으면 압축결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지 못하고 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 영상을 나누어 압축하게 됩니다...
-
4012. [모의 SW 역량테스트] 요리사알고리즘/SW Expert Academy 2022. 3. 28. 00:01
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 두 명의 손님에게 음식을 제공 두 손님은 식성이 비슷해서, 최대한 비슷한 맛의 음식으로 제공하고자 함 N개의 식재료가 존재 식재료를 각각 N/2 씩 나누어 요리하려고 함 (N = 짝수) 음식의 맛은 음식을 구성하는 식재료의 조합에 따라 달라짐 조합이라는 시너지가 존재하며 시너지 배열을 통해 계산하여 이 시너지가 최소가 되도록 구현해야 한다. 예를 들어 음식 A를 위해 식재료 2, 3, 6..
-
[백준] 11725번 : 트리의 부모 찾기 - 자바(JAVA)알고리즘/백준 2022. 3. 27. 00:01
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 루트가 없는 트리가 주어집니다. 이때 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오 문제 풀이 전 설계 우선 그래프 탐색 문제라고 생각을 했습니다. 따라서 2차원 배열 graph [i][j]를 선언하고 정점 i와 정점 j가 연결되어있으면 1 그렇지 않으면 0으로 표기합니다. 문제 풀이 하면서 생각한 점 하지만 우리가 원하는 것은 부모의 노드를 찾아야 합니다. 단순히 graph 2차원 배열에 정점이 연결된 것만으로는..
-
[백준] 1074번 : Z - 자바(JAVA)알고리즘/백준 2022. 3. 26. 00:01
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 해석 크기가 2^N x 2^N인 2차원 배열을 Z 모양으로 탐색하고자 합니다. N > 1 인 경우 , 배열의 크기가 2^(N-1) x 2^(N-1)로 4등분 한 뒤에 재귀적으로 순서대로 방문합니다. N=3일 때 예시 문제 풀이 전 설계 재귀 함수를 잘 작성해야 할 것 같다. 1. r x c 배열을 생성한 후 값을 0부터 하나씩 채워가기 -> array [r][c]의 값 출력 2. a..
-
가장 빠르게 소수를 찾는 방법알고리즘/알고리즘 2022. 3. 26. 00:01
소수란? 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는, 1보다 큰 자연수입니다. 방법 1: 가장 간단한 방법 N이 소수인지 판별하기 위해서는 2 ~ N-1까지 나누어서 하나라도 나누어 떨어지는가를 확인하는 방법이 있습니다. 이는 한개의 숫자에 대해 소수인지 파별하기 위해서는 O(N)의 시간 복잡도를 가지며 N개의 수에 대해서는 O(N^2)의 시간 복잡도를 가집니다. 방법 2 : 제곱근 만약 12에 대하여 소수를 판별하려고 합니다. 12의 약수는 1, 2, 3, 4, 6, 12를 가집니다. 가장 간단한 방법처럼 12를 2부터 N-1까지 나누어보려고 할 때 2* 6 = 6 * 2의 성질을 이용한 방법입니다. (xy = yx) 제곱근을 기준으로 제좁근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 ..
-
[백준] 2839번 : 설탕 배달 - 자바(JAVA)알고리즘/백준 2022. 3. 25. 00:01
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 해석 설탕을 정확하게 N 킬로그램 배달해야 한다. 설탕 봉지는 3kg 와 5kg 봉지가 있다. 최대한 적은 봉지를 들고 가려고 할 때 봉지 몇 개를 들고 가야 할까? 정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다. 문제 풀이 전 설계 N의 범위가 3~5000이기 때문에 완전탐색으로 하기는 힘들 것 같습니다. 최대한 적은 봉지를 들고가야 하기 때문에 5kg 봉지를 들고 가는 것이 제일 좋습니다...
-
[백준] 3040번 : 백설 공주와 일곱 난쟁이 - 자바(JAVA)알고리즘/백준 2022. 3. 22. 00:01
https://www.acmicpc.net/problem/3040 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net 문제 해석 일곱 난쟁이의 모자의 합은 100이다 그런데 갑자기 아홉 난쟁이가 등장하여 각자 자신이 진짜라고 우기는 상황이다. 이때 모자의 합을 통해 진짜 난쟁이가 누구인지 판별하라 모든 숫자는 서로 다르고, 답이 유일한 경우만 입력으로 주어진다. 문제 풀이 전 설계 N의 크기가 9이며 조합을 통한 완전 탐색으로 해결합니다. 9C7을 통해 7명의 난쟁이를 뽑고 모자의 합이 100이라면 출력..
-
[백준] 2089번 : 외판원순회 - 자바(JAVA)알고리즘/백준 2022. 3. 21. 00:18
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 해석 N개의 도시가 존재합니다. 도시를 연결하는 단방향 도로가 존재하며 도로를 가는 데는 비용이 존재합니다. 문제 풀이 전 설계 1번도시에서 출발한 경우, 2번 도시에서 출발한 경우를 모두 DFS를 통해 완전 탐색해보기 -> 시간 초과 문제 풀이하면서 1번 도시에서 출발한 경우, 2번 도시에서 출발한 경우를 세어줄 필요는 없습니다. 어떤 도시를 선택해도 ..