매일 매일 성장하는 섭섭군

www.acmicpc.net/problem/12018 12018번: Yonsei TOTO 연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배 www.acmicpc.net 문제요약 가장 많은 과목수를 골라야 한다. 즉 내가 가진 포인트를 최대한 활용해서 많은 강의를 듣는것이 목적인 문제이다. 문제풀이 IDEA - 각 과목별로 수강할 수 있는 가장 적은 마일리지를 알아낸다. 신청인원이 수강총 정원보다 작을 경우 수강 마일리지는 1 신청인원이 수가총 정원보다 클 경우 수강 마일리지는 다음과 같다. 수강신청 마일리지를 오름차순으로 정렬 -> [수강총 정원 -1]이 수강 마일리..

programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제요약 배열에 있는 문자열의 종류를 모두 포함하는 최소 구간을 찾으면 되는 문제입니다. 간단하게 모든 경우의 수를 생각하면서 문제를 풀게되면 시간초과가 나게됩니다. 문제풀이 IDEA 시간 초과 없이 문제를 해결하기 위해 다음과 같은 고민을 진행하였습니다. 배열에 있는 문자열을 한번만 순환하여 찾는 방법이 없을까? 특정 구간 안에 있는 문자열의 종류의 수를 한번에 찾을 수 없을까? 먼저 한번만 순환하여 찾는 방법으로 지렁이 ..

programmers.co.kr/learn/courses/30/lessons/60060# 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제 개요 이번에 풀어볼 문제는 2020 Kakao 블라인드 채용에 출제되었던 가사 검색이란 문제입니다. queries에 있는 '?'가 섞인 문자열이 있는데 각 해당하는 문자열이 words에 있는 것과 몇개나 매칭이 되는지 알아봐야 합니다. 단순하게 모든 문자열을 비교한다면 풀릴 것 같은 문제입니다. 하지만 그렇게 한다면 시간은 굉장히 오래걸리게 됩니다. 문제 풀이 IDEA 문자열들이 있는 집합에서 특정 문자열을 효율적으로 검색하기 위해서 Trie 라는 자료구조를 사용 할 것 입니다. Trie 에 대한 설명은 다음 링크에 있습니다. 설명보기 queries..

https://www.acmicpc.net/problem/1599 1599번: 민식어 첫째 줄에 민식어 단어의 개수 N이 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄부터 한 줄에 하나씩 단어가 입력으로 들어온다. 단어의 길이는 최대 50자이다. 민식어에 없는 알파벳� www.acmicpc.net 문제 요약 이번 문제는 '민식어' 라는 문제이다. 문제를 요약하자면 다음과 같을것 같다. 민식어의 알파벳 순서는 "a b k d e g h i l m n ng o p r s t u w y" 순이다. 입력으로 들어온 단어를 민식어 알파벳 사전순으로 정렬하여 순서대로 출력한다. 문제풀이 IDEA 민식어 단어를 영어로 변환한다. Dict 테이블에 Key : 민식어 , Value : 영어 로 저장한다..

leetcode.com/explore/challenge/card/august-leetcoding-challenge/550/week-2-august-8th-august-14th/3419/ Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. leetcode.com 문제요약 이번에 풀어볼 문제는Excel Sheet Column Number 라는 문제입니다. 문제를 해석해 보면 알파벳으..

이번에 풀어본 문제는 Power Of Four이란 문제입니다. 문제는 다음과 같습니다. leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3412/ Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 제목에서부터 어떤 문제인지 알것 같다. 입력으로 주어지는 숫자가 4의 제곱근인지 판단하면 되는 문제다. 간단한 수학만 ..

백준 5397 키로커 이번에 풀어볼 문제는 백준 5397번 키로커 라는 문제이다. 스택 알고리즘에 분류되어있고 solved.ac 랭크 실버3 정도의 문제이다. 문제는 다음과 같다.링크 내가 본 문제에서 중점적으로 본 것은 커서의 위치를 어떻게 컨트롤 하는지에 관련된 것이다. 커서의 위치를 기억하고 해당하는 위치에 비밀번호를 입력하고 삭제하게 된다면 굉장히 많은 시간을 낭비하게 될것이다. Python list에서 insert와 특정위치의 pop의 시간복잡도는 O(N)이다. 문제 해결 아이디어 하나가 아닌 두개의 스택을 사용한다.(stack1, stack2) 알파벳이 나왔을 경우 stack1에 쌓는다. "-"가 나올경우 stack1에서 pop을 진행한다. "" 가 나올경우 stack2에서 pop을 진행하고 ..

이번에 풀어볼 문제는 백준 2688번 문제인 '줄어들지 않아' 라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 문제 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다. 예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, www.acmicpc.net 줄어들지 않는 수를 각각 구하게 된다면 시간초과가 발생할 것입니다. 64자리까지 있으니까 말이죠 그렇다면 각 자릿수의 경우들간의 관계를 살펴보면 좀 더 쉽게 풀 수 있을 것 같습니다.(다이나믹 프로그래밍을 사용했습니다.) 먼저 자리수에 따른 경우의 수를 살펴보면 다음과 같습니다...