신입부터의 기록

숫자가 순서대로 n 크기의 나열된 리스트가 있다. 이를 m만큼 건너 뛰며 제외시킨다고 할 때, 그 제외된 목록들을 순서대로 출력해보자. struct Node { int n; Node* before; Node* next; }; int main() { int n = 0; int m = 0; std::cin >> n >> m; std::vector v(n); for (int i = 0; i n = i + 1; } for (int i = 0; i before = v[i - 1 >= 0 ? i - 1 : n - 1]; v[i]->next = v[i +1 < n ? i + 1 : 0]; } int count = 0; in..

Dynamic Programming의 약자로 하나의 문제를 한 번만 푸는게 핵심이다. 문제를 작은 문제로 쪼개어 풀고, 푼 결과를 기억해 결과의 합으로 본래의 문제의 해를 구하는 방식이다. 대표적인 예로 피보나치 수열이 있다. f(x) = f(x-1) + f(x-2) 예제문제. 이동 비용이 있는 계단에서 n번째 계단까지 가기위한 최소 비용 구하기 #include #include using namespace std; int minCostStairs(vector& vec, int target) { int maxCoins = 999999; vector dp(target + 1, 0); // 계단을 한번에 1칸 또는 2칸 올라갈 수 있다. dp[0] = 0; dp[1] = 0; for (int i = 2; i ..

풀 때 신경쓸 부분은 다음 2가지 정도 인 것 같다. 1. 맨하탄 거리 맨하탄 거리는 피타고라스의 정리처럼 직선 거리가 아닌 실제 유효한 이동거리(건물을 뚫고 갈 수 없으니 실제 도보의 길이)임을 기억 2. 파티션의 위치 사람 사이에 파티션이 있는지 체크해야 하는데, 직선일 때(X축, Y축)와 대각선으로 있을 때만 구분해서 체크 #include #include using namespace std; // 맨하탄 거리 구하기 int getManhattanDistance(int r1, int c1, int r2, int c2) { return std::abs(r1 - r2) + std::abs(c1 - c2); } // 문자열 잘라서 테이블 만들기랑 P의 좌표만 기억해두기 void parse(const vec..

너무 오랜만에 하려고 하니까 귀찮아서 대충 짠거같다. 풀기 급급해서 깔끔하게 짜는건 실패한거 같다. 요지는 1글자부터 length/2 글자까지 반복해가면서 줄여보고 가장 짧은 글자 수를 반환하면 된다. 늘 풀면서 느끼는건 뭔가 대단한 알고리즘이 있을거 같지만 대부분은 그냥 노가다 코드 짜는 것 뿐인것같다. #include #include using namespace std; int check(string& str, int size) { string temp; string temp1; string temp2; int count = 1; // 생각해보니 매번 자르지말고 size별로 미리 텍스트를 잘라서 vector에 담아놓고 써도 될 것 같다. for (int i = 0; i < str.length() - ..

https://leetcode.com/problems/reverse-linked-list-ii/ Reverse Linked List II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 단방향의 링크드리스트와 left, right 값이 주어졌을 때, left와 right 사이에 해당하는 Node들을 reverse 하는 문제다. 너무 오랜만에 풀어서 그런가 링크드리스트 뒤집는것도 생각이 안나고 범위가 주어지니 또 헤매고.. 아는 건데도 어렵고 개념이 조금만 바뀌..

https://leetcode.com/problems/combination-sum-ii/ Combination Sum II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 임의의 정수 목록과 목표 값이 주어졌을 때, 목록의 요소들의 합으로 목표 값을 만족하는 결과 목록을 출력하는 문제다. 2021.11.07 - [코딩테스트 준비/leetcode] - 39. Combination Sum와 비슷한 유형이지만 차이점이 있는데 주요 고민 포인트는 다음과 같은 3가지다..

https://leetcode.com/problems/combination-sum/ Combination Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 고유한 정수 목록과 목표 값이 주어졌을 때, 요소들의 합으로 목표 값을 만족하는 부분 목록을 구하는 문제다. 풀어봤던 유형이지만 너무 오랜만에 풀어서 그런지 삽질을 좀 했다. 주요 고민 포인트로는 1. 요소를 중복으로 사용할 수 있기 때문에 매번 목록의 현재 위치부터 돌며 목표 값을 계산해야 했다. 2..

https://leetcode.com/problems/merge-two-sorted-lists/ Merge Two Sorted Lists - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2개의 정수 목록이 주어졌을 때, 두 리스트를 오름차순대로 합친 목록을 만들어 반환하는 문제다. 별달리 고려할만한 case는 없었던 것 같다. /** * Definition for singly-linked list. * struct ListNode { * int val; * L..

https://leetcode.com/problems/valid-parentheses/ Valid Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com (){}[]로 구성되어있는 문자열이 괄호쌍이 순서대로 열리고 닫혀있는지 확인하는 문제다. 처음엔 순서쌍 갯수만 맞으면 되는줄 알고 counting만 했어야 했는데, 열리고 닫히는 순서도 체크해야해서 stack 으로 변경해서 풀었다. class Solution { public: bool check..

https://leetcode.com/problems/subsets-ii/ Subsets II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 중복될 수 있는 정수가 포함된 목록의 모든 하위 목록을 반환하는 문제다. 일전에 풀었던 문제와 비슷하지만, 목록의 조건이 다르다. (중복) 그렇기 때문에 선 정렬 후 이전 문제와 동일한 방법으로 풀면 되는데.. 속도는 느린것 같다 ㅎ.. class Solution { public: void solve(vector& nu..