Algorithm/Programmers
-
[Programmers] 스티커 모으기(2)Algorithm/Programmers 2021. 10. 24. 14:45
출처: https://programmers.co.kr/learn/courses/30/lessons/12971 분류: dp 접근 배열의 길이도 100,000 으로 크고 이 스티커를 뗄지 안 뗄지, 앞에껄 땠는지 안 땠는지 등등의 경우를 고려해줘야 하니 DP로 문제로 접근을 했어요. 그냥 배열의 첫 번째를 기준으로 잡으면, 이 스티커를 땔 경우 DP vs 떼지 않을 경우 DP 두 번의 DP를 구해서 최대를 구하면 되는 문제였네요 처음에 저도 이렇게 접근은 했는데 첫 번째 인덱스부터 DP, 마지막 인덱스부터 거꾸로 DP 라는 엉뚱한 풀이로 해서.. 꽤나 삽질을 했습니다 😰 풀이 일단 각 케이스의 0, 1번 기저 사례를 구해주고 2번 인덱스부터 점화식으로 적용해주면 됩니다. (사실 n이 3일 때는 하나밖에 땔 ..
-
Programmers Lv3) [2020 카카오 인턴십] 보석쇼핑Algorithm/Programmers 2021. 4. 21. 17:31
출처: programmers.co.kr/learn/courses/30/lessons/67258 분류: Lv3, 카카오 인턴십, 투 포인터 접근방식 투 포인터 방식으로 해결했습니다. 먼저 전체 보석 종류의 개수를 구해놓고 포인터를 움직이면서 모든 보석이 들어있는 경우를 체크해주는 방식입니다. 저는 처음에 조금 비효율적으로 접근했는데요, 보석의 개수를 체크해주면서 현재 시작 포인터의 보석이 여러 개라면 현재 보석을 더 들고 있을 필요가 없으니 포인터를 옮겨주는 방식을 사용했습니다. 전체 과정을 좀 더 설명드리면, 저는 시작 포인터가 끝에 도달할 때까지 반복문을 돌려주면서 먼저 보석이 모두 들어있는지 체크해서 최선이라면 결과를 바꿔주고 끝 포인터를 움직이면서 보석에 담아줍니다. 그리고 현재 시작 포인터의 보석..
-
Programmers Lv3) [2020 카카오 인턴십] 경주로 건설Algorithm/Programmers 2021. 4. 21. 17:16
출처: programmers.co.kr/learn/courses/30/lessons/67259 분류: Lv3, BFS 접근방식 BFS 방식으로 해결했습니다. 조금 확장된 개념이 들어가는데, 단순히 방문 체크에 더해서 비용과 방향까지 기록해주면서 탐색해나가면 됩니다. 방향까지 체크해주는 이유는 같은 가격이여도 어떤 방향에서 오는지에 따라 달라질 수 있기 때문입니다. 현제 체크되어 있는 방향의 비용보다 더 작다면 다시 방문해주는 방식이 되겠습니다. 저는 enum으로 방향을 정의해주고 (그냥 Int나 bool 변수 등으로 정의해도 상관없을 것 같습니다.) Point 를 하나 정의해서 가지고 있도록 해줬습니다. enum Direction: Int { case horizontal = 0, vertical } ty..
-
Programmers Lv3) [2019 카카오블라인드] 길 찾기 게임Algorithm/Programmers 2021. 4. 21. 16:50
출처: programmers.co.kr/learn/courses/30/lessons/42892 분류: Tree 접근방식 주어진 노드 정보를 가지고 이진트리를 구성한 후 전위순회, 후위순회 결과를 반환하면 되는 문제였습니다. 노드 정보는 [Int]로 x, y 값이 주어지는데, 같은 레벨의 노드는 모두 y값이 같고, y값이 클수록 상위 레벨의 노드입니다. 따라서 y값을 기준으로 sort해주고 차례대로 이진트리를 구성해주면 됩니다. 저는 순회할 때 인덱스를 반환해야 하므로, 노드에 index 값을 가지고 있도록 했습니다. x,y 정보도 그냥 배열 그대로 들고있도록 해줬어요. class Tree { var value: [Int] var index: Int var leftChild: Tree? var rightC..
-
Programmers Lv2) [2021 카카오블라인드] 메뉴 리뉴얼Algorithm/Programmers 2021. 2. 27. 14:04
출처: programmers.co.kr/learn/courses/30/lessons/72411 분류: 조합 접근방식 카카오 블라인드 2번 문제였습니다! 주어진 코스의 개수에 해당하는 조합을 모두 찾고 그 중에서 가장 많은 사람이 먹었던 메뉴들을 골라주면 됩니다. 여러 개라면 모두 넣어줍니다. 주어진 입력 범위가 그리 크지 않기 때문에 ( 20(orders) x 10(각 order의 최대 길이 ) x 10(course) x 10(각 course의 최대 길이) = 20000 정도?) 그냥 다 돌면서 조합을 찾아주고 필터해주면 됩니다. 조합을 찾는 방식은 어렵지않게 찾아볼 수 있습니다 :) 저는 각 코스 문자열의 인덱스를 돌면서 해당 인덱스를 추가해서 재귀, 추가하지 않고 재귀를 돌려서 만들었습니다. func..
-
Programmers Lv2) [2021 카카오블라인드] 신규 아이디 추천Algorithm/Programmers 2021. 2. 22. 13:38
출처: programmers.co.kr/learn/courses/30/lessons/72410 분류: 문자열 접근방식 친절하게 단계별로 요구사항을 제시해주고 있기 때문에 주어진 대로 열심히 구현하면 되는 문제였습니다! 문자열을 다루는 문제이니 만큼 굉장히 다양한 풀이들이 있더라구요. 문자열을 연습하기 아주 좋은 문제였던 것 같아요. 각 단계별로 가능한 다양한 풀이를 생각해보면서 정리해보고자 합니다. 우선 다른 분들의 풀이를 보면 그냥 solution 함수에 다 때려박아(?)서 구현하신 분도 있고 함수를 나누신 분도 계시고 extension 으로 처리해서 더 깔끔하게 푸신 분들도 계시던 것 같아요. 편한대로 풀면 되겠지만 실전이라면 여기서 너무 시간을 오래 끌지 않도록 익숙하고 빠르게 풀 수 있는 방법으로..
-
Programmers Lv4) [2020 카카오블라인드] 가사검색Algorithm/Programmers 2020. 8. 30. 11:57
출처: programmers.co.kr/learn/courses/30/lessons/60060 분류: Kakao Blind 2020, Lv4, Trie 접근방식 효율성 문제였습니다. 대부분 정확성까지는 어렵지 않게 푸셨을 것 같은데요, 효율성에서 상당히 애를 먹었습니다 ㅠㅠ 문자열을 얼마나 효율적으로 관리하고 탐색할 수 있을지가 키포인트였던 것 같습니다 :) 카카오 단골이죠 문자열 ... 😇 문제설명 가사검색은 주어진 words가 있을 때 query에 만족하는 단어가 몇 개인지 찾는 문제였습니다. 쿼리는 ?를 포함하고 있는데요, ?는 한 글자를 의미하며 어떤 글자가 와도 괜찮습니다. 예를 들어 다음과 같다면, words = ["frodo", "front", "frost", "frozen", "frame"..
-
Programmers Lv2) [3차] n진수 게임Algorithm/Programmers 2020. 8. 28. 17:34
출처: programmers.co.kr/learn/courses/30/lessons/17687 분류: 카카오 블라인드 2018 3차, Lv2 접근방식 주어진 진법의 수를 한 글자씩 끊어서 말하는 게임입니다. 모든 멤버 * turn 이 총 말해야 할 문자열의 길이가 됩니다. 0부터 시작해서 총 문자열의 길이가 멤버 * turn 가 될 때가지 문자열을 만들어 주고 여기서 튜브가 차례의 문자들 (p-1 + m * turn) 을 찾아주는 방식으로 해결했습니다. (p가 1부터 시작하기 때문에 -1을 해줬습니다.) 해결방법 func solution(_ n:Int, _ t:Int, _ m:Int, _ p:Int) -> String { let string = radixString(radix: n, turn: t, me..