'코드업' 태그의 글 목록

[백준] 2485번 키 순서 (C)

출처 한국정보올림피아드 지역본선 2011 초등부 4번 문제 번호 백준 2458번 키 순서 코드업 4714 : 키 순서 알고리즘 DFS 힌트 나보다 큰 아이보다 작은 아이와의 관계는 알 수 없음 나보다 큰 아이보다 큰 아이는 나보다 큼 나보다 작은 아이보다 작은 아이는 나보다 작음 나보다 작은 아이보다 큰 아이와의 관계는 알 수 없음 풀이 들어오는 입력들을 그래프에 저장해 줄 때 1과 2로 구분하여 저장해줌으로써 누가 더 큰 아이인지 구분이 가능하게 해준다. 나보다 큰 아이들과 나보다 작은 아이들의 합이 전체 아이의 수 - 1 (n-1) 이라면 모든 나의 등 수를 알고있다고 할 수 있다. 따라서 dfs함수를 구현 할 때 몇 번째 아이에 대해 탐색할건지 n와 어느 방향에 대해(큰 아이들, 작은 아이들) 탐색..

Problem Solve/DFS & BFS 2020. 3. 20. 01:07

[백준] 7596번 토마토 (C)

출처 한국정보올림피아드 지역본선 2013 초등부 3번 문제 번호 백준 7569 토마토 코드업 :4773 토마토 (초등) 알고리즘 3차원 BFS 힌트 배열에 토마토가 익는 날짜를 저장 문제 풀이 이 문제 풀이의 핵심은 배열에 토마토가 익는 날짜를 저장한다는 것이다. 익은 토마토의 입력이 1로 들어오기 때문에 day배열에 저장될 숫자는 그 위치의 토마토가 익는 날 +1이 된다. 토마토의 위치를 나타낼 dot 구조체를 만들어주고 dot을 넣을 큐q를 만들어 준다. 3차원이기 때문에 방향 배열의 크기는 6*3이 된다. BFS이기 때문에 가장 먼저 갱신된 값이 날짜의 최소값이다. 따라서 check배열을 만들어 주지 않고 day배열을 check배열처럼 사용할 수 있다. BFS가 끝나고 day배열에 들어있는 최대값을..

Problem Solve/DFS & BFS 2020. 3. 16. 18:17

[백준] 2468번 안전영역 (C)

출처 한국정보올림피아드 KOI 2010 초등부 2번 문제 번호 백준 : 4697 안전 영역 코드업 : 2468번 안전 영역 알고리즘 DFS, Flood Fill 풀이 수면의 높이를 0부터 100까지 올려가면서 구역의 개수를 세어준다.(cnt) 각 수면의 높이마다 ans를 최대 값으로 갱신해준다. 매 높이 마다 구역을 새로 세어야 하기 때문에 check배열을 매번 초기화 해주어야 한다. #include using namespace std; int in[100][100]; int check[100][100]; int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; int n; void fill(int a, int b){ check[a][b]=1; for(int i=0;i=n||nb>=n..

Problem Solve/DFS & BFS 2020. 3. 15. 23:52

[코드업] 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

[백준] 2667번 단지 번호 붙이기 (C)

출처 : KOI 1996 초등부 1번 알고리즘 : Flood Fill 풀이 Flood Fill 알고리즘을 그 이상 그 이하도 아니다. 알고리즘만 알면 간단히 풀 수 있다. 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 #include #include #include using namespace std; vector ans; int in[27][27]; int check[26][26]; int dir[4][2]={{0,1}, {0,-1}, {1,0}, {-1,0}}; int fill(int a, int b){ int c..

Problem Solve/DFS & BFS 2020. 3. 10. 15:13

[코드업] 3212 : 위상 정렬(topological sort) (C)

알고리즘 위상정렬 풀이 위상정렬을 하 되, 우선순위가 같은 경우 작은 숫자부터 출력해야 하기 때문에 한번의 시행이 끝날 때 마다 다음 시행할 '한 개'의 숫자를 Queue에 넣어준다. ( 이런 우선순위 조건이 없을 경우엔 간선이 지워지는 노드들만 확인 하면 된다. ) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include#include#include#includeusing namespace std; queue q;queue ans;vector vec[201]; int ind[201]; int main(){ int v,n; cin>..

Problem Solve/DFS & BFS 2020. 3. 9. 23:14

[코드업] 2610 : 그림판 채우기 (C)

알고리즘 Flood Fill 풀이 주어지는 X, Y 좌표가 Zero base이기 때문에 Zero base로 짜는 것이 편하다. '_' (빈칸) 과 '*'(채워진 칸)을 0, 1으로 대응시키면 조건 처리를 할 때 더욱 편리하게 할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#includeusing namespace std; int in[10][10];int dir[4][2]={{1,0}, {0,1}, {-1,0}, {0,-1}}; void print(){ for(int i=0;i

Problem Solve/DFS & BFS 2020. 3. 9. 18:44

[코드업] 2605 : 캔디팡 (C)

알고리즘 Flood Fill 풀이 문제 그대로 같은 색으로 이어진 칸들의 갯수를 세면 된다. 배열 범위를 벗어나는지 좀 더 편리하게 체크하기위해서 배열의 크기를 9*9로 잡아 주었다. 입력값에 0이 없기 때문에 in[i][j]가 0이라면 배열의 범위를 벗어난 것으로 확인할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142#includeusing namespace std; int in[9][9];int check[8][8]; // 한번 방문했던 곳 체크 int dir[4][2]={{1,0}, {0,1}, {-1,0}, {0,-1}}; // 방향배열 int ans; int search(int a,int b){ /..

Problem Solve/DFS & BFS 2020. 3. 9. 09:23

[백준] 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

낭만 IT

코드업 → (15)건