Embedded Files
<Baekjoon Basic Algorithms 2/2 50X, Brute Force 후기 및 일정>
기초 알고리즘 2/2 50X 문제를 관통하는 Brute-Force 탐색을 위해서
DFS, Back-tracking, Recursive, Permutation, Bistmask 에 대해서 이해할 수 있었다.
2023.12.22 - Basic 2/2 500 Start.
2023.12.23 - DFS 공부 with 510: N과 M (x)
2023.12.27 - DFS 공부, 510: N과 M(x) DONE.
2023.12.28 - Brute-Force, Edge Cases, 500 DONE.
2023.12.31 - Brute-Force, 순열 (Permutation), 520 DONE.
2024.01.04 - Brute-Force, Bitmask, 540 DONE
2024.01.06 - Brute-Force. Recursive, 530 DONE
2023.12.27 - Baisc 2/2, Brute-force 510 N과M(x), DONE.
2023.12.28 - Basic 2/2, Brute-force 500, DONE.
2023.12.31 - Basic 2/2, Brute-force 순열 Permutation 520, DONE
2024.01.04 - Brute-Force, Bitmask, 540 DONE
2024.01.06 - Brute-Force. Recursive, 530 DONE
2024.01.06 - Baekjoon 1248 맞춰봐 (Guess), Python3, 61% 에서 시간초과
PyPy3, 메모리 124412KB, 시간 4060ms로 통과
2024.01.06 - Baekjoon 1248 맞춰봐 (Guess), Python3, 61% 에서 시간초과 >
a 의 탐색 범위를 첫 부호 좌표 (1,1) , (2,2), (3,3) 에 해당하는 '+','0','-' 에 따라 양수, 0, 음수로 제한해주고 탐색.
답이 찾아졌다면, 다른 답은 더 찾지 않음.
list(deq)[:idx] 대신 rowsum += deq[idx-1] 을 활용하여서 연산 최소화.
> Python3 에서 34096KB, 6564ms 로 통과! 😁
2024.01.05 - Baekjoon 9663 N-Queen, 백트래킹 문제. 2차원 배열은 메모리와 시간초과. look-up table을 잘 구성하여, 해당 열 상하, 좌하향 대각선, 우 하향 대각선을 판단하여 구성. python3로 통과하기 힘들어 PyPy3로 통과.
문어박사 IT편의점 참고, https://www.youtube.com/watch?app=desktop&v=1Bh6DBcKgOc
2024.01.05 - Baekjoon 문제풀이, 문어박사 IT편의점 유튜부 채널 감사인사.
2024.01.04 - Baekjoon 14391 종이조각 - 비트마스크 공부, https://thought-process-ing.tistory.com/108.
단순히 1과 0으로 구성된 list [0,1,0,1] 을 만드는 것 보다 (N과 M에서 visited list처럼), 전체 경우의 수를 대표하는 binary string으로 접근하는 것이 메모리측면에서 효율적이란는 것을 배움. bit shift 연산 (1<<shift) 사용법에 대해서도 간단하게 짚고 넘어가볼만한 했던 예시.
2024.01.02 - Baekjoon 15661 링크와 스타트 - 시간초과.
2024.01.02 - Baekjoon 15661 링크와 스타트 - 조합의 절반만 해결하는 것으로 시간초과 해결, 조합을 생성할 때 절반만 확인하는 것으로 시간복잡도를 더 낮출수도 있겠음.
2023.12.31 - Baekjoon 10974 모든 순열, permutation, 쉬운 dfs 문제.
2023.12.31 - Baekjoon 10973 이전 순열, Baekjoon 10972 다음 순열과 동일한 아이디어로 접근.
보다 작은 수열을 만들 수 있는 위치를 수열 끝에서부터 오름차순이 깨지는 위치로 찾고, 작은 수열임에도 가장 큰 수열, 즉 바로 이전 수열을 찾은 위치 다음부터 존재하는 부분수열을 오름차순 정렬하는 것으로 확인.
시간초과 해결을 위해서 list.sort() 사용.
2023.12.31 - Baekjoon 11723 집합 - 1<=x<=20에 의한 집합이므로 set에 포함 유무를 0,1로 표시하는 쉬운 비트마스크 문제. python set([])을 사용하지않고, 비트마스크 기법으로 풀이.
2023.12.30 - baekjoon 10971 외판원 순회 2, 모든 도시를 방문하고, 마지막에 돌아오는 것 까지 종료조건으로 처리. 쉬운 DFS 문제.
2023.12.31 - Baekjoon 10870 피보나치 수 5, 쉬운 재귀
2023.12.29 - Baekjoon 6603 로또 : 쉬운 dfs
2023.12.30 - Baekjoon 27433 팩토리얼 2, 쉬운 재귀
2023.12.28 - Baekjoon 14550 테트로미노,
ㅗ,ㅜ,ㅓ,ㅏ 모양을 제외한 모양은, 좌표가 연속되어 DFS로 확인.
ㅗ,ㅜ,ㅓ,ㅏ 모양은 좌표 +,- 1 을 적절하게 4가지 경우 모두 테스트.
모든 좌표 [i][j] 를 중심으로 두개의 테스트 각각 확인.
2023.12.29 - Baekjoon 10972 다음 순열: 처음에 35%에서 멈추어서 틀린 이유를 찾지못했음. 문제 조건을 잘못이해했었음.
처음에는 input이 1~N까지의 수가 모두 한번씩 사용된 순열만 가능한줄 알았음. 마지막 순열의 조건을 list(range(N,0,-1)) 으로만 비교했었음.
알고보니, input이 1~N 중의 수로 이루어진 N개의 숫자 순열으로 중복을 허용함. 마지막 순열이 항상 list(range(N,0,-1))인 경우가 아니므로, y_max = -1로 swap 할 수 없는 경우에 -1을 출력하도록 함.
2023.12.28 - Baekjoon 2529 부등호: 숫자가 적어서 생각없이 for문으로 구성했는데 2984ms로 통과, dfs로 유효한 수열만 모두 찾으면 132 ms 으로 약 1/22 배 빨리 통과!
2023.12.28 - Baekjoon 1182 부분수열의 합: 쉬운 백트래킹 문제
2023.12.28 - Baekjoon 14550 테트로미노, colab에서는 잘동작하는데, baekjoon 에서는 런타임 에러 > 변수 sum 을 sum_val 로 교체하고, list 자료형을 너무 많이 쓰는 것을 줄임.
2023.12.28 - Baekjoon 10819: 차이를 최대로, 쉬운 list permutations 확인
2023.12.28 - Baekjoon 14501 퇴사, 재귀함수를 통해서 모든 경우를 탐색하고, 최댓값을 출력. 이전 날짜의 최대로 만드는 것이 다음 날도 최대로 만든다는 아이디어로, 점화식을 세워서 DP로 복잡도를 낮추어 풀수 있음.
2023.12.28 - Baekjoon 14889 스타트와 링크, 모든 팀의 조합을 고려
2023.12.27 - Baekjoon 15665 N과M(11), N과M(8) 에 visited list를 없앤 버전. prev는 기억하여 중복한 결과 수열은 제외함.
2023.12.27 - Baekjoon 15666 N과M(12), N과M(11) 에 visited list를 없앤 버전. prev는 기억하여 중복한 결과 수열은 제외함.
2023.12.28 - Baekjoon 1759 암호만들기 - 쉬운 dfs, N과 M (6) 오름차순 문제와 유사
2023.12.27 - Baekjoon 15663 N과 M(9), list를 set으로 바꾸었으나, "틀렸습니다"라고 출력
8 8
1 2 3 4 5 6 7 8 의 경우 런타임 에러임에도, 틀렸습니다, 라고 출력되는 경우가 있다고함. 반례를 찾으려 했으나, 해당 런타임 에러 문제로 생각됨.
2023.12.27 - Baekjoon 15663 N과M(9), 각 노드마다, prev를 기억함으로써 중복을 제거
2023.12.27 - Baekjoon 15664 N과M(10) 각 노드마다, prev를 기억함으로써 중복을 제거, N과M(9) 에 strat index만 추가한 버전.
2023.12.27- Baekjoon 1107: 리모컨, 내 총시도 = 18회
2023.12.27- Baekjoon 1107: 리모컨, 고장나지 않은 키에서 번호를 조합하는 것이 아니라, 항상 Channel 0 ~ 999999(6자리) 까지 탐색하면서 해당 Channel이 가능한지 str(num) 을 통해서 판단.
말그래도 Channel 숫자 기준으로 Brute-Force를 접근하여 시간은 좀 더 오래걸리지만 메모리 초과 해결. 시간제한 2초라서 넉넉하여 Bruteforce로 시도가 가능했음에 유의.
2023.12.27 - Baekjoon 1107: 리모컨. 꽤 귀찮게 어려운 문제, 현재 84%에서 메모리초과. itertools 의 product 함수를 사용하면서 생기는 문제로 판단.
2023.12.26 - Achieve Purdue Top 9, Over 200 Puzzles
2023.12.26 - Baekjoon 6064: 카잉달력 - 시간초과
2023.12.26 - Baekjoon 6064: 카잉달력 - 시간초과 lcm 으로 해결
2023.12.26 - Baekjoon 3085: 사탕게임, 딱히 요령없이 Brute Force. swap에 관한 문제이므로 현재 위치의 오른쪽과 아래쪽만 swap하는 것은 아이디어.
2023.12.26 - Baekjoon 15655 N과 M (6), N개의 숫자가 수열 A로 주어짐. 알고리즘 자체는 중복을 허용하는 N과 M(3) 과 동일
2023.12.26 - Baekjoon 15655 N과 M (8), N개의 숫자가 수열 A로 주어짐. 알고리즘 자체는 중복을 허용하는 비내림차순 수열 N과 M(4) 과 동일
2023.12.26 - Baekjoon 15655 N과 M (9) - 시간초과, 제출 전에 어느정도 예상은 했음.
2023.12.25 - Baekjoon 15652 N과 M (4), 비내림차순에 관한 쉬운 DFS
2023.12.26 - Baekjoon 15654 N과 M (5), N개의 숫자가 수열 A로 주어짐. 알고리즘 자체는 N과 M(1) 과 동일. visited list 대신 not in lst 로 구현해봄.
2023.12.26 - Baekjoon 15655 N과 M (6), N개의 숫자가 수열 A로 주어짐. 알고리즘 자체는 N과 M(2) 과 동일
2023.12.24 - Baekjoon 15650 N과 M(2)_sol1, 중복을 허용하지 않는 경우, 1~N까지 선택한다/선택하지 않는다 이진 탐색으로 Brute Force 진행.
2023.12.24 - Baekjoon 15650 N과 M(2)_sol2, 중복을 허용하지 않는 경우. 예쁜 for 문을 구성하는 방식으로 접근.
1을 선택했다면 다음 선택은 2~N 까지
n을 선택햇다면 다음 선택은 n+1 ~ N 까지
2023.12.24 - Baekjoon 15651 N과 M(3), 중복을 허용하는 쉬운 DFS
2023.12.24 - Baekjoon 15649 N과 M(1), DFS 연습
2023.12.24 - Baekjoon 15649 N과 M(1), DFS 연습 및 코드 재귀구조 이해
2023.12.24 - DFS에 관한 좋은 설명: https://jie0025.tistory.com/455
2023.12.22 - Baekjoon 2309: 일곱 난쟁이, 쉬운 Brute Force.
2명을 빼주는 경우로 for 문 2번 작성하는 아이디어로 접근.
라이브러리를 활용하여,
import itertools,
for x in itertools.combinations(array, 7):
if sum(x) == 100: break
로도 주어진 array에서 7명을 뽑는 모든 조합을 확인 가능.
2023.12.23 - Baekjoon 1748: 수 이어쓰기 1, 간단한 Brute Force 문제.
2023.12.23 - Baekjoon 15649 N과 M(1), itertools 활용.
인터넷은 DFS 방식으로 접근, 공부가 필요.
[백트래킹, DFS, 문어박사 IT 편의점]
Page updated
Google Sites
Report abuse