[백준 - Gold IV] 단어 수학 - 1339 https://www.acmicpc.net/problem/1339 문제 설명 1. 영어로 이루어진 N개의 단어가 제공2. 영어 글자에 숫자(1~9)를 배정하고 합을 계산3. 이때 숫자의 합이 최대가 되었을 때 해당 합을 출력 입력값 N : 단어의 개수S : N개의 단어 출력값res : 주어진 단어의 최댓값 핵심 로직 = 가중치가장 큰 자릿수에 존재하는 글자부터 가장 큰 숫자 9 배정자주 등장하는 글자도 포함해서 계산해야 함 풀이 코드 오답 코드heapq, 우선순위 큐를 사용해서 자릿수에 대한 가중치만 생각한 코드, 자주 등장하는 글자를 체크하지 못한 것이 오답의 원인import heapqn = int(input())s = [input() for _ i..

최장증가 부분수열 - LIS(Longest Increasing Subsequendce) 주어진 수열에서 일부 원소를 골라내어 만든 부분 수열 중, 오름차순으로 정렬된 가장 긴 부분수열을 의미한다. 이때 핵심은 부분수열이 반드시 연속될 필요는 없다는 것이다. 즉 몇 개의 원소를 건너뛰어도 해당 연속으로 정렬만 되면 된다는 것이다. 예를 들어 {2, 3, 8, 6, 4, 5, 9, 1}의 경우 가장 긴 증가 부분수열은 {2, 3, 4, 5, 9}이 됨 특징부분수열의 각 원소는 원래 수열에서 순서를 지켜야 함, 연속적일 필요는 없음오름차순이므로 앞의 원소보다 뒤의 원소가 크거나 같아야 함한 수열에는 여러 개의 최장 증가 부분 수열이 존재할 수 있음 구하는 방법동적계획법 - DP각 인덱스에서 끝나느 LIS의 길..

[백준 - Silver I] 안전 영역 - 2468https://www.acmicpc.net/problem/2468 문제 설명 안전 영역이란 비에 잠기지 않은 지점들이 상하좌우로 존재하는 경우를 의미한다. 주어진 지도에서 물의 높이 H를 기준으로 안전영역의 개수를 계산하고, 이때 안전 영역이 최대가 되었을 때 영역 개수를 반환하는 것이 문제에서 요하는 출력값이다. 완전탐색으로 물 높이의 최소부터 최댓값까지 순회하며 이때 각 지역별로 정해진 높이가 h를 넘어가는 순간 BFS를 호출했다. 이때 BFS는 잠기지 않는 영역을 연결하고 BFS가 종료되면 안전영역의 카운트가 증가하는 방식으로 접근했다. 그리고 이때의 최종 카운트가 기존의 answer를 넘어가는 순간 해당 cnt로 변경하므로 최대 영역 개수를 남겼..

[Python] Programmers lv2 - 더 맵게 코딩테스트 연습 - 더 맵게 | 프로그래머스 스쿨 (programmers.co.kr) 문제 설명 주어진 조건 음식의 스코빌 지수가 담긴 리스트 스코빌 지수의 최소 요구치 리스트 내의 모든 요소들이 해당 요구치를 넘어야 한다 풀이 아이디어(기존) 주어진 스코빌 지수 리스트를 heap에 넣어준다 heap으로 들어가면 작은 순서대로 정렬이 되며 pop을 하는 경우에도 작은 순서대로 나오게 된다 heap에서 두 개의 원소를 꺼내서 조건에 맞게 조립 후 총 조립 횟수의 cnt와 요구치를 넘었는지 확인한다 풀이 아이디어 ( 오답 후 조건 추가 - 문제를 다각도로 분석 및 조건 설정의 미숙함 존재 ) 첫 번째 원소를 pop 하고 힙에 남아있는 원소가 있는지 체..

[Python] 프로그래머스 lv3 - 가장 먼 노드 코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 vertex로 연결된 정점들이 주어진다. 연결된 정점끼리의 간선은 모두 1이다. 1번 정점을 기준으로 하여 해당 정점에서 멀리 떨어진 정점의 개수를 반환하는 것이다 떨어진 거리를 dist로 하여 배열에 저장을 한다 이때 거리의 최댓값과 동일한 노드의 갯수를 반환하는 방식을 선택했다 거리를 측정하는 방법은 다익스트라 알고리즘을 사용 각 정점끼리의 거리를 최대..

[Python] 프로그래머스 lv2 - 뉴스 클러스터링 코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어진 문자열(특수문자 제외)의 교집합과 합집합을 구해서 값을 구하는 문제이다 마지막 도출 값은 교집합/합집합*65536을 곱해주고 뒤에 소수점은 버려주는 것이 조건이다 풀이 코드 각각의 문자열의 부분집합 생성 2개의 문자를 가진 문자열을 생성한다. 이때 문자열에 특수문자가 끼어있는 경우 제외한다. -> isalpha() 사용 문자열의 경우 대..