스위프트
-
[Programmers] 스티커 모으기(2)Algorithm/Programmers 2021. 10. 24. 14:45
출처: https://programmers.co.kr/learn/courses/30/lessons/12971 분류: dp 접근 배열의 길이도 100,000 으로 크고 이 스티커를 뗄지 안 뗄지, 앞에껄 땠는지 안 땠는지 등등의 경우를 고려해줘야 하니 DP로 문제로 접근을 했어요. 그냥 배열의 첫 번째를 기준으로 잡으면, 이 스티커를 땔 경우 DP vs 떼지 않을 경우 DP 두 번의 DP를 구해서 최대를 구하면 되는 문제였네요 처음에 저도 이렇게 접근은 했는데 첫 번째 인덱스부터 DP, 마지막 인덱스부터 거꾸로 DP 라는 엉뚱한 풀이로 해서.. 꽤나 삽질을 했습니다 😰 풀이 일단 각 케이스의 0, 1번 기저 사례를 구해주고 2번 인덱스부터 점화식으로 적용해주면 됩니다. (사실 n이 3일 때는 하나밖에 땔 ..
-
백준 12865 평범한 배낭Algorithm/BOJ 2021. 3. 30. 13:09
출처: www.acmicpc.net/problem/12865 분류: DP 접근방식 디피로 해결할 수 있는 문제였습니다. 디피는 상황에 따른 최대 값을 기록해놓고 더 최적인 경우를 비교하면서 업데이트 해나가는 메모제이션 방식입니다. 이 문제에서는 특정 무게에 최대 가치가 얼마인지 기록해놓으면 되겠네요. 테이블에는 현재까지 찾은 최적의 가치가 들어있다고 할 때, 현재 무게 4짜리의 물품으로 테이블의 무게 7 칸을 채우려고 한다면 최적은 테이블의 무게 3짜리 칸 가치 + 현재 물품의 가치 (무게 4) vs 테이블의 무게 7짜리 칸의 가치 로 생각해볼 수 있습니다. 이런식으로 물품들을 입력받을 때마다 테이블을 업데이트 해나가면됩니다. 물품마다 현재 무게부터 테이블의 끝까지를 업데이트를 해나가야 하는데 테이블을 ..
-
백준 5639 이진 검색 트리Algorithm/BOJ 2021. 3. 26. 14:19
출처: www.acmicpc.net/problem/5639 분류: 트리 접근방식 pre-order 결과가 들어오면 이 트리의 post-order 검색의 결과를 출력하는 문제였습니다. pre-order의 결과를 놓고 보면 첫 번째가 root, root+1 부터 처음으로 root보다 큰 값이 나오는 위치까지가 Left 그 다음이 Right 트리가 됩니다. 우리가 원하는 결과인 post-order는 왼쪽부터 탐색하기 때문에 루트를 타겟으로 이분탐색으로 UpperBounds를 찾아서 왼쪽 -> 오른쪽 -> 루트 를 반복적으로 돌려주면 원하는 결과를 얻을 수 있습니다. 처음엔 입력 받을 때마다 루트부터 위치를 찾아 트리를 만들어 나가는 방식으로 접근했었는데 이렇게 하니까 시간초과가 났습니다. c++로는 이런 식으..
-
백준 1068 트리Algorithm/BOJ 2021. 3. 25. 16:49
출처: www.acmicpc.net/problem/1068 분류: 트리 접근방식 전형적인 트리 문제였습니다. 주어진 대로 부모자식을 쭉 연결한 다음 dfs나 bfs 방식으로 탐색하다가 삭제해야 할 노드를 만나면 건너뛰는 방식으로 하면 해당 요구조건에 맞게 빠르게 해결할 수도 있으나 (많은 분들이 그렇게 푸신 것 같습니다.) 저는 실제 트리에 가깝게 해결해보고 싶어서 실제로 해당 노드와 그 자식 노드들을 제거해주는 방식으로 해결해봤습니다. 처음에는 Node, Tree 클래스를 각각 만들어서 처리해서 풀었다가 별도의 Tree 클래스 없이 루트노드만 가지고 해결하도록 개선해봤는데요, n만큼 임시 배열에 노드를 만들어두고 -1을 만나면 treeNode의 변수로 저장해두고 연결과 제거를 모두 끝내고 나면 임시 배..
-
백준 15649 N과 M(1)Algorithm/BOJ 2021. 1. 28. 11:29
출처: https://www.acmicpc.net/problem/15649 분류: 백트래킹 접근방식 1~N까지의 수 중에서 중복없이 해당 길이의 모든 경우의 수를 다 찾는 문제였습니다. 가능한 모든 경우의 수를 다 고려하는 백트래킹으로 해결했습니다. 처음엔 원하는 길이만큼 만들어 나가는 dfs를 1~N을 시작점으로 해서 여러 번 돌리는 방식으로 풀었는데요 백트래킹을 공부하고 정통적인 방법으로 다시 풀어봤습니다. 해결방법 1 ~ N을 시작으로 해서 주어진 길이만큼의 배열을 만들어나가는 dfs 방식입니다. protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } exten..
-
백준 2252 줄 세우기Algorithm/BOJ 2021. 1. 27. 22:16
출처: https://www.acmicpc.net/problem/2252 분류: 위상정렬 접근방식 위상정렬로 해결할 수 있는 문제였습니다 :) 특정 순서를 지켜야 하고 방향성 있는 그래프 일 때는 위상정렬!! 을 다시 한번 기억해야겠습니다. 해결방법 큐를 구현하긴 귀찮고 removeFirst도 사용하기 싫어서 큐 인덱스를 가리키는 변수를 하나 만들어서 FIFO를 구현해봤습니다 :) protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()!..