https://school.programmers.co.kr/learn/courses/30/lessons/87390 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 N^2 배열을 만들려고 봤더니 N의 크기가 1억이었다. 이걸로 2차원 배열을 만들면 너무 커지기 때문에 배열을 모두 만들어 쪼개는 것은 불가능하다고 생각했다. 그래서 규칙을 찾아보았다. 그 결과 다음과 같은 규칙을 찾을 수 있었다. (r, c)의 값은 r, c 중에 더 큰값에 1을 더한것이다. 예를들어 (1,3)일 경우에 해당 배열에 들어갈 값은 4가 된다. 이런 방법을 사용해 left ..
https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 고민하다가 방법이 잘 떠오르지 않아 다른 사람의 풀이를 봤다. 너무 쉽게 풀었다. 비슷한 접근을 하고 있었는데 조금 더 고민해볼걸 그랬다 라는 생각이 들었다. 1. 배열의 뒤에서 부터 탐색하며 각 값을 변수에 더해준다. 2. 각각 더한 변수의 값이 하나라도 0이상이라면, 계속해서 cap 만큼을 빼준다. 3. 빼는 행위를 할 때는 정답값을 더해준다. #include #include #in..
https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 완전 탐색을 할 수 있는지시간 복잡도를 먼저 계산해 보았다. 할인율의 종류가 4가지이고, 최대 이모티콘 개수가 7개이므로 4^7이 나온다. 거기에 사람 n은 최대 100이다. 이모티콘 할인 모든 경우에 수에 따라 사람마다 각각 이모티콘을 살지, 이모티콘 플러스를 살지 계산해 주어야 하므로 4^7 X 100 이다. 계산하면 1,638,400이 나온다. 이정도면 충분히 완전탐색을 돌려도 된..
https://school.programmers.co.kr/learn/courses/30/lessons/214288 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 완전 탐색으로 풀수 있을까? 생각해보았다. 상담 유형 k가 5이고, 멘토 수 n이 20일 때, 5명은 반드시 각 지정을 해야하므로 나머지 15명을 3곳에 각각 지정하면 된다. 이 경우의 수는 15C3이고, 각 경우마다 reqs 배열을 반복돌아야 하므로 시간초과 발생 우려는 없다. 그래서 완전 탐색으로 풀어도 된다고 생각했다. 1. 상담원을 각 상담유형에 배치하는 모든 경우의 수를 구한다..
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제풀이 위상정렬 문제 접근 방법을 기억하지 못해 정답을 참고했다. 이참에 위상정렬에 대해 다시 한번 공부해 보았다. 위상 정렬은 "사이클이 없는 다이렉션 그래프" 문제를 풀 때 사용한다. 즉 순서가 정해져 있고, 이 순서가 순환하지 않아야 한다. 위상정렬은 위와 같은 조건을 가진 그래프를 "진입차수"의 개수를 이용하여 순서대로 출력하도록 또는 동작하도록 할 수 있다..
https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 문제풀이 하나씩 뺴먹어 버려서 틀리는 경우가 생긴다.. 초기 answer값을 1로 두고, 반복문 마지막 마다 정답 값을 갱신하도록 해주었다. 처음 값만 따로 입력받아 before에 저장한뒤, 감소 증가 길이를 저장할 변수를 선언하고 반복문을 돌며 단조증가, 단조감소에 따라 갈이를 늘려주거나 다시 1로만들어주면 간단하게 구현이 가능하다. #include using namespace std; int ma..
