본문 바로가기

Algorithm

 (2139)
(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의 ..
(C++, Python3) - 백준(BOJ) 2470번 : 두 용액 답 www.acmicpc.net/problem/2470 2470번: 두 용액첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00www.acmicpc.netBinary Search 혹은 Two Pointer로 풀 수 있던 문제였습니다.📕 풀이방법📔 입력 및 초기화배열길이와 배열을 입력받고 오름차순으로 원소들을 저장합니다.📔 풀이과정📑 Two Pointer 1. 두 용액의 특성값을 더했을때 기존에 있던 결과값보다 작다면 갱신 2. 두 용액의 특성값 합이 0이하면 left pivot을 ++ 3. 두 용액의 특성값 합이 0초과면 ..
(C++) - 백준(BOJ) 1992번 : 쿼드트리 답 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 재귀를 이용한 문제였습니다. 풀이방법 1.압축할 수 있으면 : ans+='(', 압축 진행, ans += ')' 2. 압축할 수 없으면 영역에 따라 0또는 1을 ans에 추가 Code #include #include using namespace std; int n; int video[64][64]; string tmpVideo[64]; string ans; bool haveToBePressed(in..
(C++) - 백준(BOJ) 18870번 : 좌표 압축 답 www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 구현을 해보는 문제였습니다. 문제의 조건이 수식으로 되어있어서 좀 헷갈렸던 것 같습니다. ㅋㅋㅋ 좌표를 압축한다 : 해당 좌표의 값을 그 값보다 작은 좌표값들의 개수로 대체한다의 의미입니다. 풀이방법 1. 매 좌표마다 값,index를 vector pair형태로 저장한다. 2. 값을 기준으로(vector.first) 오름차순 정렬 3. 오름차순 정렬된 상태에서 답..
(C++) - 백준(BOJ) 1780번 : 종이의 개수 답 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 9부분으로 나누어 종이의 개수를 파악할 때 반복되는 부분에 대해 재귀로 구현했습니다. 풀이방법 n = 9일 때 3*3짜리 정사각형 또는 1*1짜리 정사각형으로 종이를 나누어 볼 수 있습니다. 이럴 경우 가로를 3등분 세로를 3등 분하며 계속 종이를 세기 때문에 원래의 영역에서 9등분씩 나누어지게 됩니다. 따라서 이 9부분에 대해 종이인지 아닌지 판별한 후 종이가 아니라면 다시 현재 영역에 대해 9등분..

티스토리툴바