[백준] 4485 녹색 옷 입은 애가 젤다지?
2024. 2. 15. 22:37
Algorithm Study
문제 설명 링크가 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 할 때, 잃을 수 있는 최소 금액을 return https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 풀이법 bfs를 통해 문제를 풀면된다 map을 담아놓을 배열 board, 그리고 최소 소지금을 담을 배열 arr가 필요하다 큐를 사용해 bfs를 돌리는 것은 똑같으나 주의해야할 조건문은 링크가 최소 금액으로 통과해야하기 때문에 매번 '최소'가 되는 값을 찾아서..
[프로그래머스] 2단계 - 완주하지 못한 선수
2024. 2. 15. 21:57
Algorithm Study
문제 설명 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주했을 때, 완주하지 못한 선수의 이름을 return https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 map을 사용하면 간단하게 풀 수 있다 우선 participant 벡터를 순회하면서 map에 이름을 key값으로 하여 value에는 1을 넣어준다 이후 completion 벡터를 순회하면서 map의 key에 해당하는 value를 0으로 한다 모든 처리를 끝냈을 때, m..
[프로그래머스] 2단계 - 가장 큰 수
2024. 2. 7. 19:02
Algorithm Study
문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 return https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 algorithm 헤더에 있는 sort 함수를 커스텀하면 된다 sort에 들어가는 cmp 함수에서 잘 비교하면되는데, 처음에는 string 끼리 비교가 되는지 모르고 무조건 int형으로 받아서 비교하려고 했었다 그러다보니 생긴 문제점이 3과 400을 비교할 때의 문제점이었는데, 계..
[프로그래머스] 2단계 - 피로도
2024. 2. 6. 19:18
Algorithm Study
문제 설명 유저가 탐험 할 수 있는 최대 던전 수를 return https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 만약 던전이 3개가 있다면 갈 수 있는 던전들은 123, 132, 213, 231, 312, 321이 있으므로 dfs를 통해 문제를 풀었다 dfs 메소드의 cnt는 현재 간 던전의 수이고, k는 현재 피로도이다 answer는 현재 간 던전의 수의 max값으로 매번 갱신한다 그리고 던전의 갯수만큼 for문을 돌면서 재귀를 ..
[프로그래머스] 2단계 - 기능개발
2024. 2. 6. 19:13
Algorithm Study
문제 설명 먼저 배포되어야하는 순서대로 작업의 진도가 적힌 정수 배열과, 각 작업의 개발 속도가 적힌 정수 배열이 주어질 때 각 배포마다 몇 개의 기능이 배포되는지 return https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 맨 앞부터 작업이 배포가 되어야하므로, queue를 사용하여 문제를 풀었다 queue는 pair로 first는 작업의 진도, second는 인덱스를 담았다 queue가 empty가 될때 까지 반복문을 돌게 설정..
[프로그래머스] 2단계 - 전화번호 목록
2024. 2. 3. 21:33
Algorithm Study
문제 설명 전화번호를 담은 배열이 있을 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false, 아니면 true를 return https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 전화번호가 들어있는 vector를 sort하면 인접한 번호끼리 정렬이 될 것이므로, sort를 한 뒤에 string의 find()를 통해 찾으면 편하고 빠르게 찾아낼 수 있다 for문을 돌면서 해당 문자열이 앞 인덱스의 문자열의 접두어인지 find()..
[프로그래머스] 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 하라고 했으므로 이 점을 주의해야한다 근데 이 ..