티스토리

짧은머리 개발자

검색하기

블로그 홈

짧은머리 개발자

dev-whoan.xyz/m

DevOps Engineer | 짧은머리 개발자

구독자: 2

방명록 방문하기

주요 글 목록

[Java 코딩테스트] 프로그래머스 광물캐기 그리디 풀이 Description 본 문제는 그리디로 풀 수 있다. 한 곡괭이로 캘 수 있는 5번 횟수에 대해 각 구간을 정한다. 모든 미네랄에 대해 곡괭이로 캘 수 있는 횟수까지 대해 구간을 정한다. 곡괭이 1개라면, 5회, 2개라면 10회, … 이 때 곡괭이로 캘 수 있는 수량 보다 미네랄이 적을 수 있으므로, 내가 볼 구간의 length는 Math.min( 곡괭이 횟수, 광물 수 / 5 ) / 5를 해주는 이유는 한 곡괭이로 5번 밖에 못 캐기 때문이다. 이에 대해 모든 곡괭이를 사용하여 얼마만큼의 비용이 발생하는지 확인한다. 곡괭이가 없어도 일단 계산한다. 나중에 조건을 이용해 사용하지 않으면 되기 때문 각 구간에 대해 값을 모두 구했다면, 이를 돌 곡괭이 > 철 곡괭이 > 다이아몬드 곡괭이 순으로 우선순위 .. 공감수 1 댓글수 0 2023. 3. 29.
[Java 코딩테스트] 프로그래머스 연속 펄스 부분 수열의 합 풀이 / 연속 배열의 최대 합 Problem 연속 펄스 부분 수열의 합 darklight sublimevimemacs Java 문제 설명 어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, .. 공감수 0 댓글수 0 2023. 3. 2.
[알고리즘] BackTracking 기법, N Queen 예시/ 퇴각검색 기법 오늘은 알고리즘 중 Backtracking 기법을 다뤄보려 한다. Backtracking - 한정 조건을 가진 문제를 풀려는 전략 - 해를 얻을 때까지 모든 가능성을 시도 출처 https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 위키피디아의 설명처럼, 해를 얻을 때 까지 모든 가능성을 시도하는데, 완전 탐색과의 다른 점은 "신경쓰지 않아도 되는 수는 배제한다." 는 큰 차이점이 있다. 내가 원하는 답을 찾을 때 까지 탐색하며, 만약 해당 길을 통해 답을 찾을 수 없다면, 가능한 이전 길까지 돌아가서 다음 길을 찾는 방법을 채택하게 된다. 주요 전략 퇴각기법을 풀이 할 때는, 전략이 중요하다. 동적계획법의 경우, 주요 전략이 "1. 점화식.. 공감수 1 댓글수 0 2021. 8. 26.
[알고리즘] 동적 계획법 / Dynamic Programming 드디어 첫 알고리즘과 관련된 게시글을 작성한다! (짝짝짝) 동적 계획법, 말만 들으면 무슨말인지 모르겠다. 느낌적으로는 뭔가 활발하게(?) 바뀌는 느낌인데, 다음과 같은 프로그래밍을 칭한다. 하나의 문제를 여러 문제로 나누어 푸는 방법 예를 들어서, 우리가 1~10까지의 합을 계산할 때, 하나의 문제는 다음과 같이 존재한다. 1+2+3+...+8+9+10 = 55 - 물론 n*(n+1) / 2 로 풀 수도 있다. 그치만 그게 중요한게 아니니까! 이를 여러 문제로 나누게 되면, 다음과 같이 바뀌게 된다. 1+2 = 3 1+2+3 = 3+3 = 6 1+2+3+4 = 6 + 4 = 10 1+2+3+4+5 = 10 + 5 = 15 1+2+3+4+5+6 = 15 + 6 = 21 ... 1+2+3+...+8+9+1.. 공감수 0 댓글수 0 2021. 8. 23.
[Java 코딩테스트] 백준 2775 부녀회장이 될테야 / Dynamic Programming 오늘은 백준 2775번 부녀회장이 될테야 풀이를 할 예정이다. 그간 이런저런 일이 많아서 블로그에 소홀했는데,, 여튼! 시작해보자 바로 본론으로 들어가서,, a층 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들 수의 합만큼 사람들을 데려와 살야아 한다. 이 때, 0층 N호에는 총 N명이 산다. → 0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다. → 1층 3호에 살려면 6명, 2층 3호에 살려면 10명을 데려와 살아야 한다. 문제에 따르면 1층 3호에 살려면 6명은 다음과 같이 구해진다 (1-1)층 1호~3호까지 사람의 수의 합 = 0층 1호 + 0층 2호 + 0층 3호 = 1 + 2 + 3 = 6명 이다. 마찬가지로, 2층 3호의 사람을 구해보면 (2-1층) 1.. 공감수 0 댓글수 0 2021. 8. 18.
[Java 코딩테스트] 백준 2292번 문제 풀이 / 백준 벌집 문제 오늘은 백준 벌집 문제를 풀거다. 한번에 맞추지 못했다. 배열 써서 풀려 했는데, 이유 모를 OutOfBounds 오류와 배열 사용으로 인한 메모리 초과 오류가 발생했다. 심지어 정답직전에 테스트 출력까지 포함해버려서 (...) 총 6번의 리트만에 정답... OutOfBounds는 도저히 내 컴퓨터에서 재현이 안된다... 1~10억까지 다 넣어봤는데..난 안난다.... 벌집 문제 문제를 딱 보면, "... 최소 개수의 방을 지나서 갈 때 ..."로 인해 Shortest Path를 찾는 것인가 싶다. 하지만 그림을 잘 보면, 규칙이 있다. 이 규칙을 찾았으면, 다음 규칙도 보인다. 벌집의 겉에는 원자의 전자껍질과 같은 구조를 발견할 수 있다. 심지어 해당 껍질은 등비수열을 이룬다. 그리고 제일 안쪽 껍질은.. 공감수 0 댓글수 0 2021. 8. 10.
[Java 코딩테스트] 백준 3052 문제풀이 / 배열 나머지 수 구하기 오늘은 백준 3052번 문제를 풀자! 해당 문제를 봤을 때, 바로 떠오른 방법이 두 가지가 있다. MkWeb을 개발하면서 HashMap을 엄청나게 썼기 때문에, 첫 번째로 HashMap이 떠올랐고, 그 다음으로 Queue를 이용한 풀이가 떠올랐다. 해시맵의 경우, 중복되는 키를 허용하지 않기 때문에 나머지를 구한 다음에 HashMap에 각각 넣어준 뒤, HashMap의 사이즈를 반환하면 끝이다. 너무 쉽기 때문에, Queue를 이용하여 문제를 풀이하려 한다. 사실 큐를 이용하나 ArrayList, Stack 등 다른 자료구조를 이용하나 풀이는 비슷하지만, 큐의 풀이가 더 직관적이기 때문에 큐를 선택했다. 이쯤 되면 나머지 수를 구하는 것은 쉬우니, 설명은 넘어가도록 하겠다. val = 입력값 % 42 우.. 공감수 0 댓글수 0 2021. 7. 25.
[Java 코딩테스트] 백준 10818 문제풀이 / 배열 없이 최소 최대 구하기 이번엔 백준 10818번 문제를 풀려한다. 이 문제는 굳이 [배열]에 분류되었어야 하나 싶은 문제다. 따라서 배열을 쓰지 않고 푸는 방법, 배열을 쓰고 푸는 방법 총 두 가지로 풀 예정이다. 우선 지금은 배열을 쓰지 않고 풀 것이다. 테스트 케이스가 몇 개인지 주어졌기 때문에, 해당 횟수만큼 숫자를 입력받고, 최대 최소를 결정하면 된다. 최솟값은 1000001, 최댓값은 -1000001로 초기화시킨다. 그 이유는 이 값들은 입력될 범위보다 크거나 작기 때문에, 어떤 수도 1000001보다 작고, -1000001보다 크기 때문이다. 위처럼 최소, 최댓값을 초기화 시키고, 앞으로 들어오는 수에 대하여 최소보다 작다면 최솟값을 갱신시킨다. 마찬가지로 최대보다 크다면 최댓값을 갱신시킨다. 이를 통해 배열에 굳이.. 공감수 0 댓글수 0 2021. 7. 22.
[Java 코딩테스트] 백준 1110 문제풀이 / 더하기 사이클 오늘은 백준 1110번 문제를 풀이하려한다. 사실 코딩 자체는 쉬운데 말이 어려워서..(일부러 어렵게 낸건가..) 그래서 주어진 문제를 내가 조금 정리해봤다. 1. 정수 base가 주어진다. (0 공감수 0 댓글수 0 2021. 7. 22.
[Java 코딩테스트] 백준 2438 문제풀이 Dynamic Programming 오늘은 별찍는 문제를 풀어보려 한다. 2438번 문제 같은 경우에는 for문을 중첩하여 풀 수 있고, 어렵지 않으니 코드를 바로 공유하겠다. import java.util.Scanner; public class Number2438 { public static void main(String args[]) { Scanner scan = new Scanner(System.in); int T = scan.nextInt(); for(int i = 0; i < T; i++) { for(int j = 0; j 공감수 0 댓글수 0 2021. 7. 19.
[Java 코딩테스트] 백준 15552번 문제 풀이 백준 15552번 빠른 A+B 풀이를 하려 한다. 이 문제에 빠른이라는 특징이 붙은 이유는 시간 제한이 있기 때문이다. Java를 사용하고 있다면 Scanner 대신 BufferedReader, System.out.println 대신 BufferedWriter를 사용할 수 있다. 무엇이 다르길래 Scanner와 System.out.println 대신 사용하라는 것일까? Scanner 대신 BufferedReader 우선 Scanner와 BufferedReader를 비교해보자. Scanner는 어떤 입력에 대하여 parse하는 것을 알 수 있다. 무슨말이냐면, 우리가 scanner를 통해 입력을 받을 때, 다음과 같은 함수들을 사용할 수 있다. int i = scan.nextInt(); byte b = s.. 공감수 0 댓글수 0 2021. 7. 18.
[Java 코딩테스트] 백준 2884번 문제풀이 오늘은 백준 2884번 문제에 대해 풀어볼 것이다. 이 문제는 Summer Time이라고 흔히 알고있는 시간 설정문제다. 실제보다 빠르게 시간을 설정하는 내용인데, 이 문제는 실제 설정시간보다 45분 빠르게 알람이 설정되면 된다. 알람은 N시 M분에 울리기 때문에, 입력 값으로 "N M"이 주어지면, 해당 시간에서 45분을 빼면 된다. 오늘은 입력 값을 받을 때 java.util.Scanner를 사용하지 않고, java.io.BufferedReader와 java.io.InputStreamReader를 사용했다. 시간에서 단순히 45분을 빼어주면 되는데, if문을 사용하여 시간 연산을 해도 된다. 하지만 알고리즘을 공부하는 우리는 시간은 분으로 표현할 수 있다.라는 특징을 이용하여 문제를 해결할 것이다. .. 공감수 0 댓글수 0 2021. 7. 18.
[Java 코딩테스트] 백준 2753번 문제풀이 오늘은 백준 2단계 if문의 2753번 윤년과 관련된 문제를 풀이할거다. if문과 관련된 문제는 주제 그대로 조건문을 잘 활용하면 된다. 특히 2753번의 경우, 조건이 이미 적혀있기 때문에, 크게 어려운 문제는 아니다. 제일 첫 조건에 대한 문장을 보면 다음과 같이 정리할 수 있다. 조건 (년도가 4의 배수다.) AND (100의 배수가 아니다. OR 400의 배수다.) 해당 조건만 보면 100의 배수가 아닌데 400의 배수가 어떻게 걸리는지 잘 모르겠다. (400은 100의 배수이고, 100은 또한 4의 배수이기 때문에..) 하지만 그 다음 문장을 보면 그 말을 확실하게 이해할 수 있다. "1900년은 100의 배수이지만, 400의 배수가 아니라 윤년이 아니다." 즉, 100의 배수면서 400의 배수.. 공감수 0 댓글수 0 2021. 7. 13.
[Java 코딩테스트] 백준 2588번 문제풀이 맥북이 도착하고 난 뒤부터 코딩테스트를 시작하려 했지만, 맥북이 생각보다 늦게와서 (아니 한국에 들어왔는데 왜 배송이 안되냐고..ㅠㅠ) 데스크탑으로 공부를 시작했다! 앞에 문제들은 이미 풀어져 있길래,, 2588번부터 하나하나 단계별 풀어보기를 진행할 예정이다. 오늘은! 그 대망의 첫 번째 문제인 백준 2588 A*B를 풀 것이다. 오늘의 문제 2588번의 문제는 두 정수 A*B를 계산할 때, 계산 과정을 모두 출력하는 것이다. 이 문제를 딱 봤을 때, 정해야 할것 하나와 알아야 할 것이 두 가지가 있는 것을 알 수 있다. 정해야 할것 1. 두 정수 중 어떤 것을 베이스로 할것인가? 알야아 할것 1. 곱해지는 수는 몇자리 수 인가? (365=3자리 수) 2. 곱해지는 수의 각 자리의 값은 무엇인가? (일.. 공감수 0 댓글수 0 2021. 7. 12.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.