본문 바로가기

프로그래머스 풀이

 (85)
프로그래머스 - 피로도 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 순서를 1 2 3, 2 1 3, 3 1 2 등 어떤식으로 진행해야할지 정하는 문제. 그리디하게 생각할 수 없고 모든 것을 해보는 것이 정답인 경우이다. 겨우 N이 8까지 밖에 없는 경우라서 가능하지만 숫자가 더 커지면 다른 방법을 찾아야한다. 이 문제는 dfs로 순열을 만드는 문제와 유사하다. dfs로 순열 조합을 다룰 줄 알아야한다. #include #include #include using n..
프로그래머스 - 행렬의 곱셈 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 행렬의 곱셈은 DP를 사용해서 최적화 할 수도 있다. 물론 이건 2개만곱하는 거니까 이런것 까지는 필요 없지만 DP포함이 되었다면 레벨 2가 아니겠지. 행렬의 곱셈을 할 때, answer[a][d] = A[a][b] * B[c][d] 에서 b = c 임을 눈치챈다면 쉽게 풀 수 있다. 이런 규칙을 찾는 문제는 손으로 써서 관찰하는 것이 규칙을 찾기 편하다. 물론 머리가 좋으면 바로 눈치챌 수도 있..
프로그래머스 - 다단계 칫솔(C++) https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백엔드 직무 데브 매칭 기출 문제이다. 트리를 자식부터 반대로 타고 탐색해야하기 때문에 부모가 자식의 정보를 갖고 있게 하지 않고 자식이 부모의 정보를 갖고 있도록 해야한다. 그리고 각 노드의 이름이 문자열이기 때문에 문자열을 숫자로 변환하여 map으로 관리해주었다. 1. 문제 조건 - 돈을 번 노드부터 시작하여 그 노드의 최상단 부모까지 타고 올라가야한다. - 그러면서 번 돈을 분배하는 작업을 ..
프로그래머스 - 불량 사용자 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 백트래킹 조합문제이다. 문제를 해석하는 것이 가장 중요하고 해석만 하면 조합을 구할 줄 알면 쉽게 풀 수 있다. 나중에 한번 더 풀어보면 좋을 문제 #include #include #include #include #include using namespace std; vector user, ban_user; set answerset; bool check[8] = {false,}; bool banCh..
프로그래머스 - 숫자 게임 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12987?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr A팀의 순서를 바꿔도되는데 이것을 생각해내지 못했던 문제. 어렵지 않은 문제인데 아이디어가 잘 안떠오른다 어떻게 해야 이런 사고력을 늘릴 수 있을까... #include #include #include #include using namespace std; int solution(vector A, vector B) { int answer = 0; sort(A.rbegin(),..
프로그래머스 - 야근지수(C++) https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 풀며 생각의 순서는 이러했다. 1. 내가 잘 하는 문제 유형으로 바꿀 수 있을까? dfs, bfs 등등 2. 아니라면 뭘로 바꿀 수 있을까. 이 문제는 우선 가장 최소화 시키는 것이 목적이다. 그리고 n이 백만으로 크다. 그렇다면 DP, 이분탐색, 파라메트릭을 사용할 수 있을까? 3. 모두 아닌 것 같은데 그렇다면 단순 구현인가? 4. 단순 구현이라 하면 어떤 자료구조를 사용할 수 있을..
프로그래머스 - 네트워크(C++) https://school.programmers.co.kr/learn/courses/30/lessons/43162# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 봤을 땐 행렬을 그대로 두고 그래프 순회로 풀 수 있을 것 이라고 생각해서 백준의 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc..
프로그래머스 - 최고의 집합(C++) https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 문제다. 코딩테스트 1번이 딱 이정도로 나오는 느낌. 다만 처음 읽으면 어떻게 해야할지 감이 안잡힐 수 있다. 먼저 최고의 집합이 되려면 N개의 숫자의 합이 S가 되어야한다. 즉 N개의 숫자들은 N이 3이라고하면 (N-2, 1, 1), (N-3, 1, 2) ... 이런식으로 매우 많다. 그리고 두번째 조건인 곱했을 때 최대가 되게 하려면 각 원소들간의 차이가 없어야한다. 즉 원소들은 (S ..

티스토리툴바