오늘의 문제 링크 오늘의 문제는 Job Scheduling 을 하면서, Maximum Profit 을 찾는 문제였다. 얼핏 봤을 때는 지난번에 풀었던 Interval Scheduling Algorithm 이 생각났다. Interval Scheduling Algorithm 은 일반적으로 각 간격과 관련된 이익을 고려하지 않고 겹치지 않는 간격(또는 작업)의 수를 최대화하는 것이었다. 하지만 이번 문제에서는 총 이익을 극대화해야 하므로 복잡도가 올라갔고, 다른 방법으로 접근해야 했다. 1. 종료 시간을 기준으로 정렬 Interval Scheduling Algorithm 이랑 비슷한 부분은 종료 시간을 기준으로 정렬하고 시작한다는 것 종료 시간을 기준으로 정렬하는 것은 현재 직업 이후에 선택할 수 있는 다음 ..
오늘 오랜만에 아메리카노를 마셨더니 잠이 안들어서 어쩔 수 없이 일어났다. 알고리즘을 풀면 졸려질까 싶은 생각에 리트 코드를 열었는데, 오히려 더 쌩쌩해졌다. 1. 문제 Given an integer x, return true if x is palindrome integer. An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not. 팰린드롬 수는 101, 121, 1221과 같이 뒤집어도 같은 수다. 처음에 문제를 보자마자 str로 변환하고, 뒤집은 값과 비교하면 되겠다고 생각했다. 그런데 문제의 예제를 끝까지 읽다보니 Follow up에 Follo..
이제까지는 글을 내가 공부한 걸 정리한다는 느낌으로 썼다. 하지만 면접을 보면서 다른 사람에게 설명하는 것에 미숙하다고 생각하게 됐고, 앞으로는 읽는 사람이 이해할 수 있게 글을 써야겠다고 생각했다. 1. 문제 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is wri..
링크 https://leetcode.com/problems/number-of-matching-subsequences/ Number of Matching Subsequences - 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 문제 Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s. A subsequence of a string..
링크: https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제: 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는..
링크: https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제: 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요. [규칙] 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 ..
링크> programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 문제> 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다. 네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한..
3달 전에 계속 시간 초과가 나와서 잠시(포기한건 아님) 해결을 뒤로 미뤄놨던 문제다. 지금 다시 보니 예쁘게 생기긴 했지만, 효율성은 0인 코드였다. 오늘 푼 코드도 딕셔너리를 사용하면 시간이 좀 더 단축될 거 같긴 하지만.. 일단은 통과했다! 링크> www.acmicpc.net/problem/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n= len(land)/2: print(army) else: print("SYJKGW") 그런데 조금 이상한게 과반수를 초과하는 경우에 그 군대가 땅을 지배하는 건데, 과반수여도 땅을 지배하게 해야 답이 나온다. 병사의 수를 세는데서 시간이 많이 걸리는데 Couter를 사용해서 간단하게 풀거나, 하나 하나 세줘도 된다. 다만, 셀 때는 list.c..
링크> programmers.co.kr/learn/courses/30/lessons/72412 지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 풀이> 문제 자체는 어렵지 않지만, 효율성에서 걸리기 쉬운 문제다. 하지만 의외로 해결책은 간단하다. for 반복문을 돌면서 일일이 n점 이상인 응시자를 찾지 말고, 일단 정렬을 한다음에 이진탐색을 하면 쉽게 통과된다. 응시자가 속할 수 있는 16개의 그룹을 어떻게 구할까 처음에는 많이 고민했는..
1️⃣ 링크 programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 2️⃣ 코드 from itertools import permutations import re # expression 이 '50*20+2'인 경우에 def solution(expression): # {*, +} operator = set(re.sub('\d','',expression)) # ['50', '*', '20', '+', '2'] expression = ..
sliding window 를 연습하기위해 leetcode 239번 문제를 풀고 있었다. 링크: leetcode.com/problems/sliding-window-maximum/ Sliding Window Maximum - 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 계속 시간 초과가 나와서 한번은 정답 코드 로직을 그대로 따라했는데도 시간 초과가 나왔다. 정답 코드와 내가 입력한 코드의 차이점은 변수 이름의 길이 밖에 없었고, 나는 '변수 이름의 길이가 프로..
문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 코드 import sys class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def preorder(node): if node is None: return print(node.val, end='') if node.left: preorder(tree[node.left]) if node.right: preorder(tree[node.right]) def i..
