링크 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..
문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다. 오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다. BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오. 접근 1. 최소 몇 단계 만에 이어질 수 있는..
문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 접근 대각선상에 집이 있는 경우는 연결된 것이 아니므로, 상하좌우로 탐색하는 dfs다. 코드 n = int(input()) grid = [list(map(int, list(input()))) for _ in range(n)] ..
문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 접근 그림을 보면 위와 같은 규칙을 찾을 수 있다. 피보나치 수를 구해주면 된다. 예전에 피보나치 수를 구하는 문제에서 정직하게 재귀를 사용했다가 시간초과가 나오고, 배열에 저장해도 시간초과가 나왔던 기억이 있다. 그래서 변수만 사용해서 답을 구했다. 코드 n = int(input()) if n < 3: print(n%10007) else: a, b = 1, 2 for _ in range(n-2): a, b = b, a+b print(b%10007)
