kth990303의 코딩 블로그

이번에도 UCPC 문제 포스팅이다. 트라이 구현코드를 바꾼 후, 처음으로 해결해본 응용 문제인데, 구현코드가 익숙하지 않아서였는지 꽤나 고생을 했던 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17365 17365번: 별다줄 먼 옛날에 문래빗어라는 언어가 있었다. 문래빗어에는 여러 개의 단어가 있었고, 사람들은 단어들을 나열해서 문장을 만들었다. 예를 들어 "ryan", "is", "lion" 세 단어로 "lion is ryan is lion"이라는 문 www.acmicpc.net 의식의 흐름 및 해설 예제입력1의 결과가 왜 109인지 직접 생각해보면 문제 이해에 도움이 된다. 해석하려는 단어가 aaaa 일 때, a는 예제입력1의 세 단어 모두 가능하므로 3*..

https://programmers.co.kr/learn/courses/30/lessons/84325 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 프로그래머스에서 진행되는 위클리 챌린지 문제를 풀어보았다. 문제 자체는 어렵지 않으나, 다른 사람의 코드를 보면서 배운 점이 있어서 포스팅해보려한다. 이번 문제는 문자열을 파싱하여 적절한 구현을 요구하는 문제였다. table이나 languages 벡터의 길이가 최대 10이므로 시간복잡도를 걱정할 필요가 전혀 없는 문제이나, 문자열파싱에 조금 애먹을 수 있는 문제..

5월에 카카오 월간 코드 챌린지를 치고 나서, 내 약점 중 하나인 스택을 보완해야겠다고 느끼고 풀어본 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 의식의 흐름 및 해설 우선 올바른 괄호쌍끼리만 제거할 수 있다는 점을 파악한다. 따라서 "문자열 폭발" 과 비슷한 원리를 이용할 수 있으며, 이 괄호쌍들을 넣을지 안넣을지 고려하는 알고리즘을 짜봐야 하는데, 괄호쌍은 적어도 1, 많아..

스코페에서 아호코라식 알고리즘이 출제가 돼서 언젠가 공부를 해야겠다 해야겠다 하고 미루다가 오늘에서야 공부하고 풀게 된 문제이다. www.acmicpc.net/problem/10256 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net 아호코라식 말고 간단한 풀이가 더 있는 듯 한데, 일단 난 9250번 문제(아호코라식의 정석 개념예제 문제)보다 어려운 듯 하여 P2에 투표하였다. (아호코라 식이 아니고 aho-corasick 이었어..? ㅋㅋㅋㅋ) 이 아호코라식이라는 거... 정말 엄청 어렵..