뮤츠의 프로그래밍 이야기

제가 그림 그려가며 열심히 설명할 자신이 없어서... 보고 배운 유튜브 영상으로 링크합니다. https://www.youtube.com/watch?v=QleeV_ipB7w 그 이전에 그래프와 인접행렬 개념 등도 알고있어야하는데, 이 부분도 검색하면, 그림을 동원해서 설명한 친절한 블로그들이 넘쳐납니다. (예전에 다른 문제풀때 제가 본 사이트를 링크하고 싶었으나...다시 찾으려니 알 수가 없네요. 유사한 사이트는 구글링하면 수도없이 나옵니다. -_-;;)

입출력 예제는, 스크린샷이 길어질 것 같아 생략...자세한 부분은 문제 링크를 참조. https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr BFS로 접근해야겠다는건 알았는데, '인접행렬' 개념을 잘 몰라서, 풀이를 보고 이해하게 되었다. 그 외에도 인접리스트도 쓰는 모양이나, 개인적으론 각 노드의 부분을 서치하기엔 인접행렬이 좀 더 효율적으로 느껴졌다. 풀이1. BFS import java.util.*; class Solution { int[][] ..

처음엔 백준에서 풀던 문제와 비슷해서, 그리디인가? 생각을 했습니다. https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디가 맞긴 맞는데...조금 문제가 달랐어요. 위 백준 문제는 회의실 하나로 최대한의 회의를 잡기, 해당 프로그래머스 문제는, 모든 회의를 잡는 최소한의 회의실 수를 구하기. 처음에 생각했던 발상은, 백준 문제풀이때의 감각대로 정렬한 뒤 priorityqueue를 활용해 정답을 구하는 쪽이었는데, 접근법은 맞았으나 최종코드를 작성하지 못했습니다. priorityqueue로 어떻게 구분해서 max값을 구하는지? 이 부분에 대한 이해가 부족했어요..

꽤 오래전에 풀었으나, 수수께끼(?)가 최근에 풀려, 이제야 포스팅합니다. 처음에는 반복문인줄 알고, 간단하네~ 하면서 반복문으로 풀었습니다. class Solution { public int solution(int a, int b, int n) { // a : 빈병의 수 b : 바꿔주는 새로운 콜라의 수 n : 초기 콜라의 수 int answer = 0; while(n>=a) { int k = n/a*b; n = k + n%a; answer+=k; } return answer; } } 문제의 로직을 그대로 반복하여, 더이상 교환이 불가능할때까지 반복하는 방식입니다. 충분히 좋은 효율을 보여주긴 하지만, 반복문의 시행횟수가 올라갈수록 연산이 많아지는 구조로 되어있습니다. 그리고 충격의 모범답안... cl..

조건 자체가 어렵지는 않았다. 단, 규칙성을 찾아야해서 수학문제에 가까웠다. 처음에는 규칙성을 찾을 수 없어서, 완전탐색으로 구현하였다. 범위를 보고, 이중반복문이 들어가면 안될거라는걸 직감했는데, 예상대로였다. class Solution { public long[] solution(long[] numbers) { long[] answer = new long[numbers.length]; for (int i=0; i>>2; } return answer; } } ??? ?????? 미쳤다. 말도 안되는 효율을 보여주었다. 코드의 길이와 가독성, 실행효율 모두 압도적이다. 메모리 사용이 아주약간 높기는 했다. 왜 이게 정답일까? 그걸 잘 모르겠다. 한번 곱씹어보는데, 처음에 1을 더한다. 최솟값은 +1값이기..

오랜만에 포스팅한다. 다름아닌, 모범답안을 기록하기 위해... 문제를 보고 처음에 들었던 생각은, '정규 표현식을 이용하면 좋지 않을까?' 였고, 이후 떠오른 생각은 '정규 표현식을 사용할 수 없다면, 반복문을 통해 숫자가 처음 나오는 인덱스, 다시 숫자가 나오지 않는 인덱스를 구하면 되지 않을까?' 였다. 정규 표현식은 암기하고 있지 않기도 하고, 어차피 chatgpt로 딸깍 물어보면 알려주긴 하니까...후자로 풀어보기로 했다. 중간에 효율적인 방법을 고민하다 정답을 이것저것 참조했는데, 배열보다 생성자를 활용하는 방법을 썼다. 배열이 좀 더 효율적인 느낌은 들지만, 자료형이 다른 변수들을 묶어 관리하기에는 아무래도 생성자를 활용하는 편이 편했다. 객체지향적인 깔끔한 코드가 되는 것은 덤. 내가 본 정..

문제 자체의 발상은 크게 어렵지 않았다. 자릿수를 하나씩 늘려나가면서, 가장 마지막 자릿수에 숫자를 붙이는 식으로 생각하였다. 문제는 엉뚱한 곳에서 일어났는데, n이 100까지 가는, 100자리 수가 대상이었기에 경우의 수를 따지면서 숫자가 굉장히 커졌다. 예제가 부실하여 직접 계산하거나 전체를 돌려볼 수 밖에 없었는데, 그냥 무지성 제출했던게 화근이 되었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static Double[][] dp; // 마지막 수와 자릿수에 따른 계단수의 갯수를 저장할 배열. public static void main(S..

기본 로직은 동적 계획법 패턴과 유사하다, 단, 앞에서의 최댓값이, 최종 최댓값 경로를 보장하는 것이 아니다. 따라서, 밑 지점 (끝지점) 부터 역순으로 나가는 Top-Down 방식을 활용해야 한다. '행별로 최대값' 을 구하는게 아니라, '(행, 열 좌표열을 가진)특정 지점에서의 최댓값을 구한뒤, 마지막 행에서 최대값을 구해주면 된다. 아무튼, 로직은 맞았는데 왜 틀렸냐고 한다면... import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] tri; static int[][..

동적계획법은 메모이제이션이라는 기법을 이용해서, 반복문이나 재귀를 돌리면서 이미 알아낸 값을 기록해가며 문제를 해결하는 기법이다. Top-Down 방식으로 하는 경우, 재귀를 이용해서 한계단씩 내려가는 방법을 쓰게 되고, Bottom-Up 방식으로 하는 경우, 반복문을 이용해서 처음부터 하나씩 올라가는 방법을 쓰게 된다. 문제를 풀 때, 아직 동적계획법에 대한 감이 잡힐랑 말랑 해서, 일단 백트래킹으로 풀었으나, ide에서는 작동하였음에도 백준에서는 시간초과가 나와버렸다. 값을 기록하지않고, 구했던 값을 또 구하다보니 성능에서 차이가 생긴 모양. 1. 백트래킹으로 푼 풀이, 시간 초과. import java.io.BufferedReader; import java.io.IOException; import ..

풀면서 어려운 부분이 있었던건 아니었는데, 한번 틀려서 띠용? 하고는 해결법을 찾음. 나는 반복문을 돌리지 않고, 고교때 배웠던 합공식 n(n+1)/2로 풀었는데, 이걸로 풀다보니, int로 받은 매개변수들끼리 계산하면서 int를 넘어 overflow 하는 경우가 생김. 따라서, 맨 처음 인자값을 long으로 미리 바꿔줘야 한다. 무식하게 반복문돌려서 하나씩 더하면, 이런 걱정 없음. class Solution { public long solution(int price, int money, int count) { long answer = 0; long cost = (long)price * count * (count+1) / 2; if (money