본문 바로가기

알고리즘/알고리즘 문제 풀이

[프로그래머스] 위장 파이썬 2020. 3. 17. [프로그래머스] 위장 파이썬 문제링크 : 프로그래머스 위장 다른 사람들 코드 보니까 Counter를 사용해서 간결하게 잘 푸는 것 같은데 나는 왜 이 모양 이 꼴로 푸는지 모르겠다. 자학을 통해 빠르게 반성하고 Counter를 활용해보도록 공부를 더 하자! 문제 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 r..
[프로그래머스] 전화번호 목록 파이썬 2020. 3. 16. 문제링크 : 프로그래머스 전화번호 목록 어떠한 문제던지, 이왕이면 정렬을 해두고 시작을 하는게 답에 가까워지기 쉽다. 근데 자꾸 까먹는다. 꼭 기억해야겠다! 문제 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한사항 phone_book의 길이는..
[프로그래머스] 완주하지 못한 선수 Python 2020. 3. 16. 문제링크 : 프로그래머스 완주하지 못한 선수 파이썬을 공부하고 있어서 이에 익숙해지기 위하여 비교적 쉬운 난이도의 알고리즘 문제부터 접근을 하고 있다. 따라서 다른 사람의 풀이도 참고하기 위해 다른 사람의 풀이과정도 한번 살펴볼 예정이다. 문제 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant..
[백준 10844] 쉬운 계단 수 C++ 2020. 1. 19. 문제 링크 : 백준 10844 쉬운 계단 수 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오.(0으로 시작하는 수는 없다.) 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 입출력 예시 입력1 / 출력1 : 1 / 9 입력2 / 출력2 : 2 / 17 풀이 일일이 공책에 나열하다가 규칙을 찾고, 이를 점화식으로 만들어서 풀어야 하는 문제 첫번째 자리수에는 1~9가 올 수..
[백준 9095] 1, 2, 3 더하기 C++ 2020. 1. 15. 문제 링크 : 백준 9095 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 예시 입력 : 3 4 7 10 출력 : 7 44 274 풀이 직접 다 일일이 손으로 써가면서 만들어봐야 함. 그래서 규칙을 찾고 점화식으로 만들어서 풀면 됨. 내가 찾은 점화식은 f(n) = f(n-1) + f(n-2) + f(n-3) 이었음. 코드 #include #include using namespace std; int cache[11]; int main(..
[백준 11727] 2xn 타일링 2 c++ 2020. 1. 14. 문제 링크 : 백준 11727 2xn 타일링 2 문제 2xn 직사각형을 2x1과 2x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 예시 입력 : 2 / 출력 : 3 입력 : 8 / 출력 : 171 입력 : 12 / 출력 2731 풀이 직접 다 그려보면서 점화식을 찾았다. 점화식은 f(n) = (f(n-1) + f(n-2) * 2) 코드 #include #include using namespace std; #define MAX 1000 int cache[MAX]; int main() { int n; cin >> n; cache[1] = 1; cache[0] = 1; for(int i = 2; i
[백준 11726] 2xn 타일링 c++ 2020. 1. 8. 문제 링크 : 백준 11726 2xn 타일링 문제 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 예시 입력 : 2 / 출력 : 2 입력 : 9 / 출력 : 55 풀이 Bottom-up 방식의 DP. 규칙을 찾고 점화식을 세워 해결하는 방식이다. 그림을 그려보며 규칙을 찾아낸다. cache 배열에 3번째 인덱스까지의 값을 초기화 해준다. 내가 살짝 헤맸던 부분은 cache[i] 번째에 일단 i-1 번째 인덱스와 i-2번째 인덱스를 더해주고 나중에 답을 구할 때 10007 modulo 계산을 해주어 출력을 한 부분이 왜 오답인지 몰랐어서 헤맸다. 다시 생각해보니 반복문 안에서 modulo 연산을 해주지 않으면 이전 값이 전부 틀려버리기 때문에 반복문 안에서..
[백준 1463] 1로 만들기 C++ 2020. 1. 5. 문제 링크 : 백준 1463 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 : 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. 출력 : 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 Bottom-up 방식의 DP로 접근했다. N이 1일 경우가 최종적으로 도달해야하는 목표치이기 때문에 cache 배열에서의 1번째 인덱스에 0을 넣어주고 N이 2부터인 경우를 시작으로 입력받은 N까지의 최소 연산 횟수..

티스토리툴바