본문 바로가기

programmers

[programmers] 땅따먹기 로직 - 계속 더해가면서 최대값을 찾는다. 이때, 바로 아래에 있는 값은 사용하지 못한다. - 위 -> 아래 가려면 아래 값을 "val = 아래값" 으로 지정해두고나서 더하면서 max값을 찾아야한다. - 아래 -> 위 가면 그냥 최대값을 찾으면 됨. 이때, 바로 위의 값을 제외한 리스트의 max값을 찾는다. 코드 주의할 점 1. DP사용하기! 더보기
[programmers] 가장 긴 팰린드롬 로직 [방법1] 1. 팰린드롬 확인하는 함수 만들기 : 결과값은 문자열 갯수 2. i는 문자열 처음부터, j는 문자열 끝에서부터 진행해서 최대값 구하기 -> 끝에서부터 진행하려면 팰린드롬 결과가 True이면 cnt = 팰린드롬 문자열갯수 [방법2] 1. 팰린드롬 확인하는 함수 만들기 : 결과값은 [True, 문자열 갯수] or [False, 0] 2. i는 문자열 처음부터, j는 문자열 끝에서부터 진행해서 최대값 구하기 -> 끝에서부터 진행하려면 팰린드롬 결과가 True이면 cnt = 팰린드롬 문자열갯수 => 큰 값부터 나올거기때문에 더 적게 계산 코드 [방법1] [방법2] 결과 [방법1] [방법2] 확실히 2번 방법이 빠르다!! 더보기
[programmers] 정수 삼각형 로직 1. 가쪽에서 더해지는 값은 계속 더해진다. 2. 왼쪽, 오른쪽에서 더해질 수 있는 값 중 최대값을 더해준다. 코드 더보기
[programmers] 더 맵게 로직 1. 우선순위큐를 이용해서 가장 작은 값, 두번째로 작은 값을 뺀 후, heappush를 이용해서 넣으면 값의 크기를 기준으로 들어간다. 2. 이때, 값을 두개를 빼야하기 때문에 scoville 리스트에 값이 두개 이상 들어가있어야 first, second로 뺄 수 있고, heapq구조이므로 첫번째 값이랑 K랑 비교해서 크면 뒤에 값들은 다 큰것이다. heapq구조이므로, 마지막으로 값이 하나 남아 있을 때, K보다 작으면 -1을 리턴한다. 코드 주의할 점 1. heapq 이해가 필요하다. heappop, heappush를 사용하기 위해서는 우선 리스트가 heapify로 정렬되어있어야한다. 더보기
[programmers] N으로 표현 로직 1. 계산된 값들을 저장하면서 그 값들을 가지고와서 계산한다. -> DP사용 1번 사용 : 5 2번 사용 : 55, 5+5=10, 5-5=0, 5*5=25, 5/5=1 3번 사용 : 555, 5+5+5=15, 5+5-5=5, 5+5*5=30, 5+5/5=6, 5-5+5=5, 5-5-5=-5, 5-5*5=-20, 5-5/5=4, 5*5+5=30, 5*5-5=20, 5*5*5=125, 5*5/5=5, 5/5+5=6, 5/5-5=-4, 5/5*5=5, 5/5/5=0, 555 + 1번사용->2번사용, 2번사용->1번 사용(중복은 제거) 4번 사용 : 555 + 1번사용->3번사용, 2번사용->2번 사용, 3번사용->1번 사용(중복은 제거) 코드 주의할 점 1. num_ls에 넣을 때, x-y, y-x를 동.. 더보기
[programmers] 가사 검색 로직 1. 만약 'fro??' 을 찾는다고 하자 (1) 길이가 5 인 곳으로 들어간다 (2) 거기서 f 로 들어간다. cnt에는 f로 시작하는 단어가 4개있다는 것을 저장한다. (3) r 로 들어간다. cnt에는 r로 시작하는 단어가 4개 있다는 것을 저장한다. (4) o 로 들어간다. cnt에는 o로 시작하는 단어가 3개 있다는 것을 저장한다. (5) ? 를 만나면 cnt 를 리턴. (6) fro 로 시작하면서 길이가 5인 단어는 마지막에 저장된 3개이다. 2. ** 문제점 : 이렇게 하면 효율성 3번에서 틀린다! why? 쿼리가 모두 ?로 구성된 경우 있음 ** 해결책 : 단어의 길이가 최대 1만까지이므로 1만까지의 배열을 만들고, 각 단어의 길이마다 몇개인지 저장 쿼리가 모두 ?로 구성 -> 찾지말.. 더보기
[programmers] 경주로 건설 로직 1. board를 돌면서 direction, cost를 함께 가지고 이동한다. 2. (0, 0)에서 밑으로 가는 것과 오른쪽으로 가는 것 두개를 각각 bfs를 사용해 가격을 확인한다. 3. x = y = len(board) - 1 이 되면 answer에 넣고, answer중에 최소값을 구한다. answer에 들어가는 값은 (0, 0, down)과 (0, 0, right)에서 각자 bfs를 돈 결과이다. 4. near에 (dx, dy, direction)을 넣은 다음에 (x, y)에서 near을 돌면서 xi, yi, new_cost를 구한다. 다음칸이 0이면서 visit[xi][yi]이 0이거나(아직 지나가지 않음) 기존의 값보다 작은 경우 새 가격으로 갱신해준다. 코드 주의할 점 1. bfs를 돌때.. 더보기
[programmers] 자물쇠와 열쇠 로직 1. (key-1)*2+lock길이만큼의 board를 만든다. 2. key를 한칸씩 이동하면서 넣고, lock도 넣는다. 이때, board[i][j] != 1이면 멈춘다. 3. key 이동이 (0,0)부터 끝까지 갔으면, key를 90도 돌린다(함수만들기) 4. 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 코드 주의할 점 - for문을 돌릴 때 범위 설정이 중요!! (4중 for문을 돌지만, N, M 숫자가 작아서 괜찮다.) 더보기

티스토리툴바