프로그래머스 - 표 편집 - 2021 카카오 인턴 - swift
https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 문제해설은 이미 카카오테크에 나와있다. 본글은 연결리스트로 푸는 방법과, 세그먼트트리 + 이분탐색 으로 푸는 방법을 작성할것이다. 굉장히 좋은 문제라고 생각한다. 당시 시험볼때 효율성을 맞추지못한 문제였다. 다시 풀어보니, 연결리스트를 이용하니 쉽게 풀리는 문제였다. 우선 문제의 조건에도 핵심이있다. 마지막에 "..
2021. 7. 12.
백준 15732 - 도토리 숨기기 - swift
https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 조금 고민이 필요한 문제였다. 하나씩 규칙들을 탐색하면서 각 상자에 카운팅해도되겠지만, 1개씩 찾다보면 도토리가 총 10억개이므로 시간초과다. 좀 더 효율적으로 찾는 방법이 필요하다. 고민을해보니, 100~150개에서, 10간격이라면, 총 6개 도토리를 넣을수있다. 110~150, 15간격이라면 총 3개 도토리를..
2021. 6. 26.
백준 2287 - 모노디지털 표현 - swift
https://www.acmicpc.net/problem/2287 2287번: 모노디지털 표현 몇 개의 숫자 K(K는 1, 2, …, 9중 하나)와 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)만을 사용하여 어떤 자연수 X를 수식으로 표현한 것을 X의 K-표현이라 부른다. 수식에는 괄호가 포함될 수 있으며, 나 www.acmicpc.net 조합과 dp를 이용한다. 사칙연산으로 경우의수를 고려하다보면 골치아파진다. 물론 사칙연산으로 경우의수를 고려하긴해야하는데, 이는 4가지경우의수로만 한정짓고, K가 몇개사용됐는지를 중점으로 경우의수로 고민하면 풀린다. K는 최대 8개까지사용할수있다고했다. 또한 문제에서 K가 연속으로 붙어있는경우도 존재한다. 그러므로, K가 1개, 2개, 3개...8개 사용했을때 모든경우의수를..
2021. 6. 24.
백준 1351 - 무한수열 - swift
https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 선뜻보면 감이안온다. 심지어 N이 1조이다. 1부터 증가시켜서 찾을수도없다. 이 수열은 분명 재사용되는 값이 존재할 것 같지만, N이 1조안에서 dp를 적용해도 효율적일까 싶다. 결론은 효율적인데, 그 이유는 P와 Q의 범위를 보고 알 수 있다. P,Q는 최소 2이상이다. 또한 수열특징이 P or Q로 나눈 값이다. 즉, 최소 P,Q가 2라고 가정했을때, 매번 2로 나누어진다는 점이고, 이는 log2 로 계산할수있다. 즉, log2 ( 1조 ) 는 약 39로, 39번의 횟수로 1조에서시작하여 0으로 도착하는걸 알 수 있다. 2로 했는데도 ..
2021. 6. 24.
