문제 : https://leetcode.com/problems/majority-element/?envType=daily-question&envId=2024-02-12 숫자 리스트가 주어지면 n/2 번 초과로 등장하는 숫자를 반환하는 태스크 코드 : class Solution: def majorityElement(self, nums: List[int]) -> int: thresh = len(nums) // 2 num_count = collections.Counter(nums) for num, freq in num_count.items(): if freq > thresh: return num 문제에서 지정했듯이 threshold를 정해주고, collections의 Counter를 사용해 각 숫자의 빈도수를 ..

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42626# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 레벨 2 간단한 힙 문제였다 일단 주어진 스코빌 리스트를 .heapify() 시켜준 다음 주어진 공식을 while 문 안에 넣어서 스코빌 리스트에 숫자가 하나가 남을 때까지 돌려주는 거다 import heapq def solution(scoville, K): heapq.heapify(scoville) count = 0 while len(scoville) >= 2: # while l..

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 레벨 2 어떻게 풀어야할지 감도 안잡혀서 고민하다가 풀이를 찾아봤다 https://jeongmin.tistory.com/5 [프로그래머스 Level 2] 전력망을 둘로 나누기 - 파이썬(Python) ✅문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭...

1. 10828 스택 (https://www.acmicpc.net/problem/10828) 풀이시간 5분 간단한 구현 문제 import sys ​ n = int(sys.stdin.readline().rstrip()) ​ arr = [sys.stdin.readline().rstrip().split() for _ in range(n)] ​ stack = [] ​ for l in arr: if l[0] == 'push': stack.append(int(l[1])) elif l[0] == 'pop': if stack: print(stack.pop()) else: print(-1) ​ elif l[0] == 'size': print(len(stack)) ​ elif l[0] == 'empty': if stack..

[백트래킹 깨달음] DFS와 백트래킹의 차이를 뚜렷하게 알 수 있게 좀 더 연습해야겠다 하나 전 노드로 돌아가기 위해 .pop()을 하거나 호출을 따로 하나 더 하는 것 같다 백트래킹 기초를 연습하고싶다면 n과 m 문제를 전부 다 해보는 것을 추천한다 1. 15649 n과 m (https://www.acmicpc.net/problem/15649) 간단하게 from itertools import permutations를 사용해 풀 수 있는 문제이기도하다 백트래킹으로 풀면 재귀를 활용해 풀 수 있다 n, m = map(int, input().split()) ans = [] def back_track(): if len(ans) == m: # 탈출 조건 print(' '.join(map(str, ans))) r..

해시 문제를 풀다가 친구 네트워크 (https://www.acmicpc.net/problem/4195) 문제를 접하게 되었고 유니온 파인드라는 알고리즘이 있다는 것을 알았다. 두 노드가 같은 집합에 속해있는지, 혹은 두 노드가 연결되어 있는지 확인할 수 있는 알고리즘이고 굉장히 특징적인 알고리즘이다. 1. 4195 친구 네트워크 (https://www.acmicpc.net/problem/4195) https://reliablecho-programming.tistory.com/81 [알고리즘] 백준4195 친구 네트워크 - 파이썬 단계별 풀기의 유니온 파인드 세 번째 문제이다. 전에 풀었던 두 문제와 달리 배열을 예제 입력 시에 해줘야 된다는 점이었다. find함수와 union함수도 좀 다르게 구현했어야 ..

[해시 깨달음] 예상보다 내가 해시에 약한 거 같다 기본적인 알고리즘이기 때문에 더 기초를 탄탄하게 해야될 듯 하다 해시를 사용하면 탐색에 O(1), 최악의 경우에도 O(N)이 걸리기 때문에 시간복잡도를 줄이고싶다면 잘 활용해야된다 1. 10815 숫자 카드 (https://www.acmicpc.net/problem/10815) 해시(딕셔너리)로 찾으면 시간 초과가 나지 않지만 for loop으로 찾게 되면 시간 초과가 남 n = int(input()) num_card = list(map(int, input().split())) m = int(input()) is_have = {k:0 for k in list(map(int, input().split()))} for n in num_card: if n i..

1. 전화번호 목록 (https://school.programmers.co.kr/learn/courses/30/lessons/42577) (레벨 2) 처음에는 아래처럼 풀었는데 시간초과가 나와서 쓸 수 없는 코드라고 판단하여 다른사람의 답을 찾아봤다 일단 아이디어는 pivot을 설정하는 것처럼 i를 기준으로 두고 for loop을 하나 더 돌려 i+1부터 마지막까지의 전화번호를 확인한다 이 때, i 번째 전화번호와 j 번째 전화번호의 첫 숫자들이 같으면 False, 아니라면 True를 반환한다 아무래도 for loop을 두 번 사용하고 slicing까지 사용해서 시간 초과가 난 것 같다 def solution(phone_book): for i in range(len(phone_book)-1): for j..

[완전탐색 깨달음] 완전탐색은 무식하게 모든 상황을 돌려보는 유형이기 때문에 단순하게 생각하는 게 도움이 됨 대신 시간복잡도가 높은 경우가 많으니 for loop을 돌릴 때 range 설정 잘하기 1. 카펫 (https://school.programmers.co.kr/learn/courses/30/lessons/42842) (레벨 2) for loop을 두 번 돌려서 전체 블럭의 개수 (yellow + brown)의 모든 약수를 구하는 방식을 썼었는데, 시간 초과가 나와서 다른 방식을 채택함 1에서 int(yellow ** 0.5)까지 for loop을 돌려 가능한 모든 세로 길이 탐색 int(yellow ** 0.5)를 사용하는 이유는 세로 = dungeons[j][0]: curr -= dungeons..