꾸준하게 거북이처럼

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n이 100 이하라 완전탐색을 해도(O(n^2)) 괜찮다. 하지만 입력 크기가 커지게 되면 어떻게 풀어야할까 어딘가에 개수를 저장해서, 전체 개수인 n개에서 빼면 다른 트리 개수가 나올 것 같다. dp구나! 생각이 들었고, 프로그래머스에서 풀이를 찾아봤다. 자식에서 부모로 올라가면서 개수를 증가시켜나가는 방식이다. 그러면 O(n) 방식으로 풀 수 있다. function solution(n, wires) { const g = Array(n + 1) .fill() .map((e) => Array()); for (..

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 1. 조건 - 최대 3개까지 가로선 추가, 3개를 넘으면 -1 출력 - 두 가로선이 접하면 안된다. - 모두 i -> i 번 도착해야한다. 2. 구하고자 하는 것 - 모든 1~n번 세로선이 사다리를 타고 i->i 으로 도착할 수 있도록, 추가해야하는 가로선 개수 최솟값. 3. 가로선 선택 부분 풀이 및 설계 완전 탐색으로, 10*30 => 가로선이 접하면 안된다는 조건 하에서, 약 300개 중에서 최대 3개를 고르는 조합이라고 볼 수 있다. 300C3 * 300..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 처음에 완전탐색으로 문제를 풀 수 있을 것 같았지만 15! 만큼 시간 복잡도가 나와서 시간초과가 나왔다. 2. 완전 탐색 풀이를 수정 + dfs 함수 사용해서 시간 복잡도를 줄여야했다. 3가지 곡쾡이가 존재 + 최대 광물은 50개. 1 곡쾡이당 5번 사용가능하므로, 50//5 == 10개를 뽑으면 된다. 그렇다면, 최대 대략 3^10만큼의 경우의 수가 나오므로, 시간 제한에 걸리지 않을 것이라 판단할 수 있다. 코드 answer = int(1e9) def dfs(total,p_count,m_index,m..

15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 처음에 python3로 코드를 제출하고 시간 초과가 나와다가, pypy로 제출하니 통과가 되었다. 그후로 왜 .. 어떻게 하면 python3로 통과할 수 있으려나 찾아보았다. 결론적으로는 if else문을 줄이고, for 중복문 중간에 if조건을 걸어서 통과할 수 있었다. 처음 코드 : pypy 통과 import sys input = sys.stdin.readline n = int(input()) s = [] ch = ..

14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 아이디어는 금방 떠올랐지만.! 시간초과가 나와버렸다. 왜 시간초과가 나왔나 생각해 보았다. 재귀로 조합을 구현했을 때 시간 복잡도: O(2^n) 이 문제에서는 20이 최대 n이고, 2^20 => 100만번 연산 + 재귀가 끝날때 for중복 2번 ( 최대 200번 ) => 2억연산 초과... (1억회당 1초) 내가 for중복과 사실살 필요없는 배열을 사용, 2차원 배열 index가 0부터 시작하는 것을 1로 마추려다,, 등등의 이유로 시간 초과가 났다. 정말 당연한 거지만, 아이디어가 ..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 최근에 순열 또는 조합 문제를 재귀로 푸는 연습을 하다보니, 이 문제에서도 비슷하게 적용했더니 답이 이상하게 나왔다. 그 이유가. 재귀 함수에서 재귀 호출을 for 반복문 내 에서 해서, 마치 순열 처럼 다음 인덱스를 바로 적용하는 것처럼 구현해서 답이 이상했던 것이었따.. ㅠ 상담기간이 1일이 아니기 때문에, 1일날 상담을 한다해도 그 다음날인 2일날에는 상담을 못할 수 있기 때문에, 순열과 다르게 중간 중간 뛰어넘기는 문제인다. 근데, 나는 처음에 순열처럼 풀었던 것이다..하하 평소보다 이른 아침 일찍 풀어서 그런지 미흡했다... 풀이 day: 재귀 함수 dfs 매개변수로, 해당 일을 뜻하는 in..

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 재귀 함수 호출을 통해 C개 중 L개로 순열을 만들고, 자음 2개이상 모음 1개 이상인지 체크해야하는 문제이다. 여기서 나는 재귀 함수를 통해 순열이 길이가 L가 됐을 때, 자음으로만 구성된 경우인지만 검사했다. 그럼 최소 모음이 한 개일 테니까,,, 그럼 모두가 모음인 경우가 출력되버린다.. 입력자체에서 필터를 해주지 않기 때문에 검사가 필수!!!!! 따라서 느낀 것은, 예외를 놓치지 않으려면, 이러한 특정 조건이 문제에 제시되면! 숫자로 정확히 체크하는 것이, 정..

10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 처음에 재귀를 통해 문제를 풀었지만 n의 범위가 10,000까지이기 때문에 런타임에러가 나왔다. n 범위를 항상 확인하고 빠르게 방법을 바꿨어야 했다,, ㅎㅎ 다음으로 오는 순열을 알기 위해서는 아래와 같은 특정 규칙을 알아야 문제를 풀 수 있다. 풀이 1 4 3 2를 예시로 알고리즘을 알아본다. 1. 뒤에서 부터 순열을 비교하며, 뒷 값이 앞 값보다 큰 경우까지 반복한다. (3,2), (4,3)은 해당하지 않고 (1,4)가 해당된다. 이 때, 1의 인덱스는 x, 4의 인덱스는 y라고 한다. 2. 다시 뒤에서부터 값을 비교..

1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이 문제는 브루트포스 - 완전탐색 문제로, 말그대로 모든 경우의 수를 찾는 문제다. 문제를 읽고 두 가지 경우로 크게 나눌 수 있다. 1. +, - 버튼으로만 조작해서 채널 이동 2. 고장난 번호를 피해서 target 채널과 최대한 가까운 채널로 이동한 후, target 채널까지 +, -를 눌러서 이동 일단 만들 수 있는 모든 채널을 구한 후, 그 채널 번호가 tartget 채널과의 차이가 최소인 것을 찾으면 답을 찾으면 된다. import sy..