매일 매일 성장하는 섭섭군

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

Type Conversion 과 Type Casting Type Conversion, Casting 모두 우리말로 하면 형변환이다 하지만 Swift 에서는 두개의 개념이 완전히 다르다. 결론부터 말하자면 Type Conversion은 메모리에 저장된 값은 완전히 다른 값으로 바꿔서 새로운 값을 생성한다. Type Casting은 메모리에 저장된 값을 그대로 두고 compiler가 다른 형식으로 처리하도록 지시한다. Type Conversion 문법 : Type(value) Ex) Int(2.0)Type Conversion 할 형태 안에 값을 넣어준다. 성공한다면 변환된 값을 반환 할 것이고 실패할 경우 error 또는 nil 값이 반환된다. 에러가 되는 경우 : 값을 저장할 경우가 충분하지 않다면 Err..

www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 요약 진실을 알고있는 사람과 연관된 파티에서는 거짓말을 하지 못한다. 즉 진실을 알고 있는 사람과 연관되어 있지 않은 그룹이 몇 개 있는지 파악해야 하는 문제이다. 문제의 예제 입력으로는 문제 파악이 힘들 수 있기 때문에 아래 예시를 함께 봐보자! 입력 4 3 1 4 2 1 2 1 3 2 4 3 4명의 사람과 3개의 파티가 존재한다. 진실을 알고 있는 사람은 1명이며 4번이 진실을 알고 있다. 위의 예시에서 4번 사..

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/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제요약 2차원 배열에서 최단거리를 구하는 문제에서 방향을 바꾸었을때 추가적인 비용이 발생하는 문제이..

programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 문제요약 문제를 읽어보면 쉽게 이해할 수준의 문제이다. 시간복잡도를 고려하지만 않는다면 방이 차있을 경우 1씩 더해가면서 확인하는 작업을 하면 정확성 테스트는 통과 할 수 있다. 하지만 1씩 더하는 방법을 사용할 경우 효율성 테스트에서 시간초과가 발생한다. 즉 방이 차있을경우 일일이 확인하지 않고 빠르게 배정된 방번호보다 크면서 비어있는 방을 찾는것이 관건이다. 문제풀이 IDEA 이번 문제의 주요 IDEA는 방이 비어 있는 방을 가리키는 것이다. 주요 알고리즘은 다음과 같다. 방 딕셔너리를 생성하고 다음과 같은 Key, Value 값을 가지도록 한다. ..

www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개�� www.acmicpc.net 문제 요약 이번 문제는 문제를 파악하는데에도 시간이 다소 걸렸다. 필자처럼 문제를 파악하기 힘드신 분들을 위해 사진으로 표현하면 다음과 같다. 단어목록과 보드가 주어지면 이 안에서 단어목록에 있는 단어들을 찾으면 되는 것이다. 주어진 보드에서 단어목록에 있는 단어를 모두 찾았다면 그 이후의 정답을 내는 작업은 매우 간단하다. 문제에서 하라는대로 하면 된다. 문제풀이 IDEA 문제를 해결하기..

Trie(트라이) Trie의 개요 Trie 는 트리 자료구조 중 하나이다. 특히 여러개의 문자열을 저장하는 자료구조인데 특정 문자열을 검색할 때 효율적이다. 가령 최대 길이가 m인 문자열 n개가 있는 집합에서 길이가 m인 임의의 문자열이 있는지 확인하려면 어떻게 해야할까? 단순히 직관적인 방법으로 하나씩 꺼내서 비교하면 된다. 하지만 최악의 경우 O(nm)의 시간복잡도가 소요된다. 그렇다면 Trie는 어떻게 문자열을 저장하길레 문자열을 검색할때 효율적일까? 바로 우리가 사전에서 단어를 찾듯이 문자열을 저장한다. 우리는 사전에서 "Apple"이란 단어를 찾을 때 다음과 같이 찾을것이다. 1. A가 있는 곳을 찾는다. 2. 두번째 글자가 p인 곳을 찾고 세번째가 p인 곳을 찾는다. 3. 마지막 글자까리 위와..