전체 글 (64) 썸네일형 리스트형 백준 14501번 퇴사 C/C++ 풀이 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 동적계획법으로 풀었다. 배낭 알고리즘을 응용해서 풀었다. #include #include using namespace std; FILE* in = fopen("input.txt", "r"); #define MAX 15 int n; int time[MAX]; int pay[MAX]; int cache[MAX+1][MAX * 1000]; int dp(int idx, int cost) { //메모이제이션 if (cache[idx][cost] != 0) return cache[idx][cost]; if (idx == n) return cos.. 백준 13460번 구슬 탈출 2 C/C++ 풀이 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 시뮬레이션 문제를 가볍게 봤다가 큰 코 다친 문제. 시뮬레이션 문제에서는 1) 문제 이해, 2)디버깅 을 얼마나 빨리 하는가가 문제 풀이의 속도를 결정 짓는 것 같다. 내가 접근한 방식은 재귀함수로 푸는 방식이어서 map을 초기화해주는 대신에 바로 전 단계로 돌려주는 것을 구현을 했어야했는데, 이 과정에서 실수가 많았다. #include #incl.. 백준 14888번 연산자 끼워넣기 C/C++ 풀이 https://www.acmicpc.net/problem/14888 이 역시 Brute force 문제. 재귀함수를 이용해서 문제를 풀었다. 어떻게든 재귀함수를 이용해서 완전탐색을 풀려고 끙끙 앓다보니 재귀함수 구현하는 능력이 레벨업 된 것 같다..ㅎㅎㅎ,,,, 아래는 재귀함수를 이용한 풀이 #include FILE* in = fopen("input.txt", "r"); #define MAX 11 int n; int input_array[MAX]; int sign[4]; int checked[4]; int max = -1000000000; int min = 1000000000; // 부호 숫자에 따른 계산값 출력해주는 함수 int calc(int type, int ret, int idx) { int an.. [SW Expert Academy] 2115. 벌꿀 채취 C/C++ 풀이 이 문제에 꼬박 하루를 썼다면 당신 믿으시겠습니까? 애매하게 아는 것은 확실하게 아는 것보다 위험하다는 격언을 생각나게 해주는 문제였습니다... :) 문제는 모든 가능성을 이용하는 Brute Force인데, 상자 안의 최대 수익을 구하기 위해 DP(동적 계획법)의 테크닉이 필요하다. 동적 계획법은 예전에 포스팅 했으니 참고하세요. (여기로) 동적계획법(1) 동적계획법이란? 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 분할 정복의 알고리즘과 비슷하지만 동적계획법의 chavo-s-it-life.tistory.com M개의 영역 안에서 수익의 최댓값을 구하는 것은 반복적으로 사용되기 때문에 cache 배열에 저장해두면 연산을 빠르게.. 백준 15686번 치킨 배달 C/C++ 풀이 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net Brute Force 문제이다. Brute Force란? 가능한 모든 조합를 구해서 답을 구하는 기법이다. 주어진 치킨집의 개수 중 m개에 해당하는 치킨집 조합을 모두 구한 후 그에 따른 거리 합의 최솟값을 구해주면 된다. 시간복잡도를 계산하기 위해 가장 worst case를 계산해보면 13개의 치킨집 중 6개를 선택하고 13!/7!6! 그 모든 조합에 집들(최대 100개)마.. 백준 14500번 테트로미노 C/C++ 풀이 https://www.acmicpc.net/problem/14500 전형적인 DFS(깊이 우선 탐색, Depth-First Search) 문제이다. DFS는 BFS(너비 우선 탐색, Breadth-First Search)와 구분되는데, 우선 각각의 개념을 알아보자 DFS란? 하나의 정점을 기준으로 그 지점에서 갈 수 있는 점들을 기준으로 탐색하는 방법이다. 글로 길게 적는 것보다 이에 대해 잘 설명하는 그림이 있어 들고 왔다. 출처는 https://twpower.github.io/151-bfs-dfs-basic-problem이다. BFS란? 하나의 정점을 기준으로 그와 가까운 점들부터 탐색하는 것을 의미한다. 문제에 제시된 테트로미노의 모양을 보면 깊이 탐색을 통해서 구현이 가능하다. 하지만 단 하나 ㅜ.. [SW Expert Academy] 2117. 홈 방범 서비스 C/C++ 풀이 .https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu 시뮬레이션 문제. 문제만 처음 봤을 때는 전체 다 순회하려면 시간이 오래 걸릴 것이라고 생각했다. 근데 전체 MAP 크기가 20*20 밖에 안되고 각 포인트에서 다른 포인트까지의 거리(20*20)와 거리마다의 집 수를 기록해놓고 최대 집 개수와 비교했다. 결국 마름모 모양이라는 것은 시작점을 기준으로 (K=2)라면 거리 차이가 1 이하인 점들, (K=4)라면 거리 차이가 3 이하인 점들을 모아놓은 것이라서 한 점을 기준으로 거리마다의 집 수를 구하고 그를 이용해서 수익을 계산해주었다. O(N^5)의 풀이가 나왔지만 최대 N이 20이라서 .. 어떻게 운동을 시작해야하는가? 아침에 할 일 끝내고 점심 약속 가기 전까지 시간이 떠서 글을 쓰고 있습니다. '어떻게 운동을 시작해야하는가?' '어떻게 운동을 해야하는가?' 친구들에게 많이 들었던 질문들인데요. 만족할만한 답을 찾을만한 곳이 많이 없는 것 같아 이번 기회에 글로 정리하려 합니다. 사실 운동이라고 하면 범주가 너무 넓습니다. 헬스(웨이트 트레이닝)를 제외하고 수영, 스피닝, 필라테스, 클라이밍 등 재밌는 운동들이 너무 많기 때문에 꼭 헬스장에서 운동을 할 필요가 없긴 합니다. 하지만 운동의 목적이 '근육을 키우고 싶다', '접근성이 높은 헬스장에서 운동하고 싶다'라면 제 경험에 비추어봤을 때 아래의 답변을 드리고 싶습니다. 1. 어떻게 운동을 시작해야하는가? (돈이 있다) => PT를 받으세요. (돈이 없다) ==> 운.. 이전 1 ··· 4 5 6 7 8 다음
