코테

5430_AC_골드5:

 

1. reverse() 매번하는것은 시간 복잡도 너무 큼.

2. lst = [1,2,3] 일때 ','.join(map(str, lst)) 하면 리스트를 문자열로 쉽게 바꿀수 있다. 보통은 lst 안에 문자들만 있을때만 join이 가능한데 숫자들도 map(str, lst)해줘서 map 앞에 있는 형태로 매칭시켜준다.

 

 

 

7569_토마토_골드5:

 

1. 어떻게 횟수 계산? 거리로 생각하고 노드 사이 거리가 전부 1이므로 bfs로 해결 가능

2. 큐의 pop을 어디서 부터 어떻게 시작? -> 처음 1인것들 전부 큐에 넣고 시작 

3. 어떻게 익지 않은 토마토를 판별? -> 다 마친후 0이 있는지를 판별... 괜히 어렵게 생각했네

 

 

 

1927_최소힙_실버2:

 

1. 힙 사용법에 대해서 맨날 까먹는다

2. import heapq, q = []

3. heapq.heapush(q, value), heapq.heappop(q), heapq.heapify(q)

4. value항에는 특정 값이 아니라 리스트가 들어갈수도 있다. 이때는 리스트의 맨 앞항을 기준으로 정렬(다익스트라에서 사용)

 

 

 

11723_집합_실버5:

 

1. input().split() 의 반환값은 list다

2. input().split() 의 input으로는 꼭 여러 단어가 들어올 필요가 없다. 1만 들어와도 ['1']이 반환.

3. 두개일때는 a, b = input().split() 하면 되는데, 한개일때는 ['1'] 형태이므로 input().split()[0] 해줘야겠네

 

 

 

1931_회의실 배정_골드5:

 

1. 처음에는 for문 두번돌면서 모든 경우의 수를 확인하고 최대값을 비교해서 얻으려고 함.

2. 그러나 정렬을 회의가 끝나는 시간에 맞게 하면 for문 두번 돌지 않아도 한번의 for문 만으로 최대값 얻을 수 있다.

    -> 정렬 한번으로 데이터 순서를 바꿔서 문제를 편하게 바꿈. 이것이 greedy 유형을 푸는 방법인가.

 

 

 

1764_듣보잡_실버4:

 

1. 집합 자료구조에서 교집합 -> a&b. 차집합 -> a-b

2. input()의 결과는 \n을 포함하지 않는데, sys.stdin.readline() 결과는 \n을 포함한다. 그래서 보통 strip()을 해줘서 제거.

 

 

 

18870_좌표압축_실버2:

 

1. 자료압축이란 넓은 범위에 걸쳐있는 data를 우선순위 인덱스로만 나타내려고 한거

2. set으로 묶어서 중복 없애고 정렬하고 index 순으로 해쉬처리하면 편하게 푸는듯

 

 

 

2565_전깃줄_골드5:

 

1. a기준으로 정렬하고 b가 가장 길게 증가하는 수열을 구하면 된다. dp값은 최종 그 수열에서 가장 긴 수열

2. b값을 비교하며 돌면서 이전 b값보다 클때만 그 dp값이 갱신된다.

3. 이때는 dp로 풀게되는데 dp[3]을 구하기 위해서 dp[0], dp[1], dp[2]를 비교해서 최대값을 구하고 거기서 + 1 한다.

    즉 기존 가장 긴 증가수열을 구해서 거기서 1을 더하는것이다. 이해가 상당히 안갔는데 드디어 이해갔다.

 

 

 

9019_DSLR_골드4:

 

1. visited 범위를 어떻게 정해야할까 고민을 많이했는데 생각해보니까 표현할수 있는 범위가 0~10000 이다.

2. queue에다가 표현한 수와 그 수의 command를 같이 넣어줬다 빼면 된다.

3. 원래 bfs는 격자판 위에서 4가지 방향식으로만 하는줄 알았는데 이렇게 뻗어나가는 방향을 보니까 신기하다.

 

 

 

15652_N과M(4)_실버3:

 

1. 중복조합 문제인줄 알았음 근데 백트래킹이였음. 완전탐색이 아니라 범위를 제한해서 잘 풀어야 했음.

2. 원하는 길이가 요구한것을 만족하면 끝. for문을 낮은값부터 차례대로 가므로 오름차순 만족.

 

 

 

9251_LCS_골드5: 두번 풂

 

1. 전깃줄 문제처럼 A에 대해서만 dp 표를 만들어서 풀려고 했는데 안됨.

2. 알고보니 이 문제는 dp 값을 A와 B를 동시에 고려하면서 푸는게 편하므로 2중 배열을 만들어서 푼다.

3. 이렇게 하면 두 문자를 비교 했을때 같을때는 그 이전(A-1, B-1)까지의 LCS값 + 1 해주면 되고

    다를때는 A에서 한문자 뺀값과 B의 LCS 또는 B에서 한문자 뺀값과 A의 LCS를 구해주면 된다.

4. dp 문제는 어려운것 같다. dp 배열을 어떻게 만들지, 관계를 어떻게 할지가 어렵다. 여기서는 A-1, B-1을 고려해야하므로 0일때 배려도 고려해야한다. (문자길이 + 1)(문자길이 + 1) 배열을 만들어주는것이다.

 

 

 

12865_평범한배낭_골드5:

 

1. 현재 가방에서 나온 값 + 이전 저장된 값이 최대일 경우 vs 이전 가방에서 나온값이 그대로 최대일경우

2. i-1 인경우를 해야하므로 마찬가지로 dp가 0,0 일때도 필요

3. 이중 리스트로 dp 테이블을 만들어야 하므로 어려움

 

 

 

1991_트리순회_실버1:

 

1. node를 클래스로 만들어서 node 틀을 만든다.

2. tree는 딕셔너리로 만든다. key값을 노드로 하고 value를 class node를 저장한다. 

3. tree의 노드 하나를 정해서 전위, 중위, 후위에 관한 함수를 만든다. 이때 이 함수들은 print의 순서에만 차이가 있다.

4. 왼쪽 들어가기전에 print, 왼쪽 다 마치고 print, 왼쪽 오른쪽 다 마치고 print의 차이

 

 

 

11660_구간합구하기5_실버1:

 

1. 시간 초과 너무 남. dp 테이블을 미리 만들기. 왼쪽 위부터 오른쪽 아래로 차례로 더해지게 만드려고 했음.

2. dp[i][j] = data[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] 즉 왼쪽 값과 위 값과 그 상태의 값을 더해서 dp값을 채우려고 함.
    근데 근데 왼쪽값과 위 값에 왼쪽 위 대각선 값을 둘다 포함하고 있으므로 중복되는것을 막기 위해서 빼줌

3. dp table에서 부분합을 구하기 위해서 사분할된 사각형의 왼쪽 위아래와, 위 왼쪽 오른쪽을 빼주고, 중복으로 빼진 왼쪽      위를 더해준다.

 

 

 

1967_트리의지름_골드4:

 

1. 다익스트라로 풀어서 노드마다 for문돌고 최대값 구하면 되는줄 알았는데 아니다.

2. tree기반은 사이클이 없기떄문에 한번 구한 거리가 끝까지 유지되므로 다익스트라 쓸 필요 없다. 가중치 있으면 bfs로도 충분

3. 지름은 루트 노드에서 가장 긴거리까지 노드 구하고, 다시 거기서 가장 긴 노드를 구한게 지름이다.

 

 

 

2206_벽 부수고 이동하기_골드3:

 

1. distance에 벽 정보까지 저장해라. 즉 삼중리스트로 만들면 된다.

2. 벽 정보에 상관없이 bfs라서 먼저 n-1, m-1에서 나오는 값이 최소값 

 

 

 

1865_웜홀_골드3:

 

1. 음수 간선이 있을때 최단 거리 찾기는 다익스트라로 안된다. 벨만포드나 플로이드 워셜 알고리즘으로 풀어야 한다.

2. v^3을 보이는 플로이드는 이번 문제에서 적용불가. 벨만포드에 대해서 이해하느라 오래걸림.

3. 인접 리스트나 인접 행렬로 그래프를 표현하는게 아니라 그냥 엣지 리스트로 받아들임.

4. N개의 정점에 대하여 N-1번 반복하면서 각 정점에 대한 최단거리를 확인함. 그리고 N번째에 다시 확인했을때에도 갱신이 되는        정점이 있다면 음수 사이클이 있다는것.

5. 원래 아예 동떨어진 그래프이면 정점간 거리를 완전 무한으로 표현하는데 이 문제는 정점간에 어쩄든 연결되어있다고 판단. 그냥      큰 수로 표현

 

 

 

11657_ 타임머신_골드4:

 

1. 1번 노드랑 연결되지 않은 점들에 대해서는 판별하지 않기 위해서
    if distance[cur] == 1e9:  # 여기 추가 continue 를 추가해준다.

 

 

 

11444_피보나치수6_골드2:

 

1. F2n​=Fn​(Fn−1​+Fn​+Fn−1​)=Fn​(Fn​+2Fn−1​)

2. F2n+1​=Fn​Fn​+Fn+1​Fn+1​=Fn2​+Fn+1

3. 도가뉴 항등식 그냥 외워라. 저 큰 범위를 담을 수 없으니 devide & conquer 해서 푸는거 같다.

    시간복잡도가 O(n)에서 O(logn)이 되는것이다.

 

 

 

1918_후위표기식_골드2:

 

1. 연산자에서 우선순위를 두고 나가게 하기 위해서 복잡했음. *나 /가 +나 - 보다 먼저 나가야함.

2. 그 연산자들 위에 최우선적으로 (나 )를 고려해야함.

3. for문을 다 돈 이후에도 stack에 연산자가 남아있는 경우가 있을 수 있어 마지막 pop() 해줘야함

 

 

 

2096_내려가기_골드5:

 

1. dp table을 그대로 쓰면 메모리 초과 문제가 발생하였음.

2. 슬라이딩 윈도우 기법이라 해서 매번 dp table을 전부 기록하는게 아니라 이전 table들은 그냥 없애는 방법을 사용.

 

 

 

1043_거짓말_골드4:

 

1. 거짓말쟁이들을 몰아넣은 set을 써서 for문을 m번만큼 두번 도는 방법이 있다.

2. 거짓말쟁이들의 parent를 저장시켜놓고 그것들만 특별하게 고려해서 union 하는 방법이 있다.

3. 이 문제 어려웠다. 나에게는 ...

 

 

 

5639_이진검색트리_골드4:

 

1. 전위 순회 결과를 그대로 arr에 저장. 이때 try, except를 써서 while문으로 돌림

2. 전위 순회는 루트 노드를 기준으로 왼쪽에 있는거 먼저 돌고 오른쪽으로 감 -> 더 큰것을 만나기전까지를 루트노드 왼쪽으로 쪼개고 쪼갬. 그리고 후위 순회! data를 dataL = [], dataR = [] 미리 만들어놓고 돌기

3. 굳이 node class 만들고 딕셔너리에 노드의 루트를 넣고 안해도 되는듯. 

 

 

 

10830_행렬제곱_골드4:

 

1. 행렬의 x제곱을 행렬의 x//2제곱 * 행렬의 x//2으로 나타낸다. 만약 x%2 == 1이면 x를 한번 더 곱해준다.

2. 행렬 곱셈 코드는 직접 만들어라...

 

 

 

11054_가장 긴 바이토닉 부분 수열_골드4:

 

1. 가장 긴 증가하는 수열의 dp랑 가장 긴 감소하는 수열의 dp 더해서 가장 큰 부분이 가장 긴 바이토닉 수열

2. 1에서 말하는 가장 긴 감소하는 수열은 뭔가 좀 이상하다. 원래 구하던 방식데로 가장 긴 감소하는 수열을 구하고 reverse() 하면 안된다. 차라리 오른쪽부터 시작하는 가장 긴 수열을 생각하고 reverse 하는게 좋겠다. 

 

 

 

12851_숨바꼭질2_골드5:

 

1. q에서 나온곳이 방문하지 않은곳일때만 넣지말고 새로 구한 거리가 이전에 구한 거리랑 똑같을때 까지 포함하기

 

 

 

1744_수묶기_골드4:

 

1. 2 이상일때, 1일때, 0이하일때 세개로 묶는다.

2. 1일때는 그냥 결과에 더해준다. 2이상일때는 두개씩 묶는다. 0이하일때도 두개씩 묶는다. 음수의 곱은 양수인것을 포함한다.

 

 

 

11401_이항계수3_골드1:

 

1. dp 범위에 제한이 있으므로 dp로 풀지 못하고, 팩토리얼로 풀어야한다.

2. 팩토리얼로 풀면 아마 시간복잡도가 터질것이므로 모듈러 연산의 성질과, 페르마 소정리를 활용해야한다. 이 문제에서는 거듭제곱을 분할로 풀어가는것만 얻어가면 될 것 같다.

 

 

 

16987_계란으로 계란치기_골드5:

 

1. 백트래킹 문제이다. for문을 돌면서 재귀를 하는게 들어갔다 나왔다 하는거랑 같다. 

2. data 자료구조에서 빼고 재귀하고, 재귀하고 나올때는 더했다 하면서 백트래킹

 

 

 

1941_소문난칠공주_골드3:

 

1. bfs + dfs(백트래킹) 문제

2. dfs는 25개중 7개 선택하는 경우의 수를 찾는 문제고, bfs는 찾는 그 경우가 연결되어 있는지 확인하는 용도.

3. dfs에서 s는 좌표를 저장해서 bfs로 연결되었는지 확인하고, n은 그 좌표의 data 값을 저장해서 조건을 만족하는지 확인한다.

4. bfs에서 좌표값을 복사해서 만들어서 하나씩 확인하면서 넘겨온 s값의 상하좌우에 l이 존재하면 remove. 만약 remove 전부 되고 전부 삭제되었으면 return True

5. bfs와 dfs를 전부 연결해서 쓰는 신박한 문제. 재미있었음. 또한 bfs를 저렇게 사용하는게 신기함. dfs에서도 그래프를 두개 만들어서 저렇게 각각 저장하는게 신기함.