코딩테스트/C++ 문제풀이

[백준] Tractor

https://www.acmicpc.net/problem/5846 5846번: Tractor One of Farmer John's fields is particularly hilly, and he wants to purchase a new tractor to drive around on it. The field is described by an N x N grid of non-negative integer elevations (1 N; for (int i=0; i grids[i][j]; } } } int abs(int k){ return (k>=0)? k : -k; } void fill(int r, int c, int mid){ // bfs로 채우자 queue q; q.push((rc){r,c}); vi..

[백준] 색종이 - 2

https://www.acmicpc.net/problem/2567 2567번: 색종이 - 2 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 설명해보면, 100x100의 하얀 도화지 위에 검정 종이들을 붙입니다. 이 때, 검은 영역의 둘레 길이를 출력해야 합니다. 저의 구현의 경우 하얀 부분을 쭉 채워나가면서, 검정 경계선을 만났을 때 카운팅을 하는 방식을 사용하였습니다. 흔히 flood fill 이라 불리는 풀이방식을 사용하였습니다. 내부의 둘레도 둘레에 포함시켜야 하므로 for loop로..

[정올] 미로탈출 로봇중간 단계

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=521&sca=99&page=3 JUNGOL www.jungol.co.kr 구현문제 입니다. 우선 문제부터 간단하게 요약하면, 로봇의 규칙과 미로가 주어질 때, 해당하는 규칙으로 로봇이 최대로 이동할 수 있는 거리를 출력하면 됩니다. 구현 문제이므로 문제의 조건에 알맞게 구현을 하면 됩니다. 한번 지나간 길을 다시 지나갈 수 없다 등의 조건이 있으니, 중간중간에 확인을 올바르게 해주어야 함을 주의해서 코드를 구성하면 됩니다. 실제 구현은 아래와 같습니다. #include using namespace std; #define MAXN (10) int N; char map[MAXN + 10][MAXN + 10];..

[정올] 회의실 배정

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=645&sca=50&sfl=wr_hit&stx=1370&sop=and JUNGOL www.jungol.co.kr 기본적인 그리디 문제입니다. 문제부터 요약하면, 회의를 최대한 안겹치게 개최할 때, 회의 갯수와 어떤 회의들이 개최 되었는지를 출력해야 합니다. 회의 종료시간을 기준으로 sorting하여 greedy를 이용하여 구현하면 됩니다. 실제 구현은 아래와 같습니다. #include #include using namespace std; int N; struct meeting{ int id, start, end; }meetings[500]; int ids[500]; void getinput(){ cin >>..

[정올] 도서관

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1508&sca=3020 JUNGOL www.jungol.co.kr 그리디로 해결할 수 있습니다. 우선 문제부터 간단하게 요약하면, 도서관에 학생들이 오는 시간과 가는시간이 주어집니다. 이 때, 한 명 이상의 학생이 머물렀던 가장 긴 시간과, 학생이 한 명도 머물지 않았던 가장 긴 시간을 공백으로 구분하여 출력해야 합니다. 그리디를 사용하기 위해서 시작시간을 기준으로 정렬합니다. 그리고 나서 순서대로 보면서 이전 학생과 비교해봅니다. 만약 이전 학생이 떠나는 시간보다 다음 학생의 도착 시간이 빠르다면, 구간이 이어집니다. 구간의 끝값을 다시 계산해 주어야 하는데, 시작시간이 느려도 이전 학생이 더 늦..

[정올] 냉장고

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=3050 JUNGOL www.jungol.co.kr 그리디 알고리즘을 사용하는 문제입니다. 문제부터 간단하게 요약하면, 화학 물질들은 각각 보관 온도 범위를 가집니다. 이 때, 냉장고들은 각각 하나의 온도만을 유지할 수 있습니다. 이 때, 화학 물질들을 모두 보관하기 위한 냉장고의 최소 갯수를 구해야 합니다. 그리디 알고리즘을 사용해야 합니다. 그리디 알고리즘도 정렬을 해야 합니다. y 즉 화학물질 보관의 최대 온도 기준으로 정렬을 시킵니다. 그리고 간단한 예시를 봅시다. 4 -15 5 -10 36 10 73 27 44 정렬을 시키면 위와 같은 상황이 됩니다. 왜 뒤의 온도로 정렬하면 그리디..

[백준] 크게 만들기

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net stack을 이용하는 문제입니다. 문제부터 간단하게 요약하면, N자리 숫자가 주어지는데, 이 숫자중에서 K개를 지워서 만들 수 있는 가장 큰 수를 출력해야 하는 문제입니다. 간단하게 예시를 통해 알고리즘을 생각해보면, 1924를 보면 stack에 하나씩 넣는데, 1보다 큰 9가 들어오면, 1을 pop시키는 형태로 구현을 하면 된다는 생각이 듭니다. 조금 더 디테일 하게는 더 큰 숫자를 집어넣기 전에 stack을 pop하는데, pop은 그 숫자보다 작은 애들을 모두 pop해주..

[백준] 좋은 친구

https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 슬라이딩 윈도우를 이용하는 문제입니다. 문제부터 간단하게 요약하면, 성적 순으로 학생들의 이름이 주어지면, 좋은 친구의 쌍 수를 구해야 하는 문제입니다. 여기에서 좋은 친구라는 것은 등수 차이가 K를 넘지 않고, 이름의 길이가 같아야 합니다. 이름 길이가 2글자에서 20글자 사이이기 때문에, 이름 길이를 이용한 array를 만들어 두고, window를 움직이면서 계산을 해주면 ..