분류 전체보기 (9) 썸네일형 리스트형 [BOJ] 백준 2904 수학은 너무 쉬워 (C++) 문제 링크 www.acmicpc.net/problem/2904 2904번: 수학은 너무 쉬워 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다. www.acmicpc.net 카테고리 소인수 분해(수학) 문제 풀이 1. 먼저, 소수를 모두 구해 배열에 저장한다. (에라토스테네스의 체) 2. cal(num)을 통해 모든 입력 받은 num (총 N개)에 대한 소인수 분해를 진행한다. 👉 이 결과는 map dict[]에 각각 저장한다. (인수, 지수) 👉 단, 이때 소인수 분해한 모든 값들을 누적해서 map mp에 저장한다. (인수, 지수) 3. 이제, mp에 저장된 인수들의 지수 값들을 N으로 나누어.. [BOJ] 백준 1915 가장 큰 정사각형 (C++) 문제 링크 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 카테고리 DP 문제 풀이 * DP[X][Y] = N : (X,Y)가 어떤 정사각형의 우측 아래 꼭지점일 때, 될 수 있는 정사각형들 중 최대 변의 길이는 N이다. 1. 만약 행이나 열의 idx가 0인 경우 (X == 0 || Y == 0) 👉 DP[X][Y] = board[X][Y] 2. 인접한 위,좌상,왼쪽의 dp값 중 0이 있는 경우 👉 DP[X][Y] = board[X][Y] 3. 인접한 위,좌상,왼쪽의 dp값이 모두 0이 아닌 경우 👉 DP[X][Y] = min(.. [BOJ] 백준 2616 소형기관차 (C++) 문제 링크 www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 카테고리 DP 문제 풀이 1. DP[X][N] = X개의 기관차를 이용해 1~N번째의 객차까지 끌었을 때의 최댓값 ex) DP[2][6] : 2개의 기관차를 이용해 1~6번까지의 객차를 끌었을 때 최댓값 2. sum[N] = 기관차 1개가 N번부터 객차를 연결해 운송할 때 운송할 수 있는 최대 손님의 수 3. 점화식 3.1 DP[1][N] = max(DP[1][N-1], sum[N]) 3.2 D.. [BOJ] 백준 1461 도서관 (C++) 문제 링크 www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net 카테고리 그리디 문제 풀이 1. 양수, 음수 위치의 도서들을 분류해서 벡터에 저장한다. 2. 각각의 양수, 음수 도서들을 거리가 먼 순서로 정렬한다. 👉 +, - 위치의 도서들을 섞어서 가져다 놓으면, 0을 여러번 지나게 되므로 최솟값이 나올 수 없다. 3. 최대로 들 수 있는 책의 개수 만큼 각각 묶음을 짓는다. 3.1 각 벡터의 앞에서부터 묶고, 각 묶음의 첫번째 원소를 기준으로 .. [BOJ] 백준 2638 치즈 (C++) 문제 링크 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 카테고리 BFS, 아이디어 문제 풀이 1. 외부공기를 기준으로 BFS 탐색을 한다고 생각한다. 2. 현재 남은 치즈의 수를 remain으로 설정해 이 개수를 통해 치즈가 다 녹았는지 판단한다. 3. 다음과 같이 BFS 탐색을 한다. 3-0. (0, 0)과 연결된 영역을 찾는다는 느낌으로 BFS 탐색을 한다. 3-1. 다음 탐색할 위치(nx,ny)가 치즈이면 해당 위치의 isMelt[nx][n.. [BOJ] 백준 14923 미로 탈출 (C++) 문제 링크 www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 카테고리 BFS, 아이디어 문제 풀이 1. BFS 탐색을 통해 출구를 찾는다. 2. mazeVisit[x][y][A] : (x, y) 위치에 A번 마법을 쓸 수 있는 상태로 왔었는지 확인 (0: 온 적 없음, 1: 온 적 있음) ex) mazeVisit[2][3][1] = 1 : (2,3) 위치에 1번 마법을 쓸 수 있는 상태일 때 도착한적이 있음 => 방문했다면, 방문한 상황에 맞.. [BOJ] 백준 1600 말이 되고픈 원숭이 (C++) 문제 링크 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 카테고리 BFS, 아이디어 문제 풀이 1. BFS 탐색을 통해 원숭이가 도착점에 도달하는지 판단한다. 2. 이를 위해 방문 배열을 설정한다. 2.1 boardVisit[x][y][move] : (x,y) 지점에 move만큼 이동횟수가 남은 채로 온 적이 있다. 3. 12가지 경우의 수를 이용해 원숭이의 다음 위치를 계산해 큐에 넣는다. 3.1 (0~3 : 상하좌우, 4~11 말처럼 이.. [BOJ] 백준 17281 ⚾ (C++) 문제 링크 www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 카테고리 백트래킹, 브루트 포스 문제 풀이 1. 백트래킹을 이용해 야구선수들의 순서를 정한다. (백트래킹) 2. 각 순서에 맞게 게임을 시작해 본다. (브루트 포스) 3. 게임의 조건에 맞게 야구를 시작하고, 해당 순서에 따른 점수를 비교해 그 중 최댓값을 출력한다. * 게임 조건 더보기 1. 이닝별로 게임을 시작한다. (이닝 시작 시 변수들 초기화) 2. 베이스에 나가있는 타자들의 위치를 remainBa.. 이전 1 2 다음
