본문 바로가기

분류 전체보기

 (92)
백준_7571_점모으기_c++ https://www.acmicpc.net/problem/7571 7571번: 점 모으기 첫 줄에는 격자공간의 크기와 점들의 개수를 나타내는 두 정수 N과 M이 하나의 공백을 사이에 두고 주어진다. 다음의 M줄에는 각 줄마다 격자공간내의 점의 위치를 나타내는 두 개의 정수가 하나 www.acmicpc.net 풀이 문제자체는 정말 단순한데 "m/2를 했을때 중간점이 2개이상 나올 수 있는데 상관이없나?" 라는 의문이 드는 문제였습니다. 다시한번 생각해보니 중간점이 여러개가 나와도 결국 점들이 중간점으로 이동할 떄 필요한 거리의 합은 똑같기떄문에 문제없이 풀립니다. #include #include #include using namespace std; vector vx; vector vy; int main()..
백준_2608_로마숫자_c++ https://www.acmicpc.net/problem/2608 2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net 풀이 로마숫자 -> 아라비아 숫자 각 로마숫자를 map에 저장한 뒤 로마숫자를 순차적으로 보면서 이전 로마숫자보다 현재 로마숫자가 작다면 현재값 - 이전값 을 해주었습니다. 아라비아숫자 -> 로마숫자 오래고민을 해봤는데 아무리봐도 코드적으로 규칙이 안보여서 하드코딩을 했습니다. 각 자리수에서 [1 ~ 3, 4, 5 ~ 8, 9] 인 경우들로 나누어 생각했습니다. #include #include #include #include #include usi..
백준_개근상_1563_C++ https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 풀이 주석을 보시면 좀더 이해 하기 쉬울겁니다. N이 최대 1000이므로 DP를 써야겠다고 생각했습니다. 끝으로 오는게 O,L,A로 나누어 생각하고 풀었는데 지각횟수또한 고려되어야 하기때문에 DP배열이 조금더 복잡해지는 문제였습니다. 다른분들 풀이를보니 저와 다르게 DP배열을 설계 하신분들이 많은데 참조 해보는것도 좋을 것 같습니다. #include #include #include #include #inclu..
[백준] 1141_접두사_c++ https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 풀이 정렬을 해야겠다 라는 생각이 들고나면 매우 간단히 풀리는 문제입니다. #include #include #include #include #include using namespace std; int main() { int n; cin >> n; vector v; for (int i = 0; i < n; i++) { string s; ci..
[백준] 괄호제거_2800_C++ https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 풀이 괄호를 보자마자 스택을 먼저 떠올렷습니다. 괄호의 개수가 최대 10개이므로 조합으로 풀 수 있다고 생각하여 재귀를 이용한 조합을 사용하였습니다. 재귀를 실행하기전에 괄호의 위치를 미리 저장해줬습니다.(여는거,닫는거 세트로) C++의 set은 저장하면 사전순으로 자동 정렬되는 성질을 이용하여 set에 저장하였습니다. #include #include #includ..
[백준] 10253_헨리_C++ https://www.acmicpc.net/problem/10253 10253번: 헨리 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T 가 정수로 주어진다. 각 테스트 데이터는 한 줄로 구성되며, 여기 www.acmicpc.net 풀이 문제가 엄청 복잡하게 쓰여져있는데 일단 시키는대로 하면 풀리는 문제였습니다. 라고생각했지만 시간초과가 뜨더군요. 최대 공약수를 사용한 분수계산식으로 변경하여 해결하였습니다. #include #include #include #include #include #include using namespace std; int t, a, b; int answer; int gcd(int a, int b) { r..
[프로그래머스] 가장 큰 정사각형 찾기 https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 문제 설명 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.) 예를 들어 1234 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 있다면 가장 큰 정사각형은 1234 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가..
[프로그래머스] 짝지어 제거하기 https://programmers.co.kr/learn/courses/30/lessons/12973?language=cpp 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 문제 설명 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를..

티스토리툴바