본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 14503번 : 로봇청소기 답 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net dfs를 이용한 구현문제였습니다. 풀이방법 나와 있는 조건을 검사하며 구현하시면 됩니다 Code #include using namespace std; int n,m; int board[11][11]; int ck[11][11]; //북 동 남 서 int dx[] = {-1, 0, 1,0}; int dy[] = {0, 1, 0,-1}; int area[51][51]; int visited[51][51]; int..
(C++) - 백준(BOJ) 2473번 : 세 용액 답 www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net two pointer문제였습니다. 풀이방법 1. 첫 번째 용액 특성값을 first로 두고 n-2까지 loop를 돕니다. 2. 나머지 first+1 ~ n - 1까지 two pointer로 정답을 찾습니다. 3. 오름차순으로 정렬한 세 특성값을 출력합니다. Code #include #include #include #define ll long long using namespace std; ll..
(C++) - 백준(BOJ) 17626번 : Four Squares 답 www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net dp문제였습니다. 풀이방법 i라는 제곱수를 구하기 위해 필요한 최소 숫자의 개수는 min(dp[i], j = 1부터 루트 i까지 dp[j*j] + dp[i-j*j]) 입니다. Code #include #include #include using namespace std; int n; vector dp (50001,0x7f7f7f7f); int main(){ cin >> n; f..
(C++) - 백준(BOJ) 1439번 : 뒤집기 답 www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 간단한 문자열 처리 문제였습니다. 풀이방법 1. 연속하는 영역의 개수를 세었습니다. 1-1. 연속하는 '0'영역의 개수 : zeroArea변수에 저장 1-2. 연속하는 '1'영역의 개수 : oneArea변수에 저장 2. 두 영역의 개수 중 영역의 개수가 적은것을 출력했습니다. Code #include using namespace std; string s; int zeroCnt, oneCnt; int main()..
(C++) - 백준(BOJ) 17608번 : 막대기 답 www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 간단한 구현 문제였습니다. 풀이방법 오른쪽에서 봤을 때 가장 앞 원소는 오른쪽 끝에 있는 막대기고 이 막대기의 높이만큼 나머지 막대기를 볼 시야를 가리고 있습니다. 따라서 보이는 막대기의 수는 무조건 오른쪽 막대기부터 시작하여 높이를 확인해가면서 왼쪽 막대기를 보고, 오른쪽 막대기보다 왼쪽 막대기가 더 크다면 이 왼쪽 막대기는 보인다고 할 수 있습니다. 그렇다면 오른쪽 막대기부터 시작해 왼쪽 막대기로 순차적으로가며 ..
(C++) - 백준(BOJ) 11725번 : 트리의 부모 찾기 답 www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이방법 1. 입력을 받습니다. 받을 때 정점 사이의 간선들이 주어지므로 정점 n개를 가진 tree자료구조에서 간선들의 개수는 n-1개입니다. 따라서 그만큼 입력을 받고 vector에는 인접행렬 형식으로 양방향 간선을 추가해줍니다. 2. parent[x] 는 x정점의 부모에 해당하는 정점 번호가 값으로 들어갑니다. root node로부터 시작, 각 정점에 연결된 간선을 정보를 따라 만약 갱신되지 않은 부모배열 방이 있다면 갱신해줍니다. 즉, vector[1]이라는 정점에 연..
(C++) - 백준(BOJ) 2589번 : 보물섬 답 www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net bfs를 이용해 한 대륙에서 타일과 타일사이의 최대거리를 구하는 문제였습니다. 풀이방법 : 육지가 나올 때마다 bfs로 최대거리를 구한 후 갱신합니다. Code #include #include #include using namespace std; int n, m, ans; int d[51][51]; int ck[51][51]; char map[51][51]; int dx[] = {0,0,1,-1}; int dy[]..
(C++) - 백준(BOJ) 1107번 : 리모컨 답 www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net backtracking으로 푸는 문제였습니다. 풀이방법 1. 고장나지 않은 channel 번호를 vector 배열에 저장합니다. 2. 모든 자리 수에 대해(1자리~7자리) 고장나지 않은 channel번호를 backtracking으로 대입하여 목표 channel에서 가장 가까운 channel을 구합니다. 3. 100번으로 시작해서 목표 channel로 가는 것과 backtracking하여 구해..

티스토리툴바