본문 바로가기

알고리즘풀이

[프로그래머스] 멀쩡한 사각형 c++ 2020. 8. 10. [프로그래머스] 멀쩡한 사각형 c++ 문제 링크 : 멀쩡한 사각형 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 �� programmers.co.kr 문제설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재..
[프로그래머스] 완주하지 못한 선수 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가 올 수..
[백준 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 연산을 해주지 않으면 이전 값이 전부 틀려버리기 때문에 반복문 안에서..

티스토리툴바