본문 바로가기

Algorithm/Programmers18

[프로그래머스] 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.
[프로그래머스] 42890 파이썬 - 후보키 풀이문제에서 relation이라는 2차원 문자열 배열 안에 학생들의 인적사항이 주어진다.인적사항의 column(열) 속성들에 대해, 유일성과 최소성을 만족하는 "후보키"를 구하는 문제이다.  다음과 같이 컬럼의 길이는 최대 8로 주어진다.따라서 파이썬의 combinations를 사용하여 모든 컬럼의 조합을 구했다. (조합의 시간복잡도는 2 ^ 컬럼의 길이 = 256) 1. 모든 컬럼의 조합을 구한다.2. 각 조합에 대해 유일성을 검사한다    2-1. 집합(set()) 에 각 조합의 인덱스의 값들을 문자열로 변환한 값을 넣는다.    2-2. 만약 해당 집합의 길이가 row의 길이와 같으면 겹치는 값이 없는 것이므로 유일하다.3. 유일한 조합들을 모아놓은 candidate 리스트에 대해 최소성을 검사한다.. 2024. 9. 9.
[프로그래머스] 12978 파이썬 - 배달 풀이문제를 읽어보면 1번 마을에서 다른 마을까지 거리 중 최단 거리를 구하는 문제임을 알 수 있었다. 이때, 제한사항을 읽어보니 노드(마을의 개수)가 최대 50개임을 알 수 있었다.따라서 다익스트라 알고리즘을 사용하여 풀 수 있는 문제였다. 다익스트라 알고리즘 CT-Study/PART 2/Chapter 9, 최단 경로.md at master · JeongEunJi1127/CT-Study🔎 코딩테스트 공부 결과물 정리를 위한 저장소 . Contribute to JeongEunJi1127/CT-Study development by creating an account on GitHub.github.com- 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘- 가장 비용이 적은 노드를.. 2024. 9. 9.
[프로그래머스] 67256 파이썬 - 키패드 누르기 풀이키패드의 숫자와 각 숫자에 맞는 좌표를 미리 딕셔너리에 선언해두고 풀었다.나머지는 단순 구현이었다.if문을 사용해 조건만 잘 걸어주면 어렵지 않게 풀 수 있는 문제였다. 코드def solution(numbers, hand): answer = '' keypad = {'1':(0,0), '2':(0,1), '3':(0,2), '4':(1,0), '5':(1,1), '6':(1,2), '7':(2,0), '8':(2,1), '9':(2,2), '*':(3,0), '0':(3,1), '#':(3,2)} left = keypad['*'] right = keypad['#'] for number in numbers: .. 2024. 9. 5.
[프로그래머스] 1844 C# - 게임 맵 최단거리 문제 c#으로 처음 알고리즘을 풀다 보니, 기본 문법 관련하여 모르는 것이 많아 어려움을 겪었다.문제 자체는 기본적인 BFS문제로 난이도가 높게 느껴지진 않았다. 코드using System;using System.Collections.Generic;public class Solution{ public int solution(int[,] maps) { int answer = 0; bool[,] visited = new bool[maps.GetLength(0), maps.GetLength(1)]; BFS(maps, visited, (0, 0)); if (maps[maps.GetLength(0) - 1, maps.GetLength(1) - 1] ==.. 2024. 8. 16.
[프로그래머스] 178870 파이썬 - 연속된 부분 수열의 합 (투포인터 알고리즘) 문제 이름과 제한 사항 (sequence의 길이 투포인터 알고리즘이 생각났다. 투포인터 알고리즘?- 두 개의 점의 위치를 기록하면서 처리하는 알고리즘- 특정한 합을 가지는 부분 연속 수열 찾기와 같은 문제 & 정렬되어 있는 배열 문제에 대표적으로 사용됨- 시작점은 끝점보다 작거나 같다는 조건을 항상 만족해야 한다.- 시간복잡도는 O(N)         - 포인터가 N번 증가해야 알고리즘이 끝나므로 하나의 포인터의 시간복잡도는 O(N)      2 * O(N) = O(N) 이므로 합쳐도 시간복잡도는 O(N) 풀이1. start, end 각각 0으로 설정 & 두 포인터 사이의 값의 합 sumNum = sequence[start]으로 초기화    1-1. sumNum이 k보다 크거나 같으면 start += 1.. 2024. 4. 12.
[프로그래머스] 92334 파이썬 - 신고 결과 받기 각 유저가 받은 결과 메일의 수를 출력하면 되는 문제.신고한 모든 내용을 취합, 마지막에 한꺼번에 게시판 이용 정지를 시킨다는 조건 때문에 구현이 어렵진 않았다.시간복잡도는 report의 길이가 최대 200,000 이기 때문에 이중 포문을 사용하지만 않으면 통과였다. 풀이1. id_list에 있는 id를 key값으로 가지는 dictionary에 [id가 신고당한수, 신고한 id들]을 value로 넣는다.2. report를 돌며 신고한 id,신고당한 id를 변수 a,b에 저장한다.    2-1. 만약 dic[a]가 신고한 id들(dic[a][1])에 b가 존재하지 않는다면,            dic[a][1]에 b를 append하고 dic[b]가 신고당한 수에(dic[b][0])에 1을 더한다.3. di.. 2024. 4. 11.
[프로그래머스] 133502 파이썬 - 햄버거 만들기 1은 빵, 2는 야채, 3은 고기빵 - 야채 - 고기 - 빵 순서로 쌓인 햄버거만 포장한다. 풀이1. hamburger라는 배열에 재료를 하나씩 넣는다.2. 배열의 뒤에서부터 4개를 가져와 햄버거로 포장 가능한지 검사한다. (isBurger 함수)3. 만약 포장 가능하다면 answer += 1, 포장된 재료 4개는 pop() 해준다. 코드def solution(ingredient): answer = 0 hamburger = [] for i in ingredient: hamburger.append(i) if isBurger(hamburger[-4:]): answer += 1 for _ in range(4): .. 2024. 4. 8.

티스토리툴바