목록월급쟁이 알고리즘 (7)
IT월급쟁이의 삶
[문제] 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재, 손님에게 거스러 줘야 할 돈이 N원일 때 거스러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. [풀이] 이 문제의 핵심은 탐욕법 사고로 접근하는 것이다. 탐욕법은 "현재 상황에서 지금 당장 좋은 것만 고르는 방법" 인데 가장 최소를 구할려면 가장 큰 거스름돈 부터 거슬러 주면 된다. 즉, 가장 큰 화폐 단위부터 거슬러 주면서 카운트 하면 된다. with Python -- 추후 업데이트 with C++ int main(){ int n = 1260; int coin_type[4] = {500, 100, 50, 10}; in..
[문제] 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. [제한 조건]..
[문제] 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다. 다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다. "네오"는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디..
1008번 문제는 단순히 나누기만 하면된다. 따로 설명할 것도 없고, 블로그에 남기는 것 조차 부끄럽지만, 어쨌든 흔적이니깐 소스를 첨부해본다. 아? 근데 왜 정답률이 33%밖에 안될까? 그냥 나누기만 하면 되는데? 이러다가 나도 틀렸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그리고 문제를 다시 보았다. 출력조건에 보면 "실제 정답과 출력값의 절대오차 또는 상대오차가 10의 -9승 이하면 정답이다" 라는 조건이 있다. 즉, 오차가 소수점 아래 9번째자리 까지는 있으면 안된다는 말이다. 그렇게 부라부라 int형으로 선언했던 것을 double형으로 선언하고 했더니 성공했다. 내가 알기론 double형은 소수점이하 9째자리까지 정확한걸로 들었다.. 맞나? 이번계기로 다시 데이터타입에 대해서 공부하고 포스팅 해야겠다...
문제를 보면 뭔가 복잡하게 막 나열되어 있는 것을 볼 수 있다. 하지만 피보나치의 원리만 이해한다면 제시되어 있는 소스코드가 무엇인지 알 수 있다. 그럼 문제를 풀기 전, 피보나치 수열이 무엇인지 부터 알아보겠다. ========================================================= 피보나치 수열이란? 단순하게 수를 표현해보면 A, B, C, D, E, F 라는 수가 나열되어 있다. 이때 피보나치 수열이라면 일정한 조건을 가지고 있는데, 바로 앞의 두수의 합이 다음 수가 된다는 조건이다. 그래서 이런 피보나치 수열은 기본적으로 첫번째, 두번째 수는 1로 정해져있다. 그 다음수는 앞의 두수를 더하여 만들어 낼 수 있다. 이 논리로 피보나치 수열을 아래와 같이 나열할 수 있..
기본적인 A-B 연산 알고리즘 문제입니다. 앞서 1000번 문제와 마찬가지로 간단하기 때문에 바로 넘어가겠습니다~ 소스 #include using namespace std; int main(){ int a, b; cin >> a >> b; cout
예전부터 백준 알고리즘을 틈틈히 풀어왔었다... 그땐 티스토리를 하기전.. 이제부터라도 알고리즘 푼 문제를 기록 하기로 마음 먹었다~ 나는 무조건 C++로 알고리즘을 푼다. 왜냐하면 라이브러리가 잘되어있기 때문.. 그래서 개발은 자바로 주로 하더래도 알고리즘은 C++로 한다. 쨌든, 백준 1000번 문제는 그냥 더하기만 하면된다. 소스 #include #include using namespace std; int main(){ int A=0; int B=0; cin >> A >> B; cout