2024.07.07 - Baekjoon 12026 BOJ거리

• 간단한 DP

• list 안의 tuple을 활용하여 B, O, J 를 각각 0, 1, 2 마킹하여 B-O-J 순서에 맞게 최소 에너지값을 업데이트하는 DP.

2024.07.06 - Baekjoon 1890 점프

• BFS로 풀었더니 메모리 초과 

• 위,아래 두가지 경우로 증가하므로 2^100라고 하면 메모리 초과로 문제되는 것 이해됨. 

2024.07.06 - Baekjoon 1890 점프

• Brute-force (BFS) 로 보이는 문제에서 규칙을 찾아서 Dynamic Programming으로 풀 수 있다는 것은 꽤 흥미로운 결론. 메모리/속도 차원에서 큰 성능향상.  

• DP로 풀었음. Python3 {34028KB, 60ms}

• 왼쪽, 오른쪽으로 이동하며 최소한칸 이상은 이동한다는 점프 특성 상, 

     아래로 내려가며 각 행을 탐색해도 안전하게 모든 경우를 탐색함.

     (BFS처럼)

•  현재위치의 가짓수만큼 더하는 다음위치에 더하는 dp 구조.

2024.07.06 - Baekjoon 2293 동전 1

• 간단한 DP 문제

• 중복을 제외하기 위해, 동전의 종류를 변화시키면서 DP 업데이트 하는 것이 포인트.

• sort()는 불필요한 과정.

2024.07.06 - Baekjoon 2293 동전 2

• 간단한 DP 문제. K값을 얻을 수 있는 최소 동전 갯수를 찾으므로, 

 DP를 float('inf')로 선언하고 min 값을 찾는 방식의 점화식. 

• dp[0]= 0가, dp[coin] = 1으로 현재 가지고 있는 동전 종류의 값은, 동전 한개로 나타낼 수 있음을 반영하기 위한 자연스러운 초기 조건.

• 중복을 제외하기 위해, 동전의 종류를 변화시키면서 DP 업데이트 하는 것이 포인트.

• sort()는 불필요한 과정.

2024.07.03 - Baekjoon 15989 1,2,3더하기_4

• 수의 순서만 다른 것은 같은 것으로 센다.

• dp[n][x] = 합이 n인데 x로 시작하는 가짓수, x in {1,2,3}

• 이중 배열을 활용한 DP로 합을 내림차순 정렬하게끔 하여 순서만 다른 것을 같은 것으로 세는 조합을 구현. 

• Python3 {32140 KB, 52 ms} 로 통과.

2024.07.01 - Baekjoon 17141 연구실 2 

• visited set()과 itertools combinations를 활용해서 풀었음. 

• Python3 시간초과, PyPy3 {209640 KB, 2248ms}

2024.07.01 - Baekjoon 17141 연구실 2 

• visited list()과 itertools combinations를 활용해서 풀었음. 

• Python3 {34132, 480ms}

• PyPy3 {115996 KB, 284ms} = visited set() 결과의 약 1/8 시간단축. 메모리도 1/2 적게사용. =)

• visited True/False list를 미리 선언해두는 편이 계속 set()의 크기를 변화시키면서 tuple을 저장하는 것 보다 메모리를 적게 사용하고, 접근속도도 빠르다는 결론

• visited 는 tuple set() 보다는 True/False list로 선언하자!

2024.06.30 - Baekjoon 2234 성곽

• 모든 방의 크기를 (size, room_index)로 1차 BFS로 구함.

•  2차 BFS로 room_index가 다른 방의 합을 구해서 활용.

2024.06.30 - Baekjoon 2234 성곽

• 1차 BFS로 모든 방의 크기를 (size, room_index)로 구하여 M*N 맵에 표시

•  2차 BFS로 M*N개의 각 방마다 상하좌우를 탐색하여 room_index가 다른 방의 최대합을 구하고 정렬하여전체 최댓값 출력.

• Python3 {34176 KB, 64ms} 로 통과.

2024.06.30 - Baekjoon 16932 모양 만들기

• 모든 0의 위치를 시작으로 BFS 시도했더니 시간초과

• 다른 방법?

2024.06.30 - Baekjoon 16932 모양 만들기

• 미리 모양 구조를 탐색하고,

• 모든 0의 위치를 시작으로 상하좌우 네방향을 탐색해서 모양들의 합을 더하는 방식으로 통과 

• Python3 {120960 KB, 4660 ms}

• PyPy3 {182040 KB, 680 ms}

2024.06.21 - Baekjoon 2606 바이러스

• 양방향 네트워크 저장

• BFS + set() 활용하여 {34028KB, 56ms} 로 해결

2024.06.24 - Baekjoon 9955 NxM 보드 완주하기

• BFS + visited set으로 접근하려했으나, Python3에서는 25%에서 시간초과, PyPy3에서는 25%에서 메모리초과

• 어떤 부분을 줄여야하는지 잘 모르겠음. =|

2024.06.19 - Baekjoon 1806 부분 합

• 양방향 포인터 while문 두개로 구현.

• 함수 호출 대신, while문에서 각각 index를 변화시키는 방식으로 구현하여 recursion error 재귀함수 호출 초과문제 해결.  

• 애벌레가 오른쪽으로 기어가는 형식

2024.06.20 - Baekjoon 16945

• 3x3 매직 스퀘어(마방진) 갯수는 총 8개.

• {31252KB, 44ms} 로 통과 

2024.06.19 - Baekjoon 1806 부분 합 (recursion error)

• 1,...N에서 모든 위치에서 각각 시작하는 제일 짧은 부분 합 수열을 탐색했더니 recursion error.

• 양방향 포인터로 풀어볼 계획 (start, end) ---> (start+1,end) & (start,end-1)

2024.06.19 - Baekjoon 1806 부분 합 (recursion error 2)

• 양방향 포인터로 구성해보았으나, 재귀횟수 초과.

2024.06.18 - Baekjoon 1644 소수의 연속합

• Python3 {77024KB, 6408ms}, PyPy3 {244904KB, 1756ms}로 통과

• 모든 소수의 최소 연속합이 N이상인 index 이후부터 dfs 탐색.

• N=1 이 주어졌을 때 해결하기 위해 N+2까지 primes를 탐색.

• 다른 답변들은 dfs가 아니라, 투 포인터로 탐색하여 시간을 더 단축. 

2024.06.18 - Baekjoon 1644 소수의 연속합 (-ver2. 메모리/시간 최적화)

• num_lst를 list로 저장하지 않고, 그냥 count +1 만 수행.

• Python3 {73972KB, 2388mms}, PyPy3 {161504KB, 380ms} 로 통과.

• 결과값을 저장하지 않음으로써 약 1/3 시간단축, 1/2 메모리 단축하여 통과.

2024.06.17 - Baekjoon 17089 세 친구

• 4000_C_3 ~= 100* 10^8 ~= 100초로 combination 접근법은 X

• 현재 그룹의 {친구 set}을 계속 생성하는 방식으로 dfs 접근

• Python3 {32396 KB, 3540ms}, PyPy3 {195380 KB, 1268ms} 로 통과.

2024.06.17 - Baekjoon 16937 두 스티커 

• 처음에 넓이순 내림차순 정렬하여 greedy로 풀었으나, 4x4에서 

(3,4), (2,4), (4,2), (1,1) 일 경우 

(3,4) + (1,1) = 13

(4,2) + (2,4) = 16

으로 차순위 sticker의 합이 더 클 수도 있어서 brute force가 알맞음.

• 회전에 따라서 총 4가지 검사.

2024.06.17 - Baekjoon 2210 숫자판 점프

• 5x5 크기의 숫자판으로 작아서, dfs brute force 사용.

• result = set() 사용

• {31632KB, 44ms}로 통과

2024.06.17 - Baekjoon 2422 아이스크림

• combination을 계산하면 10^8 보다 작아서 dfs combination 구현으로 해결

• 쉬운 dfs burte force

2024.06.16 - Baekjoon 16938 캠프 준비

• Brute Force 수를 세부니 2^15 ~= 30000 < 10^8 으로 1초안에 해결이 가능해서, dfs함수로 구성.

• 쉬운 dfs 탐색 문제. {35212KB, 88ms}로 통과

2024.06.17 - Baekjoon 16943 숫자 재배치

• 9! = 362880 < 10^8 = 1초

• visited = set()

• greedy 하게 숫자를 찾으면 (큰자리 수부터 채워넣기, A의 길이가 B보다 크다면 찾는 것이 불가능) Brute Force가 아닌 Greedy이므로 더 빨리 찾을 수 있을 것으로 기대되었음. 귀찮아서 dfs로 구현. 

2024.06.15 - Baekjoon 16922 로마 숫자 만들기

• 간단한 dfs로 해결.

• set() 활용.

2024.06.15 - Baekjoon 16936 나3곱2

• 간단한 dfs로 해결. 

2024.06.14 - Baekjoon 16968 차량 번호판 1

• 시작 문자를 공백 ' '으로 시작한 것이 코드 간결성(if문 추가 귀찮음) 의 아이디어

2024.06.14 - Baekjoon 16917 양념 반 후라이드 반

• 브루트 포스로 풀라고 되어있는데, 알고리즘 구분은 생각없이 풀려고 시도.

• greedy하게 if case 5개로 나누어서 바로 price 값이 출력되게 풀었음. 2초 제한 시간 문제를 40ms 로 풀었음.