본문 바로가기

Algorithm

 (55)
[BeakJoon 1480] 보석 모으기 안녕하세요. 이번 포스팅에서는 백준 1480 보석 모으기 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/1480 1480번: 보석 모으기 첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 처음 이 문제를 보았을 때 각 가방의 한도가 같기 때문에 투 포인터 형식으로 접근을 하였는데, 해당 방식이 최적해를 구하지 못합니다. 따라서 이 문제는 Dynamic Programming으로 모든 status에 대한 검사를 해야 합니다. 가방의..
[Programmers] 위클리 챌린지 5주차 - 모음 사전 네 월요일은 위클리 챌린지의 날입니다. 오늘은 5주 차! 모음 사전을 보도록 하겠습니다. https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 위 링크에서 꼭 도전해보시고 오시길 바랍니다! 문제를 보면 A, E, I, O, U만을 사용하여 5자리의 단어까지 순서를 반환하는 문제입니다. 이 문제를 공식을 찾아서 풀 수도 있습니다. word가 1자리라면, 5이내로 풀 수 있..
[Programmers] 위클리 챌린지 4 직업군 추천하기 안녕하세요. 이번 포스팅에서는 프로그래머스 위클리 챌린지 4 직업군 추천하기 문제를 풀어보겠습니다. https://programmers.co.kr/learn/courses/30/lessons/84325 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 위 링크에서 한번 도전해보시고 오시면 좋을 것 같습니다. 일단 이 문제는 문자열 + 구현 문제입니다. 큰 고민 없이 문제의 요구사항을 코드로 적어주시면 됩니다. 저의 경우는 우선 처음 table을 각각 SI, A, B, C, D, E ... ... GAME, A,..
[BeakJoon 2042] 구간 합 구하기 안녕하세요. 이번 포스팅에서는 BeakJoon 2042 구간 합 구하기 문제를 풀어보도록 하겠습니다. 문제는 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 우선 이 문제는 구간 합 구하기 문제이긴 한데, 동적으로 계속 배열 값이 변경되기 때문에 이를 일일이 변경할 수가 없습니다. https://chanho0912.tistory.com/29?categ..
[BeakJoon 17623] 괄호 안녕하세요. 이번 포스팅에서는 백준 17623 괄호 문제를 풀어보도록 하겠습니다. 문제는 https://www.acmicpc.net/problem/17623 17623번: 괄호 6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 이 문제를 dynamic programming으로 접근해서 해결하였는데, dmap값을 기준으로 dp[n] -> val(x)=n인 x 중 최솟값으로 갱신하였습니다. 조금 더 풀어서 점화식으로 설명하자면, dp[1] = "()" dp[2] = "{}" dp[3] =..
[Programmers] 위클리 챌린지 3주차 - 퍼즐 조각 채우기 안녕하세요. 이번 포스팅에서는 프로그래머스 위클리 챌린지 3주 차 퍼즐 조각 채우기 문제를 풀어보도록 하겠습니다. https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 해당 문제는 위 링크에서 도..
[BeakJoon 2618] 경찰차 안녕하세요. 이번 포스팅에서는 백준 2618번 경찰차 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 우선 이 문제는 굉장히 어려운 문제입니다. 그 이유는 문제의 제한입니다. 보통 이런 문제는 int go(int orderIdx, int firstCar, int secondCar) { if(orderIdx == w) return 0; int& ..
[BeakJoon 16235] 나무 재테크 안녕하세요. 이번 포스팅에서는 백준 16235번 나무 재테크 문제를 풀어보겠습니다. https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 해당 문제는 위 링크에서 확인하실 수 있습니다. 우선 이 문제를 풀기 위해 별도의 알고리즘을 많이 고민하실 필요는 없습니다. 해당 문제를 시뮬레이션으로 구현하시면 되는데, 문제는 이 문제의 제한이 빡빡합니다. 시간제한이 0.3초라서, 매번 sort를 하기 어렵습니다. sort를 하는 이유는 어린 나..

티스토리툴바