복습용

파이썬에서 알고리즘 문제를 풀다보면 리스트나 객체를 변형해야 할 일이 있다. ex) permutation 문제, 그런데 파이썬에서는 모든 변수가 다 객체이므로 리스트를 그냥 a= examplelist로 복사하면 파이썬 특성상 a는 example list를 지시하게 된다. 따라서 a.append(7)같은 명령을 할 시 examplelist도 변해버려서 문풀에 문제가 생기는 경우가 있다. 그런 경우 그냥 리스트를 참조 없이 깊은 복사하고 싶다면, a = examplelist[:]와 같이 해야한다. 혹은 .copy() method를 사용할 수도 있으나 리스트 내에 중첩된 리스트가 있는 경우 .deepcopy()를 사용해야 한다.

1. 문제 문제:https://leetcode.com/problems/reverse-linked-list/ 문제는 간단하게 이해되고 쉽게 풀리는 문제. reverse linked list 만드는거임. iterative하게 recursive하게 두 방법 모두로 풀린다. 근데, 파이썬 다중할당에 대해 이해하지 못하고 있다가 iterative way로 풀 때 자꾸 에러가 나서 기억하기 위해 포스팅. 1.1 Recursive way # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverse..

문제 문제는 해석도 크게 어렵지 않다. 처음에 N이 주어지고 다음에 N개의 가격들이 주어진다. 그 다음 라인에 갖고있는 돈 M이 주어지는데, 갖고있는 돈 M으로 딱 맞춰서 살 수 있는 책 두 쌍의 가격 pair를 반환하는 것이다. 스티븐 할림의 competitive algorithm책에서는 이진탐색풀이-input을 받고 정렬해서 각 원소 p[i]에 대해 M-p[i]를 이진탐색으로 찾기-를 제시했지만 이러면 시간복잡도가 nlgn+nlgn = 2nlgn이 나오는데, sorting 외의 nlgn작업은 예전에 풀었던 문제를 참고하면 n안에 수행할 수 있다. (UVa-10487의 아이디어 참고하기:https://hezma.tistory.com/56) 다음은 그 코드다. #include #include #inclu..

문제 문제가 조금 이해안될 수도 있는데 Sample Input과 Output이 나오게 된 근거는 다음와 같다. Query에 있는 모든 character를 처음 INPUT에서 부분수열처럼 따올 수 있으면 matched, 아니면 not matched이다. 푸는 건 A..Z a..z총 52개의 character에 대해 52개의 vector를 사용하여 처음에 주어지는 S의 각 문자별로 그 인덱스 목록을 오름차순으로 정렬한 다음, 주어지는 Query에 대해 해당 문자의 위치를 해당 문자의 vector에서 이진탐색으로 찾는 코드를 짰다. 다만 내 코드는 이진탐색의 basis case처리가 난잡할 수 있다. basis case를 두개로 잡았으니까.. 다음은 코드다. #include #include using name..

문제 문제요약: 말이 조금 어려워서 이해하기 힘들 수 있다. 문제에 필요한 정보만 써보면 다음과 같다. Input으로는 차례대로 s와 d가 주어지는데 각각은 이득, 손해를 의미하는 변수다. 그리고 이 회사의 열두달 동안 어떤 달에 이득을 봤다면 무조건 그 달에는 +s만큼 이득을 본 것이고, 손해를 봤다면 -d만큼 손해를 본 것이다. 즉 어떤 달의 earning은 +s 혹은 -d일 수밖에 없다. 이 때 5월부터는 해당 월을 포함한 지난 다섯 달의 earning을 합친 report를 작성할 수 있다. 이 때 5월부터 12월까지 총 8개의 report를 작성할 수 있는데 이 회사의 모든 8개의 report는 음수여야 한다. 이런 조건을 만족하는 1년의 손해/이익표를 생각해볼 수 있을 것이다. 이 때 손익표에서..

아직 문제를 제대로 풀지 못했다.. 답은 맞을 것 같은데(uDebug에서 확인함) TLE때문에 안되니까 꼭 다시풀거다. 코드 #include #include #include #include #include #include using namespace std; typedef vector vi; typedef vector::iterator vit; map towers int main() { int n, allowed,m,t,commonArea,temp,sum,idx,max,cases=0,people; int sign = 1; inttotal = 0; int j; vector answer; /* n:number of towers planned allowed:number of towers allowed */ w..

문제 Input이 저렇게 주어질 때 저장용량에 들어갈 수 있는 곡들의 조합 중 가장 저장용량을 꽉 채울 수 있는 곡들의 조합과 그 용량을 출력하는 문제다. 이 문제는 Input의 크기가 작아서 그냥 recursive backtracking기법을 써서 완전탐색으로 풀었다. 근데 아직 재귀적 탐색이 익숙치가 않아서 별로 효율적이지 않을 수도 있다. 다음은 코드다. #include using namespace std; int maximum = 0; int N, num_of_tracks; int time_of_tracks[20]; int Choice[20]; int BestChoice[20]; int max_choice_num; void Backtracking(int c, int num_of_choices, i..

문제 문제는 간단하다. Input은 따로 주어지지 않고, 0