순간을 성실히, 화려함보단 꾸준함을

[문제] : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net [분류] : 다이나믹 프로그래밍(DP) [구현 방법] : 유명하고(well known) dp문제를 두고 보면 빠지지 않고 나오는 문제 입니다. 흔히 "냅섹(knapsack)"문제라고 불립니다. 물건 하나씩 더해가면서 현재 가방의 무게가 w 일때 최대로 담을 수 있는 가..

[문제]:https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. www.acmicpc.net #2021/02/05 코드와 로직 수정 [분류] : 탐색(DFS) [조건]: 0으로 채워진 칸을 1로 바꾸었을때 연속적으로 존재하는 1의 개수가 가장 최대임을 찾으면 됩니다. [과정] : 1)먼저 연속적으로 붙..

[문제] : https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림 www.acmicpc.net [분류] : 구현 [조건] : 6개가 연속으로 존재하면 안된다.그 외에는 특별히 주의할게 없어 보입니다. [구현과정]: 너무 화..

[문제] : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [분류] : 다이나믹 프로그래밍(DP),브루트 포스(Brute force) 조건 : 각 상담일 마다 걸리는 기간이 정해져 있으며 남은 날짜(n) 을 넘어가서는 안된다. 금액이 최대가 되어야 한다. 과정: 처음 0번 index 부터 남은 날짜(n)을 초과 하지 않는 범위 내에서 dfs를 통해 금액의 합(ans)를 구한다. 구현 방법: 유명하고(well known) 기초적인 브루트 포스 문제입니다. 이차원 배열을 사용해 dfs를 이용하였습니다. 일일이 구해보자라는 생각이 들고 재귀 탐색을 이용하여 모든 경우의 수를 구하면 해..

[문제] : https://www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 문제 페그 솔리테어는 구멍이 뚤려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다. 핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다. 현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프 www.acmicpc.net [분류]:백트래킹,브루트 포스 조건 : 수평,수직 방향으로 인접한 핀이 존재해야 하며,인접한 핀의 다음 칸은 비어 있어..