https://school.programmers.co.kr/learn/courses/30/lessons/258712 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic string과 숫자를 가지고 놀아야 하기 때문에 map자료구조가 적절할 것이라고 판단했다. friends배열에 있는 순서대로 인덱스를 매겨주고 서로 몇번 주고받았는지 확인했다. 핵심은 2중 for문에 있는데, 이중 계산을 막기 위해 선물을 받는 경우만 계산해줬다 코드는 아래와 같다. 2. Code #include using namespace std; map nameToIdx; i..
Programmers
https://school.programmers.co.kr/learn/courses/30/lessons/250137?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 그냥 구현문제 부분문제를 나누자면 1. 몬스터에게 공격받을 때 2. 몬스터에게 공격 안받을 때 (붕대 감아야 함) 부분문제를 나눠서 상황에 따라 구현하면 실수를 줄일 수 있다. 2. Code #include #include #include using namespace std; int solution(vector bandage, int health, vect..
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 1. Logic - 해당 문제는 주어진 배열을 앞에서 부터 풀이하게 될 경우 최댓값까지 배열을 돌고 또 최댓값을 구해서 배열을 돌아야해서 이중 for문을 사용하게 되어 시간복잡도가 O(n^2)이지만 뒤에서부터 풀이하게되면 다음값을 보고 최댓값인지 알 수 있기 때문에 O(n)으로 풀 수 있다. 최악의 경우를 생각 해 봤을 때 10000 *999999 곱하게되면 int 의 범위를 훨씬 넘..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. Logic - 처음에 구현한 방식은 DP테이블을 세우고 재귀함수로 문제를 풀었었다. 동전의 sum 값과 얼마짜리 동전을 사용했는지를 표기하는 DP테이블을 구성했고 dp[10001][101]로 구성했다 이렇게 되면 n * k만 해도 4MB가 넘어가므로 당연하게도 메모리초과가 났다. 이 다음 생각한 방법으로는 상향식으로 흔히 점화식을 세워서 푸는 방법으로 풀었다. 항상 재귀로 풀으려고해서 점화식을..
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. Logic - 분기가 +, -로 이루어지기 때문에 2개의 재귀를 들어가야한다. - DP Tabel을 생성할때 처음 인자는 sum의 범위, 두번째 인자는 몇번째 인덱스를 돌고있는지 체크한다. 2. Code #include using namespace std; int n; vector vec; long long dp[30][101]; long long solve(int sum, int c..
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 1. Logic 1. 인접한 두 칸에 있는 사탕을 서로 바꿔야하기 때문에 swap함수를 사용해서 값을 변경해 준다. 2. 같은 색의 사탕을 먹어야 하기 때문에 현재칸과 그 다음칸을 비교하면서 진행하며 cnt를 올려준다. 3. 최댓값을 갱신해준다. 2. Code #include using namespace std; vector vec; int n; int calc() { // 가로 int ans = -92735; for(int i = 0; i < n; i++) { int cnt = 1; for(int j = 0; j..
https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 1. Logic 2가지 상황으로 분할해 볼 수 있다. 1. n이 99이하인 경우 2. n이 100이상인 경우 - 1 ~ 99까지의 수는 항상 등차수열을 이루기 때문에 99이하의 숫자가 나오게되면 즉시 숫자를 리턴한다! - 100이상의 숫자는 어짜피 999까지 비교하면 되기 때문에 3부분으로 나눠서 100자리 10자리 1자리 숫자를 각각 비교한다. 2. Code #include using namespa..
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 1. Logic - 받은 숫자를 오름차순으로 정렬한다. 처음 숫자부터 더해가며 sum > vec[i] 일 경우 수를 조합하여 구할 수 있고 sum > n; for..
https://www.acmicpc.net/problem/10448] 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 1. Logic - 세 합이 100을 넘는 경우는 n이 45인경우부터 1000을 넘기 때문에 45까지 for문을 돌며 합을 계산해 놓는다. - 계산하고 싶은 삼각수를 받은 후 3중 for문을 돌며 찾게되면 값을 반환한다 2. Code #include using namespace std; int triangleNum[1001]; bool FindTri(int n) { for(int i =..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. Logic - 딱 봐도 BFS지만 나눠야 하는 부분이 3가지이다. 1. 조건을 같지 않을때로 걸고 BFS를 돈다 2. 이후 배열을 순회하며 R 또는 G중 원하는 것을 선택하여 R > G / G > R로 변경해준다. 3. 다시 BFS를 돈다. 2. Code #include using namespace std; int n; vector vec(101, ""); vector vis(101,..
