본문 바로가기

Algorithm43

[프로그래머스] 파이썬 - 모음사전 문제 풀이1. 모든 경우의 수 구하기from itertools import productdef solution(word): answer = 0 alphabet = ['A', 'E', 'I', 'O', 'U'] array = [] for i in range(1,6): for j in product(alphabet,repeat = i): array.append(''.join(j)) array.sort() return array.index(word)+1 product를 사용하여 1~5 길이의 모든 단어의 경우의 수를 구해주었다.이후 배열에서 word의 인덱스를 구해주고 1을 더해주면 답이 나온다. 2. dfsdef dfs(word,.. 2024. 10. 7.
[프로그래머스] 파이썬 - 점찍기 문제풀이처음 작성한 코드def solution(k, d): answer = 0 for i in range(0,d+1,k) : for j in range(0,d+1,k): if (i**2 + j**2)  문제 조건을 그대로 입력했다.k와 d의 제한사항이 각각 최대 백만이기 때문에, 이중 for문을 사용하면 안되는 문제였다. 따라서 아래 공식을 이용하여 j의 값을 구해주었다.피타고라스 정리에 의해 i² + j² = d² 이므로 (i는 x축, j는 y축, d는 최대 길이이다)j² = d² - i² 이다. 이 공식으로 j를 구한 후 j를 k로 나눈 정수 몫 + 1이 해당 i값이 x값일 때의 j값의 개수이다.  정답 코드def solution(k, d): a.. 2024. 10. 3.
[프로그래머스] 파이썬 - 이모티콘 할인 행사 문제제한 사항  풀이# 각 이모티콘의 할인율에 대한 모든 경우의 수를 구하는 dfsdef dfs(temp, depth): global array percentage = [10,20,30,40] # 이모티콘의 개수 만큼 dfs가 돌았을 때 if depth == len(temp): # 얕은 복사를 통해 새로운 temp 생성 array.append(temp[:]) return for p in percentage: temp[depth] += p dfs(temp, depth + 1) temp[depth] -= p 각 이모티콘들은 10, 20, 30, 40의 할인율 중 하나의 할인율을 가질 수 있다.따라서 .. 2024. 10. 1.
[프로그래머스] 72411 파이썬 - 메뉴 리뉴얼 문제풀이문제를 보면 orders의 길이와 course의 길이가 매우 짧게 주어진다.따라서 모든 경우의 수(조합)을 구하여 해결할 수 있는 문제이다.단, 조합을 뽑은 후 반드시 정렬을 해서 딕셔너리에 넣어야 올바른 정답을 얻을 수 있다.  오늘 배운 것 딕셔너리 key값 탐색 if frequency[i] not in new_frequency.keys() 파이썬 딕셔너리에 값을 추가할 때 그동안은 위와 같이 key값들에 접근해서 이미 존재하는 키인지 확인해왔다. if i not in new_frequency그러나, in 키워드는 딕셔너리에서 기본적으로 키만 확인한다고 한다.따라서 new_frequency.keys()로 작성하지 않고 new_frequency로 적어도 동일하게 코드가 작동한다.위와 같이 작성하.. 2024. 9. 24.
[프로그래머스] 340212 파이썬 - 퍼즐 게임 챌린지 문제 풀이 문제 자체는 간단했다.난이도 배열을 돌며 현재 레벨보다 난이도가 낮을 때와 높을 때를 나누어 시간을 계산해주고,더한 시간이 limit보다 낮을 경우의 level의 최솟값을 구하면 되는 문제. 나는 난이도 배열을 돌며 시간을 계산하는 함수를 만들었고, 해당 함수에 level만 바꾸어 넣어주며정답을 구했다. 코드첫번째 (틀린) 코드시간초과가 난 코드이다def solution(diffs, times, limit): answer = 1 # 작은 수부터 level 설정해서 계산 while(True): if puzzle(answer,diffs,times,limit): break answer += 1 return answerd.. 2024. 9. 24.
[백준] 1038 파이썬 - 감소하는 수 문제https://www.acmicpc.net/problem/1038 풀이진짜 너무 오래걸려서 풀었다. 첫번째 풀이감소하는 수의 입력 조건이 1,000,000 이하인줄 알고 for문을 돌며 감소하는 수인지 검사했다.문제를 푼 후 제출했을 때 31퍼센트에서 계속 '틀렸습니다'가 떠서 머리를 쥐어뜯었다.알고 보니, 감소하는 수 중 가장 큰 수인 9876543210까지 구해야 하는 거였다.입력 조건은 N번째 감소하는 수를 구할 때의 N의 조건이었다. (문제 좀 잘 읽자.. ) 두번째 풀이1부터 9876543210 사이 수를 for문으로 돌리고, 시간복잡도를 줄일 for문을 탈출하는 조건을 추가해야된다고 생각했다.사실 조건부터 시간복잡도가 말이 안된다. 이건 아닌 것 같았다.dp문제인가 싶었지만 부합하는 조건을.. 2024. 9. 20.
[백준] 23881 파이썬 - 선택 정렬 1 문제https://www.acmicpc.net/problem/23881 풀이선택정렬 알고리즘을 사용해서 문제를 풀면 된다. 선택 정렬이란?1. 주어진 리스트 값 중에 최소값을 찾는다.2. 그 값을 맨 앞에 위치한 값과 swap 한다.3. 위 작업을 반복한다. - 선택 정렬의 시간복잡도 : O(N^2)- 공간 복잡도: O(1)  코드n,k = map(int,input().split())numbers = list(map(int,input().split()))cnt = 0def selection(numbers): global cnt ans = [] for i in range(n-1, 0, -1): max,index = numbers[0],0 for j in range(.. 2024. 9. 17.
[백준] 2583 파이썬 - 영역 구하기 문제https://www.acmicpc.net/problem/2583 풀이입력에 따라 직사각형을 입력받고,bfs를 통해 영역을 판별하여 넓이를 구하면 되는 문제이다. 입력을 받을 때, 모눈종이의 왼쪽 아래 꼭짓점의 좌표가 (0,0)으로 선언되어있어 약간 헷갈렸으나우리가 아는 대로(왼쪽 위가 (0,0)좌표) 코드를 작성해도 답을 도출하는 데에는 전혀 문제가 없다. 코드from collections import dequerow, column, k = map(int,input().split())matrix = [[1 for _ in range(column)] for _ in range(row)]for _ in range(k): lx,ly,rx,ry = map(int,input().split()) f.. 2024. 9. 9.
[프로그래머스] 42890 파이썬 - 후보키 풀이문제에서 relation이라는 2차원 문자열 배열 안에 학생들의 인적사항이 주어진다.인적사항의 column(열) 속성들에 대해, 유일성과 최소성을 만족하는 "후보키"를 구하는 문제이다.  다음과 같이 컬럼의 길이는 최대 8로 주어진다.따라서 파이썬의 combinations를 사용하여 모든 컬럼의 조합을 구했다. (조합의 시간복잡도는 2 ^ 컬럼의 길이 = 256) 1. 모든 컬럼의 조합을 구한다.2. 각 조합에 대해 유일성을 검사한다    2-1. 집합(set()) 에 각 조합의 인덱스의 값들을 문자열로 변환한 값을 넣는다.    2-2. 만약 해당 집합의 길이가 row의 길이와 같으면 겹치는 값이 없는 것이므로 유일하다.3. 유일한 조합들을 모아놓은 candidate 리스트에 대해 최소성을 검사한다.. 2024. 9. 9.

티스토리툴바