무제

문제를 너무 단순하게 생각했었다 반례 보면서 열심히 수정함 내가 간과한 것들 1. 길이는 같지만 문자는 다른 접두어가 여러개 있을 수 있음 2. 나는 단어들을 sort 하고 오로지 인접한 단어만 있다고 생각했는데, 세개 이상 같은 경우일 수도 있음 ex) aaa aac aab 이 경우 sort하면 aaa aab aac 순서이지만 우선순위는 원본 순서이기 때문에 정답은 aaa aac가 된다 그래서 prefix_arr 에 최장길이의 접두어들을 저장해놓고(한개일수도 있고 여러개일수도 있음) 다시 원본 리스트에서 각 접두어를 포함하는 단어를 접두어별로 구분해서 index 모아놓음 그 중 제일 작은 index 포함하고 있는 리스트에서 맨 앞 두개가 정답이다 n = int(input()) arr1 = [] for ..

DP로 최장증가부분수열 구하기 Longest Increasing Subsequence python 방법은 두가지가 있다 하나는 이중 for문을 사용해서 o(n^2) 다른 하나는 이분탐색을 사용해서 o(nlogn)이 된다 1. o(n^2) 방법 dp배열: dp[i]를 포함한 LIS 길이 -> dp 배열 만들고 모두 1로 초기화로 시작 - 이중 for 문 -> 현재위치(i)와 이전에 있는 원소들 크기 비교 - 이전에 있는 원소가 작은경우 -> dp[i]와 dp[j]+1 중 더 큰것이 dp[i] - dp배열의 최댓값이 LIS 길이 for i in range(len(arr)): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j]+1) 2. o(nlo..

https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요. 하... 개킹받게 엉뚱한..

https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아무래도 해시 카테고리에 있는만큼 효율성을 위해 이중for문은 최대한 안쓰려 했다 그랬더니 도저히 모르겠어!!!!!!!!!!!! 해시니까 딕셔너리를 써야하나 싶다가 결국 다른 풀이를 참고했다 헐~ 근데 원리는 그냥 리스트를 이중for문 돌리는거랑 같은데 단지 탐색 전에 리스트를 set자료형으로 변경하는 절차가 있다는 점이 달랐다 답 def solution(phone_book): setbook = ..

https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에는 while문과 for문을 활용해서 s[i] == s[i-1]를 비교해서 같으면 제거하고 제거한 리스트에서 다시 또 비교하는걸 반복했다 그랬더니 아뿔싸 시간초과 질문게시판 들어갔다가 스택이라는 글자를 봐버렸다 이 힌트 없었으면 못풀었을듯 이런생각 어떻게 하는거야~~~ 스택을 만들어서 top과 같은문자면 pop 같은문자가 아니면 push 반복해서 성공적으로 수행가능한 경우면 스택이 텅 비어있..

공백이 여러개일경우 -> 공백 하나는 구분용 나머지 공백은 문자한칸 취급하여 첫 글자로 취급 -> if else 조건 추가, 앞이 공백인 경우에도 대문자변경X 그대로 추가 하씨발 또틀림!!!!!!!!!!!!!!!!!!!!!!!! 알아야할것 -> upper에 숫자 들어가면 그냥 알아서 무시함 오류안생김 내장함수 capitalize() -> 문제 그대로 조건 반영함...Apple , 1apple # 1. if word != False: if word != False: # 'word'가 'False'와 동등하지 않은 경우에 실행 # 'word'가 'False'와 동등하지 않은 모든 값(예: True, 0, 1, 문자열 등)에 대해 실행됨 # 2. if word: if word: # 'word'가 참 (Trut..

알고리즘 문제에서 최대공약수 또는 최소공배수 관련된 문제가 나오면 유클리드 호제법을 사용해야 한다. 유클리드 호제법이란... 최대공약수를 구하는 방법 두 정수 a와 b의 최대공약수(gcd)를 구하는 경우: a를 b로 나눕니다. 나눈 나머지를 r에 저장 r이 0이면, b가 최대 공약수 r이 0이 아니면, a를 b로, b를 r로 대체하고, 다시 1번 단계로 r이 0이 될 때까지 1번과 2번을 반복합니다. 예시) 24와 18의 최대공약수 구하기 a=24 b=18 24/18 = 몫:1 나머지(r):6 r이 0이 아니기 때문에 a = b로 b = r a=18 b=6 18/6 = 몫:3 나머지(r):0 r이 0이기 때문에 현재 b값, 6이 최대공약수이다. 참고로 나는 꼭 a>b 여야 하는 줄 알았는데 크기는 상관없..

백트래킹이란... 탐색 도중 막히면 이전 단계로 돌아가서 다른 경로를 시도하는 방식 재귀 활용 조건 만족하지 않는것은 제외함(가지치기로 효율up) 백트래킹의 기본 아이디어 1. 선택 2. 제약 조건 확인 3. 결과 확인 4. 재귀 호출 5. 원상태로 복귀 DFS와의 차이점 DFS는 모든 경로 탐색 백트래킹은 불필요한건 탐색X

작은문제로 쪼개서 -> 값을 재활용하기 DP를 사용하면 재귀나 완전탐색보다 효율적으로 문제를 풀 수 있다 ex) 피보나치의 경우... f(n) = f(n-1)+f(n-2) 재귀 사용시 복잡도: O(n^2) dp 사용시 복잡도: O(n) dp를 사용할수 있는 조건 1. 큰 문제를 작은 문제들로 나눌 수 있는가(동일한 작은문제들이 반복) 2. 작은 부분 문제의 값이 그것을 포함하는 큰 문제에서도 동일한가 dp에서 중요한것 - 점화식세우기 - memoization: 앞에서 계산한 값을 배열에 저장했다가 필요할 때 재사용 구현방법 top down bottom up

from collections import deque #상하좌우 + 대각선 x = [1,0,-1] y = [1,0,-1] while 1: w, h = map(int, input().split()) if w == 0 and h == 0: break maps = [list(map(int, input().split())) for _ in range(h)] check = [[0 for _ in range(w)] for _ in range(h)] land = 0 for j in range(w): for k in range(h): if maps[k][j] == 1 and check[k][j] == 0: land += 1 q = deque([[k, j]]) check[k][j] = 1 while q: now = q...