본문 바로가기

알고리즘

백준 알고리즘 14890 입력 : 지도 정보, 경사로 설치에 필요한 길의 길이 출력 : 지나갈 수 있는 길의 개수 풀이 1. 행과 열을 각각 처리하도록 구현. 지도의 길을 각각 조사해 지나갈 수 있는 길은 1을 리턴, 지나갈 수 없는 길은 0을 리턴했다. 2. 평지에서는 반복문을 continue, 높이가 2칸 이상이면 길을 만들 수 없기 때문에 0을 리턴했다. 3. check변수를 만들어 계단을 설치한 부분은 true로 하고 나머진 false로 만들었다. 길을 올라가야할 때는 지나온 길에 계단을 설치해야 하는데 이미 계단이 있다면 계단을 설치할 수 없기 때문이다. #include using namespace std; int board[101][101]; bool checkForRow[101][101]; bool checkForC..
백준 알고리즘 15686 입력 : 도시의 크기와 유지할 치킨집의 최대 개수 M, 도시 정보 출력 : 치킨집의 최대 개수(M)만큼을 제외하고 모두 폐점시켰을 때 치킨거리의 최소값 풀이 1. 입력받을 때 치킨집과 가정집의 위치를 따로 벡터에 저장한다. 2. 모든 치킨집 중 M개를 고르는 재귀함수를 구현해 M개를 고른 뒤 치킨거리를 구한다. 3. 치킨집을 고른 결과가 중복이 되지 않도록 재귀함수를 구현한다. 중복처리 안하면 시간초과남 #include #include #include #include using namespace std; struct Point{ int x; int y; }; Point getPoint(int x, int y){ Point result; result.x = x; result.y = y; return res..
백준 알고리즘 15685 입력 : 드래곤 커브 갯수, 각 드래곤 커브의 시작점과 시작 방향 및 세대 출력 : 네 꼭지점이 모두 드래곤커브인 정사각형의 갯수 풀이 1. 한 드래곤 커브에 대한 정보를 입력받으면 바로 드래곤커브를 그린다. 2. 최소 1세대 이상이기 때문에 0세대 드래곤커브를 우선 그린다. 3. 세대만큼 반복문을 사용해 드래곤 커브를 그린다 - 각 점을 드래곤커브의 마지막 점을 기준으로 시계방향 90도 회전한 지점에 복사한다. 이를 위한 식은 다음과 같다. x = p.x - stdp.x; y = p.y - stdp.y; return getPoint(stdp.x - y, stdp.y + x); - 드래곤 커브는 bool 2차원 배열에 표현한다. 4. 모든 드래곤 커브를 그린 다음 전체 판에서 꼭지점이 모두 드래곤커브인 ..
백준 알고리즘 14888 입력 : 연산할 수열, 연산자별 사용 가능한 갯수 출력 : 연산 결과로 나온 경우의 수 중에서 최대값과 최솟값 풀이 1. 재귀함수 한 번은 배열의 숫자 사이에 연산자를 하나 넣어본 것과 같다. 2. 함수를 한번 호출해 연산자를 넣어 계산한 뒤 재귀호출 3. 수열의 맨 마지막 수를 지나치면 전역변수 maxR과 minR을 연산 결과값이랑 비교해 갱신하고 return. 4. 연산자 사용시 opSymbol에 남은 횟수를 갱신해야 함 소스코드 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 ..
백준 알고리즘 14503 입력 : 장소의 크기 N*M, 초기 로봇청소기의 위치와 방향, 청소할 장소의 모양 출력 : 로봇청소기가 청소한 구역의 갯수 풀이 1. 로봇청소기가 특정 방향으로 움직일 때, 고려해야 할 상황은 총 3가지이다 -> 이동할 곳이 벽인가 -> 이동할 곳이 이미 청소를 한 곳인가 -> 해당 방향으로 이동하면 범위를 벗어나는가 2. 세 가지를 모두 한번에 확인할 수 있도록 하기 위해 boolean타입의 테이블을 만들어 벽과 청소한 구역을 표시 3. N*M의 장소를 (N+1)*(M+1)로 바꿔 가장자리를 모두 벽으로 매꿔 한번에 세 가지 상황을 모두 고려하도록 함 4. 2번과 3번의 처리 이후엔 문제에 나온, 로봇청소기를 4가지 이동방식에 따라 r,c를 계산해 결과값을 출력한다. 소스코드 1 2 3 4 5 6 7 ..
백준 알고리즘 14891 입력 : 톱니바퀴 모양, 회전 횟수와 회전할 바퀴, 방향 출력 : 회전 후 톱니의 모양 풀이 1. 톱니모양을 나타내는 값 사이에 공백이 없어 int로 받을 시 0과 1을 8개받는게 아닌 8자리 수로 입력됨 -> 문자열로 입력받아 문자열로 모두 처리 -> 8자리 수로 받은 뒤 각 자리 수를 저장(채택) 2. 톱니바퀴를 돌리기 전, 좌우 톱니바퀴를 돌려야 하는지 확인한 후 돌려야하면 재귀실행 -> 무한반복할 수 있으니 한번 돌린 바퀴는 전역변수로 표시해주기 -> 맨 왼쪽이나 맨 오른쪽 범위 계산 3. 좌우 톱니바퀴는 돌리기 전 상태에서 확인해야 하기 때문에 재귀실행 후에 바퀴를 돌려야 한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..
백준 알고리즘 1673 입력 : 치킨쿠폰 개수 n, 치킨과 교환할 수 있는 도장 개수 k 출력 : 주문할 수 있는 치킨 수 풀이 1. 쿠폰 개수만큼의 치킨을 주문하고 도장을 받는다 2. 도장으로 한마리 주문하고 도장 하나를 받는다 3. 도장으로 주문할 수 없을 때까지 주문한 뒤 지금까지 주문한 치킨 개수를 출력한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using namespace std; int main() { int stamp = 0; int coupon; int chicken = 0; int couponPerChick = 0; while(cin>>coupon>>couponPerChick){ stamp = coupon; chick..
백준 알고리즘 14889 입력 : 축구 인원 N과 능력치 테이블 출력 : 팀을 구성하는 경우의 수 중에서 두 팀 간의 능력치차이가 제일 적을 경우의 능력치 차이 값 풀이 1. 한 팀을 만드는 모든 경우의 수를 재귀함수를 통해 구한다. -> 재귀실행 1회 당 선수 1명 영입 -> 재귀실행 N/2회 실행시(기저조건), teamA에 인원이 N/2명이면 팀 능력치 계산 -> teamA에 없는 선수를 teamB에 영입해 능력치 계산 후 차이를 계산해 리턴 2. 중복을 피하기 위해 i번 선수 영입 후 다음 영입 선수는 i+1이상의 선수 중에서 선택 소스코드 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 3..