오늘 푼 문제 : 1325, 10815, 10816
1325 (효율적인 해킹)
처음 접근 :
이차원 리스트를 만들어서 단방향 그래프를 만들어서 dfs로 접근하되 메모이제이션 기법으로 이미 했던 작업을 또 하지 않음으로써 시간을 줄이겠다는 마인드였다.
잘못 접근한 부분 :
처음에 생각한 메모이제이션을 쓸 수 없었다. 예를 들어, 1-3-4-5-1 이렇게 해킹이 된다고 하면, 처음 접근 방법대로라면, 3번째 인덱스에는 2가 기록되어야 했다.(왜냐하면 3-4-5 이고, 1은 방문한 노드이므로 제거. 결국 2가 기록되어야 했음). 하지만 사실 3번째 인덱스에는 3이 기록되어야 맞다. 따라서 이 경우 때문에 메모이제이션 기법은 포기했다.
잘못 푼 부분 :
dfs를 구현할 때, base case로 "li[index].size() == 0"를 만났을 경우 0을 리턴하도록 했다. 논리적으로 잘못된 부분이다.
문제 해결 :
단순 dfs로 구현했다.
알게 된 부분 :
1.
파이썬으로 재귀를 돌리려고 하면, 최대 깊이가 제한(1000 이라 함)이 있어서 반드시 "sys.setrecursionlimit(100000)" 코드를 추가해 줘야 한다.
2.
g++로 컴파일시 auto 키워드를(type inference) 쓰려고 하면, 컴파일 시에 std=c++11 를 붙여줘야 함. (ex > g++ -std=c++11 hacking.cpp)
(default가 c++ 98 이기 때문인 것으로 예상. auto는 c++11 부터 지원)
3.
vector에서 인덱스 비교시에는 size_t 사용 (feat.종환)
10815 (숫자 카드), 10816(숫자 카드2)
두 문제가 비슷하기 때문에 묶었움
처음 접근 :
접근은 두 문제 동일. 인덱스로 접근하는데, 음수는 양의 정수 최대값 +(음수 값의 절대값) 로 인덱스 접근함.
잘못 접근한 부분 :
[10815] 출력은 1,0 만 하면 되기 때문에 bool형 배열을 쓰면 됐지만, 처음에는 int 형 배열로 접근했음.
잘못 푼 부분 :
[10815] 카드의 갯수(500,000)가 아니라, 카드에 적혀있는 수로 배열의 크기를 할당했어야 했다.. 문제 제대로 읽자
문제 해결 :
두 문제 모두 인덱스 접근으로 해결
알게 된 부분 :
지역 변수는 스택에 선언되는데, 스택의 공간은 한정적임. main문 안에 크기가 20,000,000인 배열을 선언해 버리면 런타임 에러가 발생할 수 있음. (그것도 int형 배열로 선언하면 20,000,000 * 8 bytes나 됨) 따라서 전역 변수로 선언하여 공간이 넓은 정적 데이터 영역에 할당하면 런타임 에러가 발생하지 않는다.
