Problem Solving
1.[프로그래머스] 입국심사
입국심사 설명 코드
2.[백준] 숫자 카드 2
파이썬 함수 bisect_right, bisect_left를 사용하면 쉽게 풀린다.
3.[백준] 가장 긴 증가하는 부분 수열 2
LIS(Longest increasing Subsequence; 최장 증가 수열) 알고리즘을 활용해야 한다. (참고)arr = \[1, 2, 1, 4, 2, 6, 3, 4, 5]lis 배열은 \[1, 2, 3, 4, 5] 가 된다.
4.[백준] 외판원 순회
dfs -> 전체 경로 탐색dp -> 메모이제이션 (이유 : 시간복잡도)bitmasking -> dp와 함께 사용 (이유 : 공간복잡도)
5.[백준] 사다리 조작
참고 : https://baby-ohgu.tistory.com/3
6.[프로그래머스] 징검다리 건너기
참고이분탐색을 통해 답을 구한다.단, 미리 답이 정해져있다고 간주하여 풀어야한다.\-> 즉, mid값이 답이라고 정해둔 뒤, 이후에 답(mid) 검증하는 순서
7.[LeetCode] 5. Longest Palindromic Substring
짝수문자, 홀수문자를 나눠서 고려한다 투포인터를 활용한다.palindrome 문자는 짝수/홀수길이를 가질 수 있기 때문에 고려해야할 경우는 짝수와 홀수 문자이다.여기서 포인트는 짝수문자와 홀수문자를 동시에 고려해야한다.투포인터를 통해 확인할 문자의 범위를 넓혀간다
8.[백준] LCS
참고 : https://www.youtube.com/watch?v=EAXDUxVYquY하나씩 규칙성을 찾아 점화식을 구하는 것 보다대략적인 점화식을 만들고 다듬어가는게 더 수월할 듯?
9.[프로그래머스] 경주로 건설
BFS -> 최소 비용을 구하기 위해 BFS로 접근해야한다.dp ->
10.중위 → 후위 표기법
피연산자이면 그대로 출력( 라면 스택에 push) 라면 (가 나올 때까지 스택 pop연산자이면 스택에서 현재 연산자의 우선순위보다 크거나 같은 것들을 모두 pop그리고 현재 연산자를 스택에 push
11.[백준] 21317 징검다리 건너기
징검다리 건너기 코드 틀린 코드 틀린 이유
12.[백준] 무기 공학
백트래킹은 global 로 최소나 최대값 갱신시켜주자.dfs(x, y + 1, score) 다음은 dfs(x, y + 1, score) \`\`\`3 332 83 7524 96 5671 88 120 0 visitedx=00, 0, 00, 0, 000 1 visitedx
13.[BOJ] 열쇠
입력출력참고새로운 key를 얻었을 때 비트 마스킹으로 상황을 구분할 수 있지만, 큐와 visited 배열을 초기화하여 구분할 수 도 있다.조건이 까다롭다면 생각의 전환이 필요하다