전체 글

https://programmers.co.kr/learn/courses/30/lessons/72412

https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 내 풀이: def solution(s): stack = [] result, ans = [], [] for char in s[1:-1]: if char == '{': stack.append(char) elif char.isdigit(): stack[-1] += char elif char == ',': stack[..

https://programmers.co.kr/learn/courses/30/lessons/67257/ 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 내 풀이: from itertools import permutations # 수식을 해당 연산자에 대해 연산한 후의 수식 리턴 def calculate(operator, expression): new_exp = [] i = 0 while i < len(expression): if expression[i] == operator: new_exp.append(st..

https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 내 풀이: from collections import defaultdict from ite..

https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 내 풀이: from collections import defaultdict def make_table(str): table = defaultdict(int) for i in range(len(str) - 1): if str[i:i + 2].isalpha(): table[str[i:i + 2].lower()] += 1 return table ..

https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr * 해결 못 함 # 문자열 p를 u, v로 분리하는 함수 def divide(p): open = 0 close = 0 for i in range(len(p)): if p[i] == '(': open += 1 else: close += 1 if open == close: return p[:i + 1], p[i + 1:] # 문자열 u가 올바른 괄호 문자열인지 확인하..

[2022 NCSOFT SUMMER INTERN] 일시: 2022.05.14(토) 11 ~ 13시 응시 환경: 프로그래머스 사용 가능 언어: C++, Java, JavaScript, Python3, MySQL 서머 인턴 '웹 서비스 개발' 분야에 지원하여 코테 체험을 해보고자 지원했다. 자소서도 500자 이내로 무난한 질문 2개로 부담없었다. 화상감독 X 두시간 동안 세 문제가 나왔으며, 파이썬으로 응시했다. 두 문제는 평이한 구현문제, 한문제는 SQL로만 풀 수 있는 문제가 출제되었다. 공고에서 SQL 관련해서 코테에 나온다고 정확히 명시가 되지 않아 전날에 이메일과 문자로 온 코테 안내사항에서 처음 발견했다. SQL은 공부한 적이 없어 전날 부랴부랴 몇 시간만 체험(?)해보고 시험에 응시했다. 예전 ..

다이나믹 프로그래밍: 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성 대부분의 재귀 알고리즘은 최적 부분 구조 문제를 풀 수 있음 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해나감 알고리즘 풀이 가능한 문제들의 특징 풀이 가능한 문제 및 알고리즘 다이나믹 프로그래밍 - 최적 부분 구조 - 중복된 하위 문제들 - 0-1 배낭 문제 - 피보나치 수열 - 다익스트라 알고리즘 그리디 알고리즘 - 최적 부분 구조 - 탐욕 선택 속성 - 분할 가능 배낭 문제 - 다익스트라 알고리즘 분할 정복 - 최적 부분 구조 - 병합 정렬 - 퀵 정렬 다익스트라 알고리즘 - 최적 ..

분할 정복: 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임 직접 해결할 수 있을 정도로 간단한 문제가 될 때 까지 문제를 재귀적으로 쪼개나간 다음(분할), 그 하위 문제의 결과(정복)들을 조합하여 원래 문제의 결과로 만듦(조합) 재귀를 활용하는 대표적인 알고리즘, 최적 부분 구조 169. Majority Element - 브루트 포스 -> 하나하나 count() 메소드로 세다가 과반수인 요소 나오면 리턴 - 다이내믹 프로그래밍 -> 리스트 순회하며 처음 출현한 요소는 count()메소드로 세고, 나왔던 요소는 과반수인지 확인 - 분할 정복 -> 재귀적으로 쪼갠 후 과반수 후보 하나만 상위로 계속 리턴 ※ 비교 연산자로 true | false 반환하여 1 | 0으로 활용 - 리스트를 정렬하면 정..

그리디 알고리즘: 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 대부분 뛰어난 결과를 도출하지 못하지만, 드물게 최적해 보장 최적해를 찾을 수 있으면 그것을 목표로 삼고, 그것이 어렵다면 주어진 시간 내에 최적에 가까운 해를 찾음 탐욕 선택 속성 + 최적 부분 구조 에 해당하는 문제에 좋다 탐욕 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는 것 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우 예) 다익스트라, 허프만 코딩, ID3 DP vs Greedy DP: 하위 문제에 대한 최적 솔루션을 찾고, 이 결과들을 결합한 정보로 전역 최적 솔루션 선택 Greedy: 각 단계마다 로컬 최적해를 찾는 문제로 접근..