목록알고리즘 (129)
이숭간 공부기록
https://programmers.co.kr/learn/courses/30/lessons/42842?language=python3 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 문제유형 : 완전탐색 문제풀이 : yellow가 X일때 만들수있는 사각형의 가로,세로 길이를 모두 구한다. ( 가로가 세로 이상 ) ex) X=6이면 (가로,세로)일때 (6,1), (3,2) 인 사각형을 만들수 있다. 위에서 구한 각 경우에 대해서 brown의 개수를 구한다. 공식 : 노란색 사각형의 길이를 알때 걔를 둘러싼 테..
https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제유형 : 순열, 에라토스테네스의 체 문제풀이 : 주어진 문자열을 리스트로 변환후에, permutations라이브러리를 이용해 모든순열은 구한다. 다시 문자열로 만들고 숫자로 변환한뒤 (001 -> 1), 집합 자료구조에 넣는다. (중복방지) 에라토스테네스의 체를 이용하여 집합에서 가장큰 숫자를 끝으로 해서 가능한 모든 소수를 찾는다. 집합을 순..
[프로그래머스] 파이썬 _ 수식 최대화 (2020 KAKAO INTERN)
https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 문제유형 : 구현, 리스트? 문제풀이 : 나는 큐 2개를 이용해서 풀었다. 정답코드 : # 연산자의 우선순위를 재정의하여 만들수있는 절댓값이 가장 큰 숫자 # 주어지는 숫자는 모두 양수 from itertools import permutations from collections import deque def solution(expression): answer=..
[프로그래머스] 파이썬 _ 정수 삼각형
https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제유형 : DP 문제풀이 : 이문제가 왜 DP인가? (DP의 조건 : 1. 최적부분구조, 2. 중복되는 부분문제) 현재위치의 가장 큰값은 윗 줄의 가장큰값이 필요하다. 즉 특정 번째까지의 최적해는 앞의 최적해를 이용한다. ( 최적부분구조 ) 특정위치의 값을 구할때 대각선 위 값들을 비교하여 찾아낸다. 이것이 계속 반복된다. ( 중복되는 부분문제 ) 현재위치에서 가장큰 합을 저장하는 배열을 new_val이라고 했을때 new_val[i][..
https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 문제유형 : DP 문제풀이: n일때 가짓수는 n-1일때의 가짓수 + n-2일때의 가짓수이다. n-1에다가 가로길이가 1인 세로로 길쭉한 사각형을 각각 붙이는 경우 n-2에다가 가로길이가 2인 가로로 길쭉한 사각형을 각각 붙이는경우 위 두경우를 더한것이 n일때의 갯수이다. 정답코드 : 백준에서 똑같은 문제를 풀어봐서 바로 생각나서 풀수 있었다! def..
https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제유형 : 그리디 문제풀이 : 여분을 가진 학생도 도난을 당할수 있다 라는 예외처리를 잘 해주어야함 이때 해당학생은 reserve와 lost에서 모두 제거해줘야함 ( 집합의 차집합연산 이용 ) 나를 기준으로 앞에 애한테 줄수있는 상황이면 앞에애한테 먼저 주는식으로 reserve를 반복한다. 내가 만약 앞에 애와 뒤에애한테 모두 줄 수 잇는 상황일때 뒤에애한테 줘..