[프로그래머스] 2단계 - 타켓 넘버
2024. 2. 3. 21:00
Algorithm Study
문제 설명 사용할 수 있는 숫자가 담긴 배열이 있을 때, 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 return https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 이 문제는 dfs를 통해서 풀 수 있다 dfs 함수의 매개변수는 현재 numbers의 인덱스, 현재 계산된 값, 그리고 숫자들이 담긴 벡터이다 dfs 함수의 종료 조건은 인덱스가 numbers의 사이즈와 같다면 종료하는데, 이때 총 계산된 값이 타겟 넘버와 같..
[프로그래머스] 2단계 - 튜플
2024. 2. 3. 20:36
Algorithm Study
문제 설명 특정 튜플을 표현하는 집합이 담긴 문자열 s가 표현하는 튜플을 배열에 담아 return https://dev-juelee.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F# Tistory 좀 아는 블로거들의 유용한 이야기 www.tistory.com 문제 풀이법 튜플을 찾는 문제인데 사실 이해는 못했는데 잘 보면 규칙이 있다 바로 s에서 나온 수를 내림차순 하면 된다 예시로 "{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}"가 있으면, 1은 2번, 2는 4번, 3은 2번, 4는 1번 나왔으므로 이를 내림차순하면 [2, 1, 3, 4]가 되는 것이다 따라서 map을 사용하여 해당 수가 몇번 나왔는지 c..
[프로그래머스] 2단계 - 의상
2024. 2. 3. 19:29
Algorithm Study
문제 설명 의상들이 담긴 2차원 배열 clothes에서 서로 다른 옷의 조합의 수를 return https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 clothes는 [의상의 이름, 의상의 종류]로 이루어져 있으므로 map을 사용하여 의상의 종류별로 몇개의 의상이 있는지 count 해주었다 각 옷의 조합의 수를 return 하는 것이므로 각 종류의 의상 수를 다 곱해보면 되는데 주의해야 할 것이 2개 있다 우선 곱할때 answer = 1..
[프로그래머스] 2단계 - 2 x n 타일링
2024. 2. 2. 22:41
Algorithm Study
문제 설명 2 x 1 타일이 있을 때 2 x n 직사각형을 채우는 방법의 수를 return https://school.programmers.co.kr/learn/courses/30/lessons/12900 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 전형적인 dp 문제이다 2 x 4까지 그려보면 규칙을 발견할 수 있을텐데 2 x 1은 1개, 2 x 2는 2개 이고 2 x n은 n - 1 + n - 2이다 피보나치 수열과 동일하다 그리고 문제에서 1000000007 로 나눈 나머지를 return 하라고 했으므로 이 점을 주의해야한다 근데 이 ..
[프로그래머스] 2단계 - 게임 맵 최단거리
2024. 2. 2. 22:09
Algorithm Study
문제 설명 게임 맵에서 상대팀 진영에 도착하기 위해 지나가는 칸의 최솟값을 return https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 최단 거리를 찾는 문제이므로 BFS를 통해서 문제를 풀었다 visited에는 방문했는지 여부를 체크하였고, arr는 지나온 칸의 수를 저장하였다 만일 마지막 지점인 arr[n - 1][m - 1]의 값이 0이라면 지나갈 수 없는 것이므로 -1를 리턴해주었다 소스 코드 #include #include ..
[프로그래머스] 2단계 - 행렬의 곱셈
2024. 2. 2. 21:18
Algorithm Study
문제 설명 행렬의 곱셈을 return https://school.programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 문제 그대로 행렬의 곱셈이기에 행렬의 곱셈 방법대로 3중 for문만 잘 한다면 어렵지 않게 구할 수 있다 다만, for문의 범위를 잘 체크해야한다!!! 설명은 행렬의 곱셈 방법 그대로이기에 pass~~ 소스 코드 #include #include using namespace std; vector solution(vector arr1, vector a..
[프로그래머스] 3단계 - 정수 삼각형
2024. 2. 1. 22:31
Algorithm Study
문제 설명 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합 중 최댓값을 return https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 아무래도 삼각형은 dp의 대표적인 문제 같다 우선 dp문제이므로 배열을 하나 선언해주고, 삼각형의 맨 꼭대기 숫자를 넣어준다 이후 for문을 돌면서 값을 넣어주는데 맨 왼쪽이나, 맨 오른쪽 값이면 위의 숫자를 바로 넣어준다 만일 y좌표가 i고 x좌표가 j일때 맨 왼쪽 값이면, dp[i..
[프로그래머스] 2단계 - 프로세스
2024. 1. 30. 19:17
Algorithm Study
문제 설명 운영체제가 우선순위 큐로 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 return https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 문제 설명에도 나와있듯이 queue를 통해서 문제를 풀었다 우선순위대로 실행이 되고 특정 프로세스의 위치를 알아야 하는 것이 핵심이었다 우선 queue에 vector에 있는 값들을 순서대로 넣어준다 그리고 우선순위를 알기 위해 vector의 값들을 내림차순 정렬을 해준다 특정 ..
[프로그래머스] 2단계 - 할인 행사
2024. 1. 30. 16:58
Algorithm Study
문제 설명 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 하는 마트에, 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하고자 할 때 원하는 제품을 모두 할인 받을 수 있는 회원 등록 날짜의 수 return https://school.programmers.co.kr/learn/courses/30/lessons/131127 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 map을 사용하여서 할인하는 제품과 할인하는 날짜 수를 넣고, 확인하는 방식으로 문제를 풀었다 map을 잘 사용해보지 않아서 ..
[프로그래머스] 2단계 - n^2 배열 자르기
2024. 1. 30. 16:00
Algorithm Study
문제 설명 정수 n, left, right가 주어졌을때 여러 과정을 거쳐 만들어진 1차원 배열을 return https://school.programmers.co.kr/learn/courses/30/lessons/87390 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 입출력 예시를 보면서 처음에는 그냥 배열을 하나 다 만든다음에 left, right 범위만 잘라서 return 했다 그랬더니 시간초과가 나버렸기에 수식을 통해서 문제를 풀어야겠다고 생각했다 수식을 알아내기 위해 우선 해당 인덱스의 좌표 값을 알기 위해 이것저것 하며 알아낸 결과..