본문 바로가기

전체 글

 (2344)
(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하여 구해..
(C++) - 백준(BOJ) 5525번 : IOIOI 답 www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 풀이방법 n이 1인 경우에 IOI는 1 IOIOI는 2 를 답으로 출력해야합니다. 따라서 OI를 한 set으로 계속 2씩 증가하며 이를 하나로 치고 개수를 세줬을때 n과 같으면 answer가 1씩 증가합니다. Code #include #include using namespace std; int n,m,ans=0; string word; //IOI 1 //IOIOI 2 //I한번나오면 n개수만큼 OI가 나올 때마다 답 1증가 int mai..
(C++) - 백준(BOJ) 5430번 : AC 답 www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net deque 자료구조를 사용해 푸는 문제였습니다. 풀이방법 1. 문자열로 부터 수를 적절히 parsing하여 deque에 저장 2. R이 짝수만큼 입력이라면 이후에 D가 나올 경우 좌측부터 우측순으로 지워지게 됨. 반대의 경우에는 우측에서 좌측순으로 지워짐. 그 방식으로 D가 나올때마다 순서에 맞게 지워나감. 지울 때 이미 deque의 size가 0이라면 error출력 3. D를 모두 수행했을 때 원소가 없으면 빈 배열인 []를 출력. Code #include #inc..
(C++) - 백준(BOJ) 14500번 : 테트로미노 답 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 완전탐색(brute force)을 구현해보는 문제였습니다. 풀이방법 : 도형의 종류를 구분하고 이 도형을 구성하는 타일 값들의 합 중 최대값이 답입니다. 도형 1. 2가지의 모양들 중 각 모양에 대한 타일들 합 최대값 반환 도형 2. 1가지 모양에 대한 타일들 합 반환 도형 3. 8가지 모양들 중 각 모양에 대한 타일들 합 최대값 반환 도형 4. 4가지 모양들 중 각 모양에 대한 타일들 합 최대값 반환 도형 ..
(Python) - 백준(BOJ) 1541번 : 잃어버린 괄호 답 www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문자열을 parsing하고 수학적으로 최소값을 구하는 문제였습니다. 풀이방법 1. '-'를 기준으로 식들을 나눈다. 문제의 예제를 예시) 55-50+40 인 경우 [55,50+40]이 됩니다. 2. 처음 식 ('-'로 나눈 후 배열의 첫번째 원소)은 '+'가 포함되어 있을 수 있으니 '+'를 기준으로 split한 뒤 나온 배열의 모든 원소를 더해 처음 식의 결과 값을 구합니다. 그 후 답 변수인 ans의 ..

티스토리툴바