participant와 completion 배열의 요소 개수 파악⇒ Counter 함수를 사용하여 dictionary로 출력Counter 함수에서 제공하는 - 사용결과 값의 key 값을 list로 변경collections 모듈의 Counter 클래스Counter 클래스
string의 정렬 형태 이용 ⇒ 각 자리에 있는 요소 비교정렬이 완료된 상태로 앞 뒤 string만 비교하면 됨startswithstartwith은 어떤 문자열의 (시작~)이 어떤 문자열로 시작하는지 알려준다.두 번째 인자로 시작, 세 번째 인자로 끝-1 을 설정할
'의상의 종류'만 필요하기 때문에 따로 배열로 만든다.각 종류의 개수를 세기 위해 Counter 클래스를 사용한다.(종류+1) \* (종류+1) ... (종류+1) -1 을 해준다. -1 은 아무것도 입지 않은 경우를 빼준 것이다.
총 재생 횟수, 플레이 횟수, 고유 번호 순서대로 수록⇒ { 장르: 총 재생 횟수 }, { 장르: (고유번호, 재생횟수) }⇒ 두 종류의 Hash를 만든다.첫 번째 Dictionary를 총 재생 횟수 내림차순으로 정렬한다.정렬한 값을 기준으로 두 번째 Dictionar
stack 배열을 만들어 괄호를 push, pop할 것이다.stack이 비어있고, 괄호 ')'가 들어오면 반복문을 빠져나온다.그 외의 경우에 stack-1과 stack-2를 비교하여 다른 괄호 모양을 가지면 pop()을 해준다.range(시작, 끝, -1)range의
'\[', '{'의 경우에는 stack에 넣어준다.']'일 경우1) 바로 이전 괄호가 '\[' (즉, 배열에 무언가 있다)이면 pop 해준다.2) 그 외의 경우는 모두 거짓임으로 flag에 0을 넣어준다.'.'이 나오면 while문을 빠져나온다.import syssys
가격의 개수만큼 0, 0, 0, ... 0으로 채워진 배열을 만든다.prices의 마지막 결과는 무조껀 0이므로 길이-1만큼 반복문을 돌린다.i번째를 기준으로 (i+1) ~ (끝)까지 비교한다.i번째보다 그 뒤가 더 크다면 반복문을 끝낸다.배열의 덧셈과 곱셈
필요한 작업 일수를 배열로 만들어 date에 저장한다.date의 길이만큼 반복문을 돌리면서 stack-1와 stack-2 를 비교한다.stack-1이 stack-2보다 작으면 pop한 후, 원래의 값을 넣는다.나온 배열 원소의 갯수를 세서 배열로 반환한다.
bridge에 다리의 길이만큼 0으로 채워넣는다.배열의 개수가 있을 동안 while로 반복문을 넣는다.반복문이 한번 돌때마다 시간이 증가하므로 time에 1을 더해주고, bridge의 첫 번째 인덱스를 pop한다.만약 stack에 있는 합과 truck_weight의 첫
예를 들어 2, 3, 3, 1 이 주어졌다고 생각해보자.첫 번째 인덱스 2보다 중요도가 높은 것이 있음으로 맨 뒤로 보낸다. 그 다음, 3, 3, 1, 2 에서 첫 번째 인덱스 3보다 중요도가 높은 것이 없으므로 두번 째 인덱스 3으로 초점을 이동시켜야 하는데 해당
card에 1, 2, 3, 4, 5 가 들어있다고 가정해보자.3개의 숫자를 선택하는 방법은 첫 번째 인덱스부터 고정하여, (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4) ... (3, 4, 5)가 있다.이를 코드로 구현한 후 M보다 작은
입력받은 체스를 origin_chess에 N 형태로 넣는다.잘라낸 체스와 제대로 칠해진 체스를 비교하기 위해 흰색으로 시작하는 체스판, 검은색으로 시작하는 체스판을 배열로 만든다.잘라질 체스판의 크기는 8\*8 임으로 (0 ~ N-7) AND (0 ~ M-7)로 이중
종말을 나타내는 가장 작은 숫자 666 을 num에 저장한다.While문을 돌면서 string의 특징을 이용해 값을 구할 것이다. 입력받은 num을 string으로 변환하여 '666' 이 포함되어 있는지 확인 후, 있다면 입력받은 N값에서 1을 뺀다.예를 들어, N에
1번 수포자, 2번 수포자, 3번 수포자가 찍은 반복적인 값을 각각 one, two, three 배열에 넣는다.정답지 배열을 돌면서 각 index가 정답과 일치하는지 확인 후, 그렇다면 count 값을 올려준다.수포자 중 가장 많이 맞은 사람을 max 를 사용하여 구한
입력받은 number string 값을 number_list 배열에 넣는다.permutations 클래스는 배열의 각 원소를 조합하여 수열을 만들어준다.예를 들어 '0', '1', '1'은 '1'이 2개 있어 중복 값이 나오므로 set을 사용하여 중복값을 제거한 후 다
가로의 길이를 x, 세로의 길이를 y라 하면 x \* y 는 전체 카펫의 갯수와 같다.테두리 1줄만 갈색으로 칠해져 있기 때문에 노란색 부분의 가로는 x-2, 세로는 y-2이며 이를 곱하면 노란색 카펫의 갯수와 같다.즉, x \* y = brown + yellow 와
풀이과정 [[몸무게1, 키1], [몸무게2, 키2] ... ] 형태로 입력 받은 값을 student 배열에 append한다. i 번째 인덱스와 나머지 값을 비교하기 위해 이중 for 문을 돌린다. 조건처럼 자신보다 더 큰 덩치의 사람이 있다면, k에 1을 더해준다.
생성자는 N을 넘을 수 없음으로 N을 기준으로 for문을 돌린다.생성자는 num이며 1부터 시작한다.num의 각 자리수를 num_list 배열에 넣는다.각 자리수와 num의 합이 N이라면 반복문을 빠져나오고, 그렇지 않으면 num 값에 1을 더해 N과 같아질 때까지 반
예를 들어, 4200원 이라면 1000원을 4번 더하고, 100원을 2번 더하는 방식으로 문제를 풀었다. 하지만 결과는 시간초과!!!낮은 가격은 문제 없지만, 높은 가격의 경우 더해야할 횟수가 많아서 그런 것 같다. While을 쓸 때 주의하자.입력 받은 동전들을 re
입력받은 회의실 시간을 정렬한다. 시작 시간, 끝나는 시간 형태로 meeting 배열에 넣는다.result 배열에 조건에 맞는 회의실을 넣을 것이다. 조건 1)의 경우, 다음 회의실 조건에 부합하기 때문에 result에 append한다. 조건 2)의 경우, 더 많은 회
sort()를 하면 시간이 최소로 나온다.이중 for 문을 돌려가면서 모든 값을 더한다.
10 + 20 - 30 + 40 + 50 - 60 + 70 이 주어졌다고 가정해보자.(10+20) - (30+40+50) - (60+70) 과 같이 - 를 기준으로 괄호를 묶고, 맨 앞 연산을 제외하고 모두 빼주면 가장 작은 값이 나온다.result 배열을 만들고 (
1\. 임의의 배열 stack을 만든다.여벌 체육복을 가져온 학생이 체육복을 도난당한 경우를 빼주기 위해 만든다.reserve 배열을 돌면서, lost에 원소가 들어있으면 stack에 넣어준다.stack에 있는 원소가 lost, reserve에 있으면 제거한다.2\.
풀이과정 1. 문자열 number을 int형으로 바꾼 후 배열에 넣는다. 2. stack 배열을 만들어 count가 k값이 될 때까지 반복한다. stack이 비어있을 땐 number[n] 값을 넣는다. 들어갈 number[n]이 stack[-1]보다 크면 sta
1\. people 배열을 정렬한다.2\. i = 배열의 첫 번째 인덱스, j = 배열의 마지막 인덱스를 넣는다.이중 for문 대신 양 끝에서부터 비교해야 효율성 좋다.3\. 양쪽 끝을 비교한다.i와 j의 합이 limit 이하면, count (필요한 보트)를 올려주고,
1\. routes의 길이 만큼 상태를 저장하는 배열 status를 만든다.원소 값이 1이면 단속 카메라를 만난 것이고 0이면 아직 만나지 않은 것이다.끝나는 기점을 기준으로 routes를 정렬한다.2\. routes 배열을 for문을 돌리면서 i번째 인덱스를 검사한다
최소 신장 트리 (MST) 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것 간선의 가중치의 합이 최소 사이클 포함 X Kruskal MST 탐욕적인 방법(그리디)을 이용하여 모든 정점을 최소 비용으로 연결 https://gmlwjd94
remove() 는 처음부터 탐색하는 아주 비효율적인 함수O(n^2) 의 시간복잡도from collections import CounterCounter 빼는 2가지 방법
주어진 배열 array를 c\[0]-1부터 c\[1]까지 자른다.오름차순 정렬한다.정렬된 배열에서 c\[2]-1 번째 원소를 찾는다.
요일과 달을 저장할 배열 week와 month를 만든다.2016년 1월 1일은 금요일으로 'FRI'부터 시작한다.윤년은 2월 29일이 있는 년도이다.a-1 달까지 더한 후, b-1 일을 더하고, 7로 나눈 인덱스 값이 답이다.
s가 홀수인 경우, 2로 나눈 값의 위치를 구한다.s가 짝수인 경우, (2로 나눈 값 - 1)부터 (2로 나눈 값 + 1) 까지 자른 위치를 구한다.
arr 배열을 돌면서, 같은 숫자가 있는 경우 원소를 제거한다.for i in arr\[:] 반복문 안에서 remove()는 효율성이 낮다.curr라는 변수에 들어갈 값을 담아두고, 이전과 다른 값이면 넣어준다.
lambda 함수의 filter을 이용한다.for 문을 돌면서 나눠 떨어지는 값을 answer에 넣는다.방법2가 조금 더 빠르다. 쉽게 풀리는 문제의 경우, 굳이 함수를 쓰지 않아도 될 것 같다.
이중 for문을 사용한다.moves 배열을 반복하며 순서대로 위치에서 인형을 빼낸다.board 배열의 첫 번째 인덱스가 가장 위에 있는 인형이다. 즉, board 배열을 반복하면서, 칸이 비어 있는 경우에는 다음 칸으로 내려온다.문제에서 주어진대로 0 값을 만나면, 다
permutation(조합) 을 이용한 방법이다.2개를 조합하여 comb 배열에 넣는다.comb 배열을 돌면서, 각 원소를 더해준 후 중복을 제거한다.permutation(조합) 을 이용한 방법이다.2개를 조합하여 comb 배열에 넣는다.comb 배열을 돌면서, 각 원
현재 정점에서 연결된 가까운 점들부터 탐색하는 방법큐(Queue) 자료구조 이용pop(0) 은 시간복잡도가 O(N) 이라 매우 비효율적인 코드가 만들어 진다. 따라서 collections 라이브러리의 deque를 사용한다.현재 정점에서 갈 수 있는 점들까지 들어가면서
사진과 같은 모양이 4번 반복되어 있다. 해당 사진에서 멀쩡하지 않은 사각형의 개수는 가로(2) + 세로(3) - 1 이다. 즉, "가로 + 세로 - 가로와 세로의 최대 공약수"는 멀쩡하지 않은 사각형의 개수이다.전체 사각형에서 멀쩡하지 않은 사각형의 개수를 뺀다.최대
주어진 skill을 list로 만든다. skill_trees 배열을 돌면서 각 문자에 skill에 들어있는 알파벳이 있다면 stack에 담는다.stack에 담긴 알파벳과 skill에 담긴 알파벳의 인덱스가 같다면 count에 1을 더한다. 가능한 스킬 트리는 count
aabbaccc를 1개, 2개 ... 8개 단위로 자른다. 예를 들어 1개를 기준으로 자른다고 했을 때, 'a', 'a', 'b', 'b', 'a', 'c', 'c', 'c'가 stack에 담기고 이를 다시 result에 담는다. num이 문자열의 길이 + 1가 되면
stack 배열을 만든다.stack이 비어있고, '('라면 stack에 담는다. ')'라면 False를 리턴한다.stack이 비어있지 않을 때는 괄호를 담는다. 만약 stack에 담긴 값이 '('와 ')'라면 짝이 맞기 때문에 stack에서 제거한다.반복문을 마쳤을 때
주어진 s는 문자열이다.문자열이기 때문에 20은 숫자 20이 아닌 문자 2와 0이다.{{20,111},{111}}를 예로 들어보자.s에 맨 앞의 '{'와 맨 뒤의 '}'를 제외한 {20,111},{111}를 넣는다.문자열 반복문을 돌면서 숫자 형태의 문자열은 stack
주어진 숫자 n을 2진법으로 변환한 후 1의 개수를 x에 저장한다.while문을 돌면서 값을 찾는다. 이진법 변환 bin( )
만약 n=15가 주어졌다고 한다면 num1은 1부터 시작, num2는 15부터 시작이다.연속된 숫자만 허용됨으로 반복문을 돌 때마다 num1에 1을 더해준다.num2가 0이되면 다 더해진 것으로 반복문을 정답 answer에 1을 더하고 반복문을 빠져나온다.
10진법 1 - 124나라 110진법 2 - 124나라 210진법 3 - 124나라 410진법 4 - 124나라 1110진법 5 - 124나라 1210진법 6 - 124나라 1410진법 7 - 124나라 2110진법 8 - 124나라 2210진법 9 - 124나라 24
numbers = 1, 1, 1, 1, 1 / target = 3 / return = 5\+, - 과정을 반복한다고 생각하면 된다. numbers의 개수만큼 더하고 빼고를 반복하기 때문에 numbers 배열로 for문을 돈다.calculData에 담긴 숫자에 +
팩토리얼의 공식은 1 \* 2 \* 3 \* ... \* (n-1) \* n 이다.입력받은 n이 1일 경우 1을 리턴하고 나머지 수는 재귀를 이용하여 구한다.
피보나치수는 0 1 1 2 3 5 8 ... 으로 n번 째 수는 (n-1) + (n-2) 값이다. 0과 1의 경우는 자기 자신을 리턴하고 나머지 수는 재귀를 이용하여 구한다.
색종이를 2차원 배열로 받는다. input() 대신 sys.stdin.readline() 을 사용하면 효율성이 더 좋다.구해야 할 하얀색, 파란색 색종이는 global로 받아야한다.첫번째 위치의 색종이 색깔을 color에 담는다.나눠진 부분의 이중 for문을 돌면서 하
종이를 2차원 배열로 받는다. input() 대신 sys.stdin.readline() 을 사용하면 효율성이 더 좋다.구해야 할 종이는 global로 받아야한다.첫번째 위치의 색종이 색깔을 color에 담는다.나눠진 부분의 이중 for문을 돌면서 하나라도 color와
10^11 % 12 를 구해야 한다고 가정해보자.첫 번째 시도의 방법은 10 \* 10 \* ... \* 10 처럼 10을 있는 그대로 11번 곱하는 방법이다. 하지만, 곱하는 수가 커지면 런타임 오류가 발생한다.따라서 최대한 곱하는 수를 줄여줘야 한다. (10^5)\
문자열을 구해야하는 문제임으로 result 변수에 빈 문자열을 넣는다.쿼드트리의 순서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래이다. \[x]\[y]의 경우, for문을 돌 때, x는 고정된 채로 y만 움직이기 때문에 쿼드 트리의 순서와 일치하지 않는다. 따라서
1~4번 원판을 두 번째 장대로 옮긴다. 5번 원판을 세 번째 장대로 옮긴다.1~4번 원판을 세 번째 장대로 옮긴다.
Bottom-up : 작은 문제부터 차례대로 푸는 방법Top-down : 큰 문제를 작은 문제로 쪼개면서 푸는 방법
fibonacci(0) = 0 출력(1) + 1 출력(0) = 1fibonacci(1) = 0 출력(0) + 1 출력(1) = 1fibonacci(2) = 0 출력(1) + 1 출력(1) = 2fibonacci(3) = 0 출력(1) + 1 출력(2) = 3fibona
N = 1 일 때 '1개' => 1 N = 2 일 때 '2개' => 00, 11 N = 3 일 때 '3개' => 001, 100, 111 N = 4 일 때 '5개' => 0011, 0000, 1001, 1100, 1111 N = 5 일 때 '8개' => 00111, 0
1 → 1 → 1 → 2 → 2 → 3 → 4 → 5 → 7 → 9발견한 규칙P(N) = P(N-2) + P(N-3)
시간 복잡도: O(2^n)시간 복잡도: O(n)Bottom-up : 작은 문제부터 차례대로 푸는 방법 (파이썬 추천)Top-down : 큰 문제를 작은 문제로 쪼개면서 푸는 방법https://velog.io/@polynomeer/%EB%8F%99%EC%A0%8
house 배열 안에 입력 받은 빨강, 초록, 파랑색 비용을 넣는다.동적 계획법을 이용하여, 배열의 앞에서부터 값을 더해나간다.house의 마지막 배열 요소 중 최소 값을 찾는다.
triangle 배열 안에 위층부터 아래층으로의 숫자 배열을 넣는다.\[3, 8] 과 \[8, 1, 0]으로 예를 들어보자. 8(j=0) 일때는 3에만 영향을 받는다. 1 일때는 3 과 8 중 큰 숫자에 영향을 받는다. 0(len(triangle\[i])-1) 일때는
stairs 배열에 계단 점수를 넣는다.계단이 1칸일 때는 1칸을 밟으면 최댓값이 된다.계단이 2칸일 때는 2칸 모두 밟으면 최댓값이 된다.계단이 3칸일 때는 1번째 + 3번째 or 2번째 + 3번째를 밟으면 최댓값이 된다.계단이 4칸 이상일 때는 마지막 도착 계단은
좋은 풀이 아님!! 배열로 다시 풀기!!n은 100 이하의 수, 따라서 각 숫자에 \[0] \* 100 배열을 만든다.첫 번째 자리에는 0(zero) 이 올 수 없음으로 zero를 제외하고 나머지 숫자 배열의 첫 번째 인덱스에 1을 넣는다.두 번째 자리를 기준으로,0은
LIS 란? > Longest Increasing Subsequence (최장 증가수열, 최대 증가 부분수열) LIS는 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열을 말한다. 증가에는 순증가와 단조증가가 있는데, 순증가는 앞
비슷한 문제 백준 - 2579번 계단 오르기 https://velog.io/@minidoo/algorithmbaekjoon2579 계단 오르기 문제와 다른 점은 마지막 포도주를 마시지 않아도 된다는 것이다. 풀이과정 wine 배열에 포도주를 넣는다. 포도주가
백준 - 11053번 가장 긴 증가하는 부분 수열https://velog.io/@minidoo/algorithmbaekjoon11053LIS 를 구하는 것과 결국 같은 문제이다.S1 < S2 < ... Sk-1 < Sk > Sk+1 > ...
LIS(최장 증가수열)을 이용하는 문제전봇대A와 전봇대B를 이차원 배열의 형태로 wire에 넣는다.전봇대A를 기준으로 정렬한다.만약 전봇대A의 1번이 B의 8번 전깃줄을 선택했다면, 그 아래 전깃줄은 B의 9번 이상의 값과 연결되어야 겹치지 않는다.위의 설명을 바탕으로
LCS(Longest Common Subsequence)LCS 는 두 문자열의 sub sequence가 같을 때, 가장 긴 길이를 구하는 문제출처: https://suri78.tistory.com/11
연속합은 동적 계획법의 가장 기본적인 문제이다.배열로 받은 값들을 앞에서부터 비교하면서 i번째 값과 그 전까지의 합을 비교해 더 큰 값을 넣는다.동적 계획법 방법을 생각하지 못했을 때, 더한 모든 값을 비교했다.당연히 시간 초과가 난다!동적 계획법을 좀더 잘 적용하는
출처 : https://claude-u.tistory.com/208
선입선출(FIFO)의 자료구조( 출처: 큐(자료구조) 나무위키 )먼저 들어오는 데이터가 먼저 나가게 되는 자료구조이다.파이썬에서 Stack 은 일반 배열을 사용하지만 Queue 은 deque 를 사용하면 시간 효율성을 높일 수 있다.
N = 7, K = 3arr = \[1, 2, 3, 4, 5, 6, 7]첫 번째 while문을 반복했을 때, arr = 4, 5, 6, 7, 1, 2 / result = 3 두 번째 while문을 반복했을 때, arr = 7, 1, 2, 4, 5 / resul
N = 4, M = 2arr = \[1, 2, 3, 4] 라고 했을 때, M 값인 2번째 위치의 2가 출력되는 순서가 궁금한 문제arr의 인덱스를 가진 배열 arrIndex를 만들어준다.arr의 변화가 일어날 때마다, arrIndex도 똑같이 적용해주면 된다.
양쪽에서 모두 삽입/인출이 가능한 스택과 큐의 특징을 모두 갖고 있는 자료구조( 출처 : 큐(자료구조) 나무위키 )
주어진 설명을 해석하는 것이 가장 어려운 문제였다...!N = 10, M = 3loc = \[ 2, 9, 5 ]arr = \[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]우리가 arr 배열에서 찾아야 할 숫자는 2, 9, 5 이다.n은 2번 연산, m은 3
처음에 이 문제에 접근했던 방법은 배열을 돌면서 R이 나올 때마다 뒤집고 D가 나올 때마다 삭제했었다. 하지만, 이 방법은 시간 효율성이 매우 떨어진다.배열의 갯수가 100,000개 까지 가능하기 때문에 매 순간 적용하는 것은 비효율적이다.첫째, 'RR'은 두 번의 뒤
백준 - 1051번 숫자 정사각형