C

[C/C++]백준 번 - 문제 링크 : https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 접근방식 일반적인 BFS문제. 백준 4179문제와 푸는 방식이 동일하다. 코드 #include using namespace std; #define X first #define Y second string board[1002]; int dist1[1002][1002]; //불 int dist2[1002][1002]; //상근 int dx[4] = {-1,0,1,0}; in..

문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 ..

탐욕 알고리즘(그리디 알고리즘) 탐욕 알고리즘 또는 그리디 알고리즘 이라는 것에 대해서 이야기 해봅시다. 탐욕 알고리즘은 주어진 순간 순간마다 가장 최선의 선택을 하는 알고리즘 설계 기법입니다. 매 순간마다 하는 선택은 최선이지만, 전체로 봤을 때는 최적의 선택이라는 보장을 하지는 않습니다. 그리디 알고리즘이 제대로 동작하지 않은 예시로 주로 드는 것은 마쉬멜로우 실험입니다. 예를 들어서, 지금 당장에 마쉬멜로우 1개를 받을 수 있지만, 10분을 기다린 경우 2개의 마쉬멜로우를 받을 수 있는 실험이 있다고 가정해 봅시다. 그리디 알고리즘으로는 지금 당장 1개를 선택하겠지만, 전체로 본다면 10분을 기다린 후에 2개의 마쉬멜로우를 받는게 가장 많은 마쉬멜로우를 받을 수 있을 것 입니다. 그리디 알고리즘은 ..

문제 링크 : www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 관련 알고리즘 : 그리디 알고리즘(탐욕 알고리즘), 동적 계획법 아이디어) 2가지 방법으로 풀어봤다. 그리디) 처음 설탕을 가져갈 때 5kg짜리로 최대한 많이 담고, 남은 설탕을 3kg으로 가져감. 만약 5kg으로 최대한 담고 3kg으로 나머지를 담는데, 나눠떨어지지 않으면 5kg를 하나 빼고 다시 3kg을 담음. 5kg를 다 뺐지만, 3kg만으로 설탕이 나눠지지 않으면, -1을 출력. 동적 계획법)cach..

문제설명 출처 : www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 평균을 넘는 학생 수 의 비율을 출력하는 문제. 문제풀이 아이디어 그냥 문제의 흐름대로 단순하게 계산. 배열의 길이를 동적으로 할당. 코드 #include #include using namespace std; int main() { int testCase; double average=0; int count = 0; //평균을 넘는 학생 수 cin >> testCase; for (int i = 0; i > N; int..