말하는대로

[알고리즘/Python] 해시(Hash) vs 정렬(Sort) 성능 비교 : O(N) 최적화 경험 (feat. 완주하지 못한 선수)

1. 문제문제: 프로그래머스 - 완주하지 못한 선수유형: 해시 (Hash)난이도: Level 1목표: 마라톤 참여자 중 완주하지 못한 단 한 명을 찾아내야 한다. (동명이인 존재 가능)2. 첫 번째 접근 : 정렬(Sorting) 활용처음에는 가장 직관적인 방법으로 접근했다. 두 리스트를 모두 정렬한 뒤, 순서대로 비교하다가 달라지는 부분이 있다면 그 사람이 완주하지 못한 사람이다.def solution(participant, completion): # 1. 두 리스트를 정렬 (O(N log N)) participant.sort() completion.sort() # 2. zip으로 묶어서 순서대로 비교 for p, c in zip(participant, completion): ..

Codeclass Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hash_1 = {} for i in range(len(nums)): if nums[i] in hash_1: return [i,hash_1[nums[i]]] comp = target - nums[i] hash_1[comp] = i시간 복잡도: O(n)간단하게 푼다면 이중포문을 이용해서 O(n^2) 으로도 푼다.class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]..

🍙 백준 28282 - 미니김밥 천국 처음엔 BFS/DFS 문제인 줄 알았는데, 알고 보니 정확히 K번의 행동으로 N번 계단에 도달 가능한지를 묻는 DP 문제였다. DFS는 시간 초과, BFS는 메모리 초과, 슬라이딩 윈도우도 모두 실패… 결국 DP로 갈아탐. 🚀 문제 핵심 정리 0번 계단에서 시작 총 K번 행동 가능 행동 종류: 1칸 걷기 → i → i+1 워프 → i → i + floor(i/2) 정확히 K번 행동해서 N번 계단에 도달하면 "minigimbob", 아니면 "water" 출력 🧠 접근 방식 - 1차원 DP dp[i] = i번 계단에 도달하는 최소 행동 수 를 저장하..

📝 TIL - 프로그래머스 신규 아이디 추천 📌 문제 요약 사용자로부터 입력된 아이디가 조건에 맞지 않을 경우, 주어진 규칙에 따라 새로운 아이디를 추천하는 문제입니다. 📚 학습 내용 정규표현식을 활용한 문자열 정제 조건문과 슬라이스를 활용한 문자열 길이 조정 문자열의 시작/끝에서 특정 문자 제거 (마침표) 로직을 함수로 분리하여 재사용성 및 가독성 향상 🔧 주요 로직 요약 모든 대문자를 소문자로 변환 허용되지 않은 문자 제거 연속된 마침표는 하나로 축약 시작/끝에 위치한 마침표 제거 빈 문자열이면 "a"로 대체 길이가 16자 이상이면 자르고, 끝이 마침표면 제거 길이가 2자 이하이면 마지막 문자를 반복하여 길..

🧠 TIL - DP로 N초 동안 가능한 스킬 조합 수 구하기 오늘은 스킬의 사용 시간 제약이 있는 조합 문제를 DP로 해결해봤다. 핵심은 dp[i]가 “i초를 채우는 방법의 수”를 의미한다는 점이다. 📌 문제 요약 스킬 A: 1초 스킬 B: m초 총 N초를 정확히 채울 수 있는 모든 조합의 수를 구하라 결과는 1,000,000,007로 나눈 나머지 출력 📄 핵심 점화식 dp[i] = dp[i - 1] + dp[i - m] (단, i ≥ m) 🔍 코드 설명 nanoom = 1_000_000_007dp = [0] * (n + 1)dp[0] = 1 # 0초는 아무 것도 안 쓰는 1가지 방법for i in range(1, n + 1): dp..

🧠 TIL - JadenCase 문자열 처리 오늘은 문자열을 JadenCase로 바꾸는 문제를 풀었다. 핵심은 단어별로 첫 글자는 대문자, 나머지는 소문자로 만드는 거고, 숫자로 시작하는 경우는 소문자만 처리하면 된다. 📌 예시 input : "3people unFollowed me"output: "3people Unfollowed Me" 💡 핵심 로직 def solution(s): answer = '' for i in s.split(" "): if i == "": answer += " " elif i[0].isalpha(): answer += i[0].upper() + i[1:].lower..

🧠 TIL - 이진탐색 과자 나눠주기 오늘은 다시 한 번 이진탐색 개념을 정리했다. 직접 구현할 땐 while문 범위나 mid 조정에서 종종 헷갈려서, 이번에 완전히 패턴을 잡아놔야겠다고 생각했다. 📌 개념 이진 탐색은 정렬된 탐색 범위 내에서 특정 조건을 만족하는 값을 찾는 방식이다. 중간값(mid)을 기준으로 탐색 범위를 반씩 줄여가며, 조건을 만족하는지 확인하고 범위를 조정한다. 🧩 기본 구조 start = 최소값end = 최대값answer = 0while start ❓ 왜 이렇게 하는가 start : 탐색이 끝나기 전까지 조건을 만족: 일단 저장하고 더 큰 쪽 탐색 조건 불만족: 무조건 줄여야 하니까 end 감소 ..

링크: https://www.acmicpc.net/problem/1783📌 문제 요약나이트가 체스판 위에서 이동할 수 있는데, 병들어서 **2가지 방향으로만 이동 가능**함.단, 방문 횟수에 따라 **움직일 수 있는 방향 제약 조건**이 있음.나이트는 총 4가지 방식으로 이동 가능 (실제론 2가지)세로로는 위로만 이동함총 이동 횟수에 따라 4가지 이동 방식 중 적어도 3가지 이상을 사용해야 제약이 풀림📌 분기높이 H가 1 → 움직일 수 없음 (정답: 1)H가 2 → 위로 2칸 못 가니까 최대 4번까지만 가능 (이동 방식 제한)H ≥ 3 and W 그 외에는 자유롭게 이동 가능 → W - 2칸까지 가능💻 코드n,m = map(int, input().split())def solution(n, m): ..

오늘은 그리디(Greedy) 알고리즘의 핵심 개념을 활용하는 문제인 백준 2437번: 저울을 풀어보았다. 🧩 문제 요약 여러 개의 저울추가 주어진다. 이 추들을 이용해 측정할 수 없는 가장 작은 양의 정수 무게를 구하는 문제다. 예: [3, 1, 6, 2, 7, 30, 1] → 정답: 21 🔍 핵심 아이디어 추들을 오름차순 정렬한 후, 지금까지 만들 수 있는 최대 누적합을 `target`이라 한다. 매번 다음 추의 무게 `w`를 확인하며, w > target일 경우, 그 순간 target이 측정할 수 없는 최소 무게가 된다. 🤔 왜 그렇게 되는가? 예를 들어, 현재까지 1 ~ 20까지는 만들 수 있었다고 하자. 그런..

이번 문제는 간단한 정규식 패턴 매칭 문제였습니다. 한국이 그리울 땐 서버에 접속하지[9996] 📋 문제 설명 첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(*) 한 개로 이루어져 있으며, 별표는 문자열의 시작과 끝에 있지 않다. 다음 N개의 줄에는 각 파일 이름이 주어지고, 패턴과 일치하는지 판별해야 한다. 별표(*)는 임의의 문자열(길이 0 이상)을 의미하며, 정규식의 .*와 동일하다. 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고: "DA"는 YES, "NE"는 NO를 의미한다. 🧪 입..