인생자취

필자는 dp 방식으로 풀기 위해 메모이제이션에 사용할 배열을 잘못 생성하여 본 문제에 대해 12시간 이상을 고민했다. 독자는 그러지 마시길 바라며 글을 시작한다. 1. 문제 이해 _ 댐은 n개의 수문을 가지고 있다. 각각의 수문은 자체 용량과 물길을 가지고 있고, 하류에 영향을 줄 수 있다. 수문이 열렸을 때, 영향을 받는 지역은 홍수의 위험이 있다. 수문에 의한 예상 피해액은 지역의 인구의 수와 면적으로 계산할 수 있다. 수문 Gi의 유량이 Fi m3/hour 이고, 피해 비용이 Ci라고 하자. 댐에는 물이 Vm3 만큼 저장되어 있고, 이 물을 T시간 이내에 모두 비워내야 하는 상황이다. 이때, 수문을 어떻게 열어야 피해 비용이 최소가 되는지를 구하는 프로그램을 작성하시오. 예를 들어, 댐에 수문이 4..

1. 문제 분석Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. 본 문제는 주어진 정수 배열인 nums를 가능한 모든 순열로 만들어서 반환하는 문제다. 어떠한 순서로든 반환이 가능하다. 2. 로직 플로우int 배열인 nums를 입력받고, 배열의 순서를 바꿀 때 사용할 temp 배열을 같은 int 배열로 생성한다. 그리고 dfs에서 방문 순서에 쓰일 visited 배열을 초기화 한 뒤, dfs 함수를 호출한다. 재귀함수 형태로 dfs를 통과할 때는 visited의 방문 체크를 true, false로 바꾸면서 진행한다. dfs를 재귀적으로 호출하..

1. 문제 이해 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력값이 길이가 N인 수열에 해당한다. 이 수열의 부분합을 구하는데, 또다른 입력 값인 S 이상이 되는 경우를 찾는다. 그 중에서 연속된 수의 길이 중 가장 짧은 길이를 구하는 것이다. 이때 부분합을 구하는 방법으로는 1차원 배열이므로 투포인터 알고리즘을 적용한다. * 투포인터(Two Pointer) 알고리즘 : left와 right로 구분한 두 포인터를 좌우로 이동해가면서 요구조건에 맞는 답을 찾는 풀이법이다. 2. 로직 2-1) 로직 플로우 정수 배열은 수열의 길이는 N+1로 초기화 시킴(ri..

1. 들어가기Java.util.Arrays 클래스에는 sort()가 있다. Arrays.sort()를 호출하면 배열을 정렬할 수 있다.위 [사진 1]을 통해 sort()는 DualPivotQuicksort로 정렬이 이뤄진다는 것은 쉽게 찾아볼 수 있고, JAVA에서 제공하는 API를 사용하는 정도로만 알고 있었기 때문에 정렬에 대한 더 자세한 구현에 대해서는 크게 관심을 갖지 않았었다. 그런데 새로운 사실을 알게 되었다. Arrays.sort()와 관련하여 JAVA API 문서에 다음과 같이 적힌 내용 때문이다.All elements in the array must implement the Comparable interface.[사진 2]와 [사진 3]을 통해 Comparable interface가 이렇..

본 문제는 벨만 포드 알고리즘 개념으로 해결할 수 있는 최단경로문제입니다. 벨만 포드 알고리즘에 대한 개념은 아래 링크로 확인해주시고, 문제를 바로 풀어보도록 하겠습니다. 2023.07.14 - [개발/Dev | 알고리즘] - 최단 경로 문제 (2) 벨만-포드 알고리즘을 중심으로 최단 경로 문제 (2) 벨만-포드 알고리즘을 중심으로 1. 들어가기 지난 글에서는 경로의 가중치가 음이 아닌 수로 부여된 경우에 사용되는 다익스트라 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 단일 출발지의 최단 24h-daily-life.tistory.com 1. 문제 이해 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수..

독자님은 코딩테스트 문제를 풀면서 밤을 새본 적이 있나요? 저는 있습니다. :)... 독자님은 밤을 새시지 마시라는 의도로 본 글을 쓰게 되었습니다. 사실 구글링만 해보면 되는 결과를 안보고 풀겠다고 고집을 부리다가 또 밤을 새버렸네요. 지난 6월에 주에 한번 꼴로는 밤을 새본 것 같습니다. 이 문제도 그러한 문제 중 한 문제라고 보시면 되겠습니다. 정말 간단하게 풀어지는 풀이법은 dp로 이차원 배열로 정의해서 메모이제이션 방식으로 푸는겁니다. 그런데 저는 1차원 배열인 dp로 풀기 위해서 많은 시간을 사용했습니다. 고집을 포기하는 순간 행복해지는 거더라구요!_! 어쨌든. https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ ..

https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr주차요금 계산 문제를 풀고 나서 생각해보면 너무 간단한 건데, 자꾸 실수하는 내용이 있어서 이를 기록하기 위해서 글로 남긴다. 1. 문제 요약이 문제를 요약해보면 다음과 같다. 1) 주차장의 요금표와 차량이 들어오고 나간 기록이 input 데이터로 주어짐(단, 차량 출입 기록에 들어온 기록만 있는 경우에는 23:59에 출차한 것으로 간주.) 2) 차량별로 주차 요금을 계산(단, 주차요금 계산 시 단위요..

Integer array가 A=[-1, 2, -3, 4]로 주어졌다고 가정하자. 이때 array의 원소 3개를 더해서 특정 값이 되는 경우를 찾고자 한다. 그런데 array의 길이가 길어질수록 계산은 복잡해진다. 따라서 이를 bit값의 형태로 변환하여 array의 원소 중 특정 원소만 찾는 방법으로 생각해본다.[아이디어 1] 비트 연산자를 사용하여 array 중 특정 규칙에 한해서 선택하는 경우를 모두 찾는다. 비트 연산자를 활용하는 방법은 다음과 같다. 1

문자열이 숫자로만 이루어진 조건에서 두 문자열이 일치하는 수만큼을 출력 하는 경우가 존재하고, 그 숫자들이 반환될 때 내림차순으로 정렬되어 반환되어야 한다고 가정해보자. 이와 관련하여 문제 해결 방법을 떠올리는 것은 다음과 같다. [아이디어 1] 문자열을 비교할 때 내림차순으로 비교 ; for(int i=9, i>=0, i--) - valueOf : String.valueOf(int a)를 사용하여 int 값을 문자열로 변환한다. 반복자를 문자열로 반환한다. 이와 같은 리턴값을 내는 메서드는 Integer의 toString(int i)이 있다. public static String valueOf​(int i) - charAt : 특정 위치의 문자열을 확인할 때, char 타입으로 반환하는 String의 ..

분수를 더하는 가장 복잡한 방법은 코드를 짜서 분수를 더하는 것이다. :? 하지만, 단발성이 아닌 작업에서는 손으로 계산하는 수고가 훨씬 덜하겠지만, 반복적인 작업에서는 코드를 짜서 분수를 더하면 손으로 계산하는 수고는 줄어들게 된다. :> 두 분수를 더할 때의 로직을 생각해보면, 다음과 같은 로직으로 생각해야 할 것이다. 1. 두 분수의 분모들의 '최대공약수'를 구함 2. 통분 3. 분자의 덧셈 4. 기약분수를 구하기 위해 '최대공약수'를 구함 5. 답 반환 이때, 로직을 구현하기 위한 주요 아이디어는 최대공약수를 구하는 방법을 구현하는 것이다. 최대공약수는 유클리드 알고리즘을 활용해서 구하고, 유클리드 알고리즘은 재귀함수의 형태로 구현한다. 유클리드 알고리즘의 실행은 다음과 같다. EUCLID(30,..