링크: https://www.acmicpc.net/problem/1539문제주어진 순서대로 이진 검색 트리를 구축하였을 때, 모든 노드들의 높이 합을 출력하는 문제이다. 9 다음에 1이 주어지면, 위와 같은 그림일 것이다.다음으로 4가 들어오면 \(x\) 위치로 갈 텐데, 이전에 등장한 수 중에서, 자신보다 바로 작거나 바로 큰 수의 높이 중 더 큰쪽 + 1이 자신의 높이이다. 만약 \(y\) 자리에 무엇이 있다고 해도, \(x < 9 < y\) 임은 항상 보장되므로, 자신보다 바로 작거나 큰 수만 비교하면 된다.코드

링크: https://www.acmicpc.net/problem/18109 문제 한글 두벌식 자판으로 타이핑할 때, 다음 글자의 초성 자음이 이전 글자의 받침으로 미리 작성되는 경우를 구하는 문제이다.자세한 예시는 문제에 자세히 나와있으니 생략한다. 풀이처음에는 영문 모드로 작성한 아무 문자열이 입력으로 들어오는 줄 알았다.그래서 모든 케이스에 대해 고려하다보니, 오토마타를 그리게 되었는 데 아래와 같다. 나중에 다시 보니 항상 "완성형 한글"이 입력되는 꼴만 입력되더라... (모음 'ㅏ'키인 k 가 대문자 K로 적히는 경우도 없었다)여기서 합성모음은 반모음+반모음(ㅘ, ㅝ)와 둘레모음+반모음(ㅞ, ㅙ) 등을 간략히 표현한 것이다. (알맞은 표현을 알려주시면 감사합니다)화살표에서 겹받침은 ㄳ, ㄼ 등으로..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu예전 기억으로는, 삼성 SW 역량 테스트 준비용 샘플 문제가 하나밖에 없었는데 뭔가 많이 추가된 모양이다.이번 문제는 그 중 하나이다.삼성 SW 역량 테스트에는 이런 백트래킹류의 탐색 문제가 자주 나오는 것 같다.문제문제를 요약하자면, 세로 길이가 D이고 가로 길이가 W인 2차원 평면에서, 특정 조건에 맞추기 위해 어떤 행을 모두 A(0) 또는 B(1)로 바꾸는 횟수를 최소로 하고 싶다는 것이다.여기서 조건은, 모든 세로줄에서 같은 종류끼리 K개 이상 연속으로 붙어 있으면 되게 만드는 것이다. 어떤 행을 선택하는 조합이 여러개이므로 ..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWK3lS6aF-MDFAWJ문제별표(*) 또는 0~9 숫자가 3개 적힌 카드가 N개 있을 때, 숫자끼리 연결되게 이어 붙여서 그 때의 모든 숫자의 합이 가장 큰 것을 구하는 문제이다. 여기서 별표(*)는 숫자를 연결하지 못하도록 만드는 구분자라고 생각하면 된다. 단순해보이지만 케이스를 제대로 생각못해서 여러번 시도 끝에 맞췄다.풀이는 브루트 포스(Brute force)이다. 먼저 숫자 카드는 아래처럼 6가지의 케이스가 있을 것이다. 편의상 (a) + (b) = 12312* 와 같이 적겠다. 숫자로만 이루어진 (a)는 어디에든 붙을 수 있으니, 그냥 무조건 더해..

링크: https://www.acmicpc.net/problem/5052문제한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.풀이 1 (정렬)모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, \(O(nlogn + n|s_{max}|)\)코드 1 (정렬) 풀이 2 (트라이; Trie)분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.문자열을 하나씩 확인하며 트라이를 만들어간다.어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.다음에 트라이를 만드는..

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqPrpnKSCQDFAT_문제경로에서 등장하는 모든 숫자의 곱에서 맨 뒷자리에 연속으로 있는 0의 개수, 즉 trailing zero의 개수의 최소를 구하는 문제입니다.trailing zero가 나오기는 위해서는 10의 배수라는 의미이고, 소인수 중 2와 5의 개수 중 작은 쪽만 확인하면 됩니다.이 부분은 BOJ 1676 - 팩토리얼 0의 개수 문제에서 풀어보시면 됩니다.가장 왼쪽 위 (1, 1) 지점에서 시작해서 오른쪽 또는 아래쪽으로만 이동한다는 점은,다음 지점의 입장에서는 위쪽 또는 왼쪽의 영향만 받는다는 의미이기도 하지요.항상 위쪽 또는 왼쪽까지 도착..

문자열을 정수로?이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다. 영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 문자열을 정수형 변수 하나에 담는 것을 말합니다.왜?보통 해싱은 작은 크기로 우겨넣기 때문에 데이터 손실이 일어나는 형태가 많습니다. 그래서 그대로 저장하면 충돌 해결 이슈가 따라오죠. (resolving collisions in hash tables) 정수로 바꾸어서 다룬다면 문자열 비교를 길이만큼인 \(O(|s|)\) 가 아닌 정수 비교 시간인 \(O(1)\) 으로 줄일 수 있습니다. 조건만 가능하다면 데이터의 손실 없이 그대로 담을 수도 있죠.26진법소문자 26개 혹은 대문자 26개만 사용하..

링크: https://www.acmicpc.net/problem/5535문제각 날짜마다 입을 수 있는 옷들이 있고, 다음 날과 옷의 화려함의 차이가 최대한 크도록 옷을 고르는 문제이다.날짜마다 가능한 옷을 저장해둔다. 그 날에 한해서는 옷의 종류나 순서가 중요치않길래 화려함 정도를 넣어버렸다. 이제 각 날짜마다 옷을 하나씩 고른다면, 총 D일동안 N가지의 옷을 고르므로 경우의 수는 \(O(N^{D})\) 이다. 어떤 d번째 날에 A라는 옷을 골랐다고 치자. 그럼 d+1번째 날 이후로는 d번째 날에 A를 고른 영향이 계속 생긴다.즉, d번째 날에 a를 고른 이후로는 하나의 부분 문제로 볼 수 있다. 점화식을 dp[D][N] = D번째 날에 N번째 옷을 선택했을 때의 화려함의 최대값 으로 세우면 \(O(ND..