전체 글

문제 https://www.acmicpc.net/problem/14501  다음 문제에서 목표로 하는 최대 수익을 얻으려면 모든 가능한 선택지를 비교하고, 가장 높은 수익을 선택해야 한다.아래 문제를 보면, i일 이후에도 얻을 수 있는 최대 수익을 대략적으로 계산할 수 있다. 이러한 특징을 기반으로 현재를 최적화하는 방식에 적합한 DP 방식으로 풀이해보았다.   점화식 세우기 i번째 날에서 선택될 수 있는 결정은 두 가지로 구분될 수 있다. 오늘 시작되는 상담을 했을 때, 퇴사일까지 끝나지 않는 경우 (상담하지 못한다)오늘 시작되는 상담을 했을 때, 퇴사일 안에 끝나는 경우 (상담한다)   i일에 상담 가능한 경우의 기준상담이 끝나는 날인 i + T[i] -1 일이 N 이하여야 한다.즉, i + T[..

로컬에서는 빌드가 잘 되는데 Github Actions에서 gradle build를 하면 위와 같은 에러가 나오는 경우가 있다.gradle-wrapper.jar가 커밋되지 않았기 때문에 GitHub Actions 환경에서 올바르게 로드되지 않을 가능성이 크다고 나와서 의심되는 부분을 살펴보았다.  gradle-wrapper.jar 파일의 깃 누락이 의심되어서 .gitignore 파일을 수정하고 다시 돌려보았더니 똑같은 에러를 내뱉는다.(일단 임시적으로 jar로 끝나는 파일들을 gitignore에서 제외했다.)  이런 저런 방법들을 시도해 본 결과, ./gradlew --version을 실행하는데 그에 대한 Gradle Wrapper가 제대로 인식되지 않는 상황이었기 때문이라는 것을 확인할 수 있었다. (..

두 노드 사이가 길이가 가장 긴 값을 찾는 문제이다.임의의 지점에서 가장 먼 정점을 찾고, 다시 그정점으로부터 가장 먼 정점을 구하면 트리의 지름이 된다. 문제   임의의 노드 1에서 시작했다고 가정한 다음, 이전 연결 노드의 가중치를 합산해가며 노드 거리의 배열을 저장 한다. 그리고 가장거리가 먼 노드를 찾으면 그 정점에서 BFS를 재실행하는 방식으로 노드 거리 배열을 저장하며 답을 구한다.     BFS 풀이package BFS;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class BOJ1167 { static ArrayList[]..

수열 A에 대해 버블 소트를 수행했을 때, swap이 총 몇 번 발생하는지를 알아내는 문제이다. N의 범위가 최대 500,000이기에 O(n^2)인 버블 소트로 풀이하면 시간 초과가 발생하는 문제가 발생한다. 여기서는 O(NlogN)의 시간복잡도를 가진 병합 정렬을 사용하여 풀이하였다. 두 그룹을 병합하는 과정에서 버블 정렬의 swap이 포함되어 있다는 것을 떠올리는게 포인트였다.  문제    문제 풀이 버블 소트에서 swap이 일어나는 조건 : 배열 앞의 숫자가 뒤의 숫자보다 클 때 (A[i] > A[i+n])result의 자료형을 처음에는 int로 설정했었으나 틀렸다는 결과가 뜨자 long으로 바꾸었더니 통과가 되었다.아마도 최악의 경우, n의 최대 범위에서 모두 swap이 일어나고, 그 swap 횟..

앞서 포스팅한 수 정렬하기2 문제를 풀면서 이해 안가는 부분이 있어 병합 정렬의 개념을 다시 한번 복기하고자 이 문제를 풀이해보았다.재귀를 활용한 Top down 방식으로 풀이하였다.문제   풀이 import java.util.Arrays;import java.util.Scanner;// 배열 A에 K 번째 저장되는 수를 구하는 문제public class BOJ24060 { static int[] arr, tmp; // 저장 횟수 누적 카운트 static int count = 0; // 결과 (실패 시 -1 출력) static int result = -1; // 저장 횟수 static int k; public static void main(String[] arg..

문제     문제 풀이  안일하게 Array.sort() 돌렸다가 시간초과가 났었다.검색해보니 Arrays.sort()는 dual pivot quicksort 알고리즘을 사용하기에 시간 초과가 난 것이라고 한다.dual-pivot Quicksort 알고리즘은 평균 시간복잡도가 O(nlogn) 이고, 최악의 경우 시간복잡도는 O(n2) 이기 때문에..N의 범위가 1,000,000까지로 꽤나 크다 보니 최악의 경우 시간복잡도가 O(nlogn)인 알고리즘을 활용해야 했다.힙 정렬과 병합 정렬이 해당하는데 병합 정렬을 적용하여 풀이하였다.       병합정렬 풀이 import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOExcept..

캡스톤, 기말 등 각종 이벤트들로 인해 그동안 백준을 많이 풀지 못하였는데 쉬운 것부터 다시 복습하고자 정리해보았다.이전 포스트와 같이 인접 행렬, 인접리스트, 그래프 형태로 풀이해보았다. 문제  문제를 통해 탐색을 시작할 정점의 번호가 1번부터 시작한다는 것을 알 수 있다.  입력 예제   문제 풀이 입력 예제를 참고하여 아래와 같이 그래프를 그리고, 그에 따른 인접리스트와 각 노드 별 연결 상태를 나타내는 행렬을 그려보았다.BFS 기준으로 탐색을 진행하였을 때에는 1, 2, 5, 3, 6의 순서로 이동하고, 이 때 바이러스에 걸리게 되는 컴퓨터의 수는 1번 컴퓨터를 제외한 4개이다. 이러한 연결 및 탐색 정보를 통해 BFS로 풀면 간단하게 풀리겠구나를 짐작하고 코드로 옮겨보았다.      인접 리스트..

CoreML을 적용한 iOS 앱을 만들며 마주한 에러와 해결 방법을 정리해보려 한다.파이썬 프로젝트에서 keras 모델을 생성하여 Xcode에 모델을 추가하기 위해 변환하는 과정을 진행하고 있었는데coremltools 패키지를 이용하면 CoreML에서 쓰이는 형식인 .mlmodel로 변환이 가능하다.    추출된 mlmodel을 Xcode 프로젝트에 성공적으로 추가해주었다.  그리고 실행하여 이미지를 앨범에서 선택하여 분류를 시작하였는데 다음과 같은 에러가 떴다.  왜인지 검색해봤더니 모델의 입력 형식과 관련해서 설정이 되지 않아 나오는 에러인 듯 했다. 아무래도 모델을 추출하는 과정에서 설정이 잘못된 듯 하여 파이썬 코드를 다시 확인해보았다.  CoreML 모델로 변환 시 입력 텐서의 이름을 모델의 ..