개발/알고리즘11 [백준 11279][Python] 최대힙 자료구조 직접 구현하기, 시간초과 나는 이유 입력 받을 때 input() 을 사용하면 시간초과가 날 수 있습니다. 저는 7%정도에서 시간초과 오류가 났는데, sys.stdin.readline()으로 바꾸니 한번에 통과했습니다. 힙에 추가하는 부분보다는 삭제하는 부분이 어려운데, 자식 노드가 존재하는지 검사하지 않으면 list out of range 에러가 날 수 있기 때문에 size 변수를 잘 이용해서 현재 노드의 개수를 잘 파악해야 합니다. 힙은 완전이진트리이기 때문에 노드 개수만으로도 트리 모양을 예측할 수 있습니다. 파이썬을 오랜만에 썼는데 까먹은 부분이 많아서 놀랐고 앞으로도 종종 써야겠다고 생각했습니다 import sys class Heap: def __init__(self, max_size): self.size = 0 self.data .. 2021. 5. 29. [2021 카카오 신입 공채][Javascript] 메뉴 리뉴얼 완전 제 멋대로 풀어봤습니다. 문제에 워낙 조건과 요구사항이 많지만... 제 생각에 문제 풀이에 중요한 조건은 다음과 같습니다. 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함 즉, 간단하게 말하면 'AB'처럼 문자열 길이가 2 이상이고, 'AB'가 주문된 횟수가 2 이상일 때만 포함시키면 되겠습니다. 코스 요리 조합이 나올 수 있는 경우의 수를 combination을 통해서 다 찾았습니다. 그리고 Map에 key로 메뉴의 조합을, value로 주문 횟수를 넣어 저장합니다. 이차원 배열 courseArr을 만들어 courseArr[n][0]에는 메뉴 조합을, courseArr[n][1]에는 주문 횟수를 저장합니다.. 2021. 4. 25. [프로그래머스][Javascript] 타겟 넘버 이 문제는 조건 서술을 매우 빈약하게 해 놓아서 푸는데 어려움이 있었다. 문제에서 제대로 설명이 안 된 조건은 바로 배열에 주어진 순서대로 연산이 이루어진다는 점이다. 예시 케이스도 [1, 1, 1, 1, 1] 뿐이라 이 조건이 전혀 설명이 되지 않는다. 풀이는 재귀를 이용했다. 지금까지 더해진 수를 sum 변수에 저장하고, 이번에 연산할 수가 sum에 더해진 것을 added, 뺀 것을 subbed에 저장했다. index을 1씩 늘려가며 recur 함수를 반복한다. index가 배열 끝에 달했을 때, added나 subbed가 원하는 target과 동일할 경우가 정답 케이스이다. 프로그래머스에는 이렇게 조건 설명이 허술한 문제들이 좀 있는 것 같다. 주의해야 할 듯.. 1 2 3 4 5 6 7 8 9 1.. 2021. 4. 25. [프로그래머스][Javascript] 체육복 첫 번째 for문으로 문제에서 주어진 조건대로 체육복의 개수를 저장한다. reserve와 lost에 모두 들어있는 경우도 생각해야 한다. 두 번째 for문으로 최대한 많은 사람이 체육복을 입을 수 있도록 처리한다. 체육복이 2개이고 앞사람이 체육복이 없는 경우만 체육복을 전달한다. 그 후 뒷사람도 동일한 코드를 반복한다. 문제 조건 상 인접한 앞, 뒷사람에게만 체육복을 나눠줄 수 있다. 이 조건이 바로 이 문제를 greedy하게 풀어도 되는 조건이다. 체육복이 0이 아닌 사람의 수를 계산하면 끝~ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 function solution(n, los.. 2021. 4. 25. [백준1021][Java] 회전하는 큐 오랜만에 자바 1. 왜 변수가 오는 자리에 상수를? 21번 줄의 list.size() 대신 N을 사용했다가 왜 안되지? 이러고 있었다. 리스트 앞/뒤로 추가 삭제가 일어나기 때문에 N을 사용해선 안된다. 2. 왜 입력 다 받고 코딩 줄줄줄 하려 하는가? 습관처럼 앞에서 입력을 다 받아야 한다고 생각하지 말자. 유연하게 풀기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 package ps; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(.. 2020. 4. 29. [C++][백준 2178] 미로탐색 - 가중치가 없는 그래프의 최단경로? 가중치가 없는 그래프의 최단경로 탐색은 BFS 로 가능하다 ! 단, 경로는 유일하지 않을 수도 있다. 왜 DFS는 안될까? 방법 1) 스택을 이용해 푼다고 가정했을 때, 스택에 넣었을 때 visited를 true로 초기화한다고 생각해보자. 다음 예제에서 110110 110110 111111 111101 위와 같은 경로로 첫 탐색이 이루어 지고, 15개의 노드를 거치게 된다. 문제는 이 경로상의 노드들은 모두 방문 한 것으로 간주되기 때문에, 실제 최단 경로상에 이 노드들이 포함되는 경우, 정답을 찾지 못하게 된다. (하지만 운이 좋다면 특정 케이스의 경우 한번에 정답을 찾을수도 있다.) 방법 2) 가능한 모든 경로를 DFS로 구하고 최소값을 출력하면 안돼? -> 경우의 수가 너무 많아진다. 지수 시간 복.. 2020. 3. 13. 이전 1 2 다음