알고리즘/알고리즘 문제
[python] 프로그래머스 > 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버
- 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. - 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입..
[python] 프로그래머스 > level1 > 같은 숫자는 싫어!
- 문제 설명 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면, arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다. arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다. 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요. - 제한사항 배열 arr의 크기 : 1,000,000 이하의 자연수 배열 arr의 원소의 크기 : 0보다 ..
[python] 프로그래머스 > 스택/큐 > 주식가격
1) 첫번째 시도 : pop을 사용하였고, for문 안에 모든 경우의 수를 일일이 적어주었다. -> 시간초과 2) 두번째 시도 : collections의 deque를 사용하였다. for문 안에 조건을 조금 줄였다. --> 시간초과 3) 세번째 시도 : append()를 쓰면 느리다는 글을 보고 수정 --> 시간초과 4) 네번째 시도 : 도저히 모르겠어서 구글에 찾아본 결과 pop() 또는 deque()를 사용하면 더 느리다는 글을 보고 변경 --> 시간초과 4) 이게 진짜 답!!! : break를 하기 전 이미 1을 더한 상태이므로 answer[i]가 1임을 굳이 명시해주지 않아도 됨을 깨닳음 -> 삭제 -> 성공 왜 큐/스택문제라고 굳이 해놨는지 잘 모르겠다... 당연히 pop()을 사용해야할 줄 알았다.
[python] 프로그래머스 > 멀쩡한 사각형
문제 설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solutio..
DP- 1로 만들기
- 정수X에 사용할 수 있는 연산은 다음과 같이 세 가지 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. - 어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 구하는 문제 [Top-Down 방식] int go (int n){ if(n==1) return 0; if(d[n] > 0) return d[n]; d[n] = go(n-1) + 1; if(n%2 == 0){ int temp = go(n/2) + 1; if(d[n] > temp) d[n] = temp; } if(n%3 == 0){ int temp = go(n/3) + 1; if(d[n] > temp) d[n] = temp; } retu..
[python] 프로그래머스 > level1 > 자연수 뒤집어 배열로 만들기
map(int,값)을 주면 값이 int로 변환되는 것을 알게되었다. 그리고 return에 한번에 주니 확실히 깔끔해 보이는것 같다. map과 list는 파이썬에서 자유자재로 바뀌어서 편리한 것 같다.
[python] 프로그래머스 > level1 > 두 정수 사이의 합
- a와 b중 어떤게 큰지 경우의 수에 따라 나누어 분기처리하였다. - a와 b의 크기 비교를 저렇게 간단하게 표현할 수 있었던 것을 보고 감탄했다. - 다른 사람이 짠 좋은 코드를 많으 보며 배워야겠다 생각했다. - 밤에 푸니까 너무 졸려서 너무 쉬운것만 풀지만.... 푸는게 어디야.... 내일도 쉬운거라도 하나 풀자 :)