For coding test

코딩 테스트를 위한 백준, 프로그래머스 문제 풀이

python - string strip(), rstrip(), lstrip() strip() : string의 앞, 뒤 공백을 제거 rstrip() : string의 오른쪽 공백을 제거 lstrip() : string의 왼쪽 공백을 제거 tree 구현은 dictionary를 이용 print 출력 시 줄바꿈 없애는 법 python에서는...

문제 자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 108 이하이다. 출력 입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다. 처음 작성한 코드_Timeover...

입력 데이터의 개수에 따른 복잡도의 증가 만약 그 복잡도가 지수꼴이라면 n값의 증가에 따른 증가폭이 급격히 증가한다. 따라서 코드를 짤 때 있어서 최대한 일차 or log함수를 그 복잡도로 갖는 코드를 작성하는 것이 좋다. 효율적인 알고리즘 알고리즘이 결과 도출까지 걸리는 시간이 짧을수록, 사용하는 메모리가 적을수록 효율적이라고 할 수 있다. 항상 코드...

2960.에라토스테네스의 체 문제 바로가기 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 ...

다음 소수 문제 바로가기 문제 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. 출력 각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를...

21919. 소수 최소 공배수 문제 바로가기 문제 입력 출력 문제 접근 주어진 수열에서 소수를 먼저 구분, 그 소수를 이용해서 lcm을 구한다. lcm()에 list를 대입할 순 없다. 따라서 list값을 lcm에 대입하는 함수를 따로 정

14916.거스름돈 문제 바로가기 문제 >춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 15원...

문제 설명정수 n이 매개변수로 주어질 때 n의 각 자리 숫자의 합을 return하도록 solution 함수를 완성해주세요입출력 예시아이디어int로 입력된 n의 자릿수를 표현할 수 있는 방법 > 10의 n제곱수를 이용해서 표현하자내 풀이추가 개념split('구분자', '

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.b

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니

문제 설명 바로가기 >짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할...

문제 설명 바로가기 >무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이

문제 설명 바로가기 >숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기...

문제 설명 문제 바로가기 >- 과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다. 한 상자에 사과를 m개씩 담아 포장합니다. 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사...

문제 설명 문제 바로가기 >- 햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채...

순열과 조합의 사용 >순열 : n개의 list에서 m개의 요소를 순서를 고려하여 뽑는 것 중복 순열 : n개의 list에서 m개의 요소를 순서를 고려하여 중복해서 뽑는 것 조합 : n개의 list에서 m개의 요소를 순서를 고려하지 않고 뽑는 것 중복 조합 : n개의 list에서 m개의 요소를 순서 고려 없이 중복해서 뽑는 것 library 사용하여 구현...

문제 설명 문제 바로가기 >- 숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요. 예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314...

문제 설명 문제 바로가기 >0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요. 제한 사항 >1 ≤ numbers의 길이 ≤ 9 0 ≤ numbers의 모든 원소 ≤ 9 numbers...

count()는 시간 복잡도가 O(n)이다. (n = len(str)) >for문 내에서 count()를 사용하면 그 복잡도가 급격히 증가하므로 Collections Counter를 사용하면 이점이 있다. from collections import Counter >- Counter 생성자는 여러 형태의 데이터를 인자로 받는데, 중복된 데이터가 저장된 배열...

문제 설명 문제 바로가기 >머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 ...

문제 설명 문제 바로가기 >한 개 이상의 항의 합으로 이루어진 식을 다항식이라고 합니다. 다항식을 계산할 때는 동류항끼리 계산해 정리합니다. 덧셈으로 이루어진 다항식 polynomial이 매개변수로 주어질 때, 동류항끼리 더한 결괏값을 문자열로 return 하도록 solution 함수를 완성해보세요. 같은 식이라면 가장 짧은 수식을 return 합니다. ...

문제 설명 문제 바로가기 >영어 점수와 수학 점수의 평균 점수를 기준으로 학생들의 등수를 매기려고 합니다. 영어 점수와 수학 점수를 담은 2차원 정수 배열 score가 주어질 때, 영어 점수와 수학 점수의 평균을 기준으로 매긴 등수를 담은 배열을 return하도록 solution 함수를 완성해주세요. 제한 사항 >0 ≤ score[0], score[1] ...

문제 설명 문제 바로가기 >스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. > 제한 사항 >numbers 배열의 크기는 1 이상 1,000 이하입니다. numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다. hand는 "left" 또는 "right" 입니다. "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다. ...

문제 설명 문제 바로가기 제한 사항 입출력 예 풀이 접근 >- 처음에는 participant list에서 각 원소를 받아 해당 원소가 completion에 존재 하지 않는다면 해당 i를 return, i를 포

python 에러 타입 > 1. 구문에러(SyntaxError) : 문법 오류, 오타에 의한 에러 런타임 에러(RuntimeError) : >>1. zerodivisionerror : 0으로 나누었을 때 발생하는 error IndexError : indexing을 할 때 길이 이상으로 선언 했을 때 NameError : 선언하지 않은 변수를 사용하...

문제 설명 제한 조건 입출력 예 문제 접근 > - 공백 기준으로 split() 후에 capitalize를 써서 해당 list를 update시킨 후 join()하면 되겠다. 근데 8번 문제가 에러가 자꾸 난다. 질문을 살펴보니 공백문자가 연속해서 나올 수 있고, 이는 문자열을 이룰 수 있다고 문제에 나옴.![](https:

문제 설명 문제 바로가기 제한 조건 >n은 10,000 이하의 자연수 입니다. 입출력 예 > 문제 접근 >- 접근을 어떻게 할지 전혀 몰랐다. 이럴 땐 그냥 완전 탐색.. 1부터 하나씩 증가하면서 더하고, 이 값이 n보다 커지면 다음 case로 넘어간다 for문 속의 for문을 이용해도 되지만, while을 이용해서 풀이 추가) n//2+1부턴 무조건...

문제 설명 문제 바로가기 제한 조건 >N : 2^1 이상 2^20 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.) A, B : N 이하인 자연수 (단, A ≠ B 입니다.) 입출력 예 > 문제 접근 > - while문을 이용해서 a, b의 값을 계속 update 그 차이가 1이고 b가 짝수일 때의 cnt값을 return하도록...

문제 설명 문제 바로가기 제한 조건 >제한 사항 숫자 N: 1 이상 10억 이하의 자연수 숫자 K: 1 이상의 자연수 입출력 예 > 문제 접근 >- 2로 나누었을 때 나머지를 모두 더하면 1씩 이동한 횟수의 합이 된다. 주어진 수에서 0으로 간다고 생각하면 이해가 편함 내 풀이 > 다른 사람 풀이 > ? 10진수를 2진수로 바

문제 바로가기 문제 접근 >- 가입자 수가 큰 것을 우선으로 그 다음에 판매익을 비교한다 >> 가입자 수가 같을 경우만 판매수익을 비교해서 업데이트 시킨다 >- user의 제한이 100명, emoticon의 수가 7개로 한정되어있다 >> 할인율은 10,20,30,40으로 정해져 있으므로 emoticon을 할인하는 경우의 수는 최대 4^7으로 모든 case...

문제 바로가기 문제 접근 >1. while문을 사용해서 주어진 규칙을 따라 n번만큼 반복 후 그 문자열에서 slicing으로 해당 범위 구한 후 count('1') >> 예상했지만 시간초과 발생 마찬가지로 while문 사용하지만 주어진 범위의 길이가 천만으로 제한되어 있기 때문에 범위가 포함되는 부분적인 문자열만 구한 후 indexing 정답 코드 1 ...

문제 바로가기 문제 접근 > 1. while문을 두 번 사용해서 모든 k의 배수에 대해서 확인 >> 당연히 시간초과 발생 가능한 x값들 내에서만 모든 k의 배수에 대해서 확인 >> 시간 줄어들었으나 여전히 시간초과 가능한 x값들 내에서의 y값을 구하고 그 값의 범위 내에서의 k에 대한 배수의 개수를 count 정답 코드 3번 접근 > 딱히 새로운 접근...

1강 바로가기 알고리즘 설계 Tip >- python의 경우 1억번의 연산 횟수 당 1초 정도, 시간초과의 경우 1억 이상의 연산 횟수를 가지면 시간초과가 걸린다고 생각하면 된다. 예를 들어 주어진 수가 1~10000이라고 할 때 이중 for문 ( O(n^2) )의 시간 복잡도를 가질 경우 시간 초과가 일어날 거라고 생각하고 풀면 된다. 기업 코테의 경우 ...

2강 바로가기 그리디 알고리즘 > 현재 상황에서 가장 좋은 것만 고르는 방법 최소한의 아이디어는 필요함 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토한다 최적의 해를 보장할 수 없는 경우가 많은데, 코테에서는 그리디 알고리즘으로 얻은 해가 최적의 해가 되도록 설정해서 문제를 낸다. 예시 거스름 돈 : 거슬러 줄 때...

while로 접근 : 당연히 시간초과heap 자료구조로 접근 (heap은 그 최솟값을 추출하기 용이)heap 시간초과 : list로 되어있는 값의 sum, len을 이용해서 그 때 그 때 비교했는데 이 부분에서 시간이 미세하게 더 걸려서 초과 > 최대한 상수로 정의해서

문제 바로가기

문제 바로가기 문제 접근 > plans 수 최대 1000개.. 그냥 단순 구현 진행하다가 멈추는 과제는 ing에 담고, 끝난 과제는 fin에 담아서 기록 현재 시간은 time_change를 통해 int값으로 정의 현재시간 + 걸리는 시간과 다음 과제 시작 시간을 비교하면서 fin,ing비교 만약 과제를 끝낸 현재시간과 다음 과제 시작 시간 간에 간격이 발...

문제 바로가기 문제 풀이 > checkp, checkpnum으로 팰린드롬과 소수를 판별하는 함수를 정의한 뒤 두 함수의 return값이 모두 1일 때의 출력을 구했다 이 때 1은 팰린드롬이긴하지만 소수가 아니어서 1일 때는 2로 출력해주는 예외를 적어줘야 한다.(...) 정답 코드 추가적인 개념 (optional) 소수임을 판단하는 함수로 제곱근을 ...

문제 바로가기 문제 풀이 > 국가의 금, 은, 동에 대해 매달 순으로 list.sort(key = x lambda : x = l[0]) 이런 식으로 배열한 후에 rank를 출력하면 되는 간단한 문제 라고 생각했으나 배열을 country.sort(key = lambda x : (x[3],x[2],x[1])) 위와 같이 짜버려서 메달 순서에 따른 list 나...

문제 바로가기 문제 풀이 > 그래프는 노드와 간선으로 이루어져있으며 서로 연결된 노드의 그룹 수를 출력하는 문제. 개념 자체가 어려워서 찾아보면서 문제 풀이 진행 dfs와 bfs 중 bfs의 개념 이해 (한 노드에 연결된 노드를 우선적으로 탐색) visited와 link list를 잘 활용할 줄 알아야함. 시간 초과 문제가 있을 수 있기 때문에 impor...

문제 바로가기 문제 풀이 > bfs를 이용한 연결된 범위 탐색. 나는 visited와 graph를 따로 생각했는데 그냥 한 번에 생각해도되는 문제였다. bfs관련 문제들이 여전히 처음에 시작하는 것이 꺼려지지만 이전보다 많이 이해하고, 도전할 수 있어서 재미도 느끼고 있다. 정답 코드 추가적인 개념 (optional) > import sys를 통해 i...

문제 바로가기 문제 풀이 >주어진 상자의 x,y 좌표를 이용해서 graph를 만들고 graph가 0일 경우에만 bfs를 실행해서 인접한 영역을 모두 방문처리 한다. 이 때 더 이동할 곳이 없으면 bfs를 종료하고 regions에 +1씩 추가하며 영역의 수를 구한다. bfs내에서 q에 append시킬 때마다 (인접한 영역을 1개 발견할 때마다) cnt를 +...

문제 바로가기 문제 풀이 >- two pointer로 문제를 푸는 것이 익숙하지 않아서 itertools의 combination을 이용했다 -> 당연하게도 모든 경우를 확인하는 것이니 시간 초과가 발생 따라서 two pointer로 문제를 해결하려했다. sorted(list)에서 left, right를 지정하고 비교 대상과 크기를 비교해서 경우에 따라 l...

https://www.acmicpc.net/problem/16235 문제 풀이 > 일단 계절 별 구현 3차원 tensor 이용해서 풀이 각 나무의 나이를 리스트에 저장해서 햇수를 반복하며 실행 오답입니다 -> 5의 배수가 아닌 5 이상으로 알고 구현, 봄&여름에서 list에서 새로운 list를 이용했는데, remove를 여전히 사용하고 있어서 값의 변동이...

문제 바로가기 문제 풀이 > prices 리스트를 정의하고 가능한 가격을 모두 append시킨 후에 min(prices)를 출력한다. 한 브랜드 내에서만 구매해야하는 줄 알았다. -> A브랜드 package + B브랜드 single로 구매해서 더 싼 경우 발생 여러 브랜드도 고려해서 구매. 기타줄 개수 맞춰서 6의 배수인 경우 min(packagepric...

bfs순회로 경우를 찾되, 가장 작은 경우일 때를 출력한다.최대 거리가 주어졌으니 해당 범위에 맞춰서 수를 미리 설정해둘 수 있다.

문제 바로가기 문제 풀이 > 키가 작은 순서대로 입력, answer를 [0]*N의 list로 만들었을 때, 0의 수가 현재 사람이 기억하는 자기보다 큰 사람의 수와 같아야 성립한다. -> 본인보다 큰 사람이 있을 경우를 고려했기 때문에 계속해서 오류가 발생 정답 코드 추가적인 개념 (optional) > greedy algorithm → 미래를 생각하...

문제 바로가기 문제 풀이 >단어 길이와 단어를 함께 list에 넣은 후 key값에 따라 정렬 순서를 기재하여 정렬한다. for문의 range를 N이 아닌 수치로 지정하고, 공통되는 값을 제거해주지 않아서 오답 과정을 거침 정답 코드 추가적인 개념 (optional) > sort함수 사용법 sort(), sorting, sorted()를 매번 헷갈려하는...

문제 바로가기 문제 풀이 >1. k값을 정하고, 그 값에 따라 list를 돌면서 l과 r값을 정의한다. S를 미리 sorted했으나 처음부터 k보다 큰 값이 나오면 오류가 생겼다 -> 코드를 짤 때 특수한 경우에만 국한되지 않도록 인덱스를 이용해서 무언갈 하는 것은 좋지 못한 것 같다. cnt를 두고 이미 max값이 한 번 지정되었을 경우 더이상 변화가 ...

문제 바로가기 문제 풀이 > 단순 구현, 조금 더 고차원 list를 다루는 데에 익숙했으면 쉽게 금방 풀이를 완료했을 수 있었을 것이다. 정답 코드 다른 사람 코드 >여기서 나는 word에 대해 list를 만들고 각 원소에 대해 다시 list를 만들어서 두 개의 for문으로 접근했다면 worda형태로 한 번에 접근 가능하도록 하는 것이 코드를 간편하...

문제 바로가기 문제 풀이 >L개 이상의 연속된 수의 합으로 N을 나타내는 문제, L의 제한이 100이었으므로 하나하나 체크하는 것이 옳은 방법이라고 생각해서 while문으로 L이 100이 되는 순간까지 식을 반복했다. 식을 세우는 과정에서 약간 버벅임이 있었다. 정답 코드 추가적인 개념 (optional) > 풀이가 너무 난잡한 것 같다. N-sum ...

문제 바로가기 문제 풀이 >인근에 위치한 부등식만 만족하는 조건 하에 하나씩 찾을 것, 이 때 시간을 최소화하기 위해 max값과 min값의 순서 배열 시작을 다르게 함 max=9876543210 min=0123456789로 시작 op로 부등호를 받은 후 idx값을 이용해서 하나하나 비교, 식이 성립하지 않을 때마다 배열의 앞뒤 값을 바꿔주며 while문을...

문제 바로가기 문제 풀이 > nums로 숫자 값을 받은 뒤 그 안에 들어있는지 탐색 그냥 단순 구현 : in nums로 check했더니 시간초과 발생 ( list 내의 모든 값을 서치하는 데에 시간이 오래 걸림 ) list에서의 탐색 함수의 시간 복잡도는 O(n) 이분탐색을 이용 : l,r값을 지정한 후 sorted(nums)에서 인덱스를 이용한 크기 ...

문제 바로가기 문제 풀이 >bfs로 검색 -> 시간초과 발생 dfs로 풀이 -> 해당 위치에서의 방문 여부를 list로 구현하기보다 True/False로 구현하는 것이 더 편리, 이 때 ord()를 사용해서 그 idx를 파악했다. visited=[]로 리스트에 해당 문자가 존재하는지 여부를 파악하는 것을 조건문으로 걸었다. 이 때 반드시 방문이 끝날 때는...

문제 바로가기 문제 풀이 >첫번째 코드를 구현할 때 각 자릿수를 누를 수 있는 버튼 중 그 차이가 가장 작은 값을 불러와서 정답을 내렸다. 그러나 테스트케이스7번과 같이 target channel보다 자릿수가 작은 경우가 답인 경우에는 오답이 발생했다. 해당 케이스를 따로 구현하려하다가 단순히 전체를 탐색했을 때 답을 구할 수 있음을 알 수 있었다. 정...

문제 바로가기 문제 풀이 > 현재 단어와 다음 단어를 비교했을 때 같으면 pass, 다르면 list에 저장되어있는지 확인 후 저장되어있지 않으면 append, 이미 저장되어 있으면 cnt-=1하고 break 정답 코드 다른 사람 코드 (optional) > string에 대해서 slicing으로 문자열 일부를 자른 후 그 안에 현재의 원소가 들어있는...

문제 바로가기 문제 풀이 > 두 번의 for문을 사용 -> 시간 초과 발생, 보통 부분합은 dp를 이용한다 정답 코드 추가적인 개념 > dp에 대한 이해가 중요함 > 앞의 값을 더하지 않고 다시 수열을 시작하는 기준이 어떻게 되는지 파악할 것 -> 이 문제의 경우엔 현재까지 더한 값이 현재 값보다 작다면 굳이 앞의 값을 사용할 이유가 없으므로 해당 ...