'온라인저지' 태그의 글 목록

[코드업] 3500 : 지뢰 찾기 2 (C)

알고리즘 : DFS, Flood Fill 풀이 단순한 탐색 알고리즘 문제지만 다른 문제들과 다른점은 4방향이 아닌 8방향을 탐색해야 한다는 것이다. 방향배열을 8*2로 잡아주고 탐색을 해주면 된다. 문제를 풀기에 앞서 이해를 해보면 다음과 같다. 특정 칸의 숫자는 그 칸 주위의 8개의 칸 중에 지뢰의 개수를 나타낸다. 클릭한 칸에서 시작하여 (1)의 숫자가 0이 아닐때 까지 탐색한다. (이때 탐색도 8방향이다) 탐 탐색한 칸은 (1)의 숫자, 탐색하지 않은 칸은 _로 출력한다. 내가 선택한 칸이 지뢰일 경우 그 칸을 -1 나머지는 _를 출력한다. in배열은 입력 데이터 이고 map배열은 지뢰의 갯수를 세어 놓는 배열이다. ( 탐색이 끝나는 지점이 될 것이다. ) 처음에 in 배열을 모두 돌아 map 배열..

Problem Solve/DFS & BFS 2020. 3. 13. 01:50

[백준] 2457번 공주님의 정원 (C)

출처 2011 지역본선 초등2 문제 주소 백준 2457번 공주님의 정원 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1a>>b>>c>>d; in[i].start=a*100+b; in[i].end=c*100+d; } sort(in,in+n,cmp); int now=301,ans=0,index,max=0; for(int i=0;i1130) break; // 오늘(now)을 포함하는 꽃들 중 가장 오래 심을 수 있는 꽃을 찾는다. if(max

Problem Solve/Greedy 2020. 3. 8. 09:44

[백준] 8980번 택배 (C)

출처 2013 전국 본선 초등2 알고리즘 그리디 힌트 상자를 싣고 갈 구간을 보자. 문제 풀이 그리디 알고리즘으로 간단하게 풀리는 문제지만 뭐에 대해서 그리디를 적용시킬지 찾는게 쉽지 않다. 결론 부터 말하자면 상자가 트럭에 실려 있는 구간이 짧은 순으로 확인하면 된다. 구간이 같다면 먼저 실을 수 있는 상자를 선택한다. 따라서 상자를 목적지, 출발지 순으로 오름차순 정렬하면 된다. 그 뒤 반복문으로 앞에서 부터 살피면 되는데 이번에 선택된 상자(now)가 트럭에 실려있어야 할 구간을 살피고 모두 실을 수 있다면 now의 cost를, 용량이 초과된다면 남은 용량 만큼을 그 구간에 더해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

Problem Solve/Greedy 2020. 3. 7. 22:37

[코드업] 4040 : 펜션 (C)

알고리즘 그리디 힌트 손님이 펜션에서 가장 오랫동안 머물 수 있는 방을 찾아준다. 풀이 아이디어는 간단하다. 손님이 오늘부터 가장 오랫동안 머물 수 있는 방을 찾아주면 된다. 여기서 잔재주를 부려보면 펜션의 상태를 char형으로 그대로 저장 말고 0,1로 바꾸어 저장해준다. (O : 1, X : 0) 이러면 비교 연산자를 사용하지 않고 조건문 처리가 가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include using namespace std; int in..

Problem Solve/Greedy 2020. 3. 7. 15:16

[코드업] 3321 : 최고의 피자 (C)

알고리즘 그리디 힌트 가장 칼로리가 높은 토핑만 생각한다. 풀이 도우는 무조건 포함해야 하므로 cost(가격)와 cal(칼로리)를 도우의 가격과 칼로리로 초기화해준다. 토핑의 가격들이 입력되면 내림차순으로 정렬해준다. (토핑은 한 번만 사용할 수 있으므로 남아 있는 토핑 중 가장 칼로리가 높은 토핑만 고려하면 된다.) 현재의 칼로리/달러가 i번째 토핑을 추가했을 때의 칼로리/달러보다 클 경우 cal과 cost를 갱신해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int cmp(int a, int b)..

Problem Solve/Greedy 2020. 3. 7. 01:44

[코드업] 3301 : 거스름돈 (C)

알고리즘 그리디 힌트 가장 비싼 화폐부터 거슬러 준다. 풀이 이 문제는 대표적인 그리디 문제다. 거슬러 줄 수 있는 가장 비싼 화폐부터 거슬러 주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int main(){ int money[8]={10,50,100,500,1000,5000,10000,50000}; int n,cnt=0; cin>>n; for(int i=7;i>=0;i--){ cnt+=n/money[i]; n%=money[i]; } cout

Problem Solve/Greedy 2020. 3. 6. 21:43

[코드업] 3120 : 리모컨 (C)

알고리즘 그리디, 백트래킹 힌트 매 시행마다 목표 채널과 현재 채널중 큰 것을 골라 빼거나 작은 것을 골라 더한다. 풀이 a와 b의 대소 관계가 고정되어 있지 않기 때문에 임의로 a>b로 잡아 주었다. 변경할 수 있는 수가 1, -1, 5, -5, 10, -10 인 것에 주목하자. (절대값이 같은 두 수가 3쌍이다.) a에 10을 뺀 것은 b에 10을 더한 것으로 치환할 수 있다. ( 현재 온도를 x도 높인 것은 목표 온도를 x도 낮춘것 과 같고, 현재 온도를 x도 낮춘 것은 목표 온도를 x도 높인 것 과 같다. ) 따라서 두 수 중 큰 수만 값을 줄여주면 되기 때문에 임의로 a와 b의 대소관계를 정해주는 것은 일반성을 잃지 않는다. 시행 횟수에 영향을 미치지 않는다. d 배열에 양수 값만 필요하고 a,..

Problem Solve/Greedy 2020. 3. 6. 15:35

낭만 IT

온라인저지 → (7)건