![]()
제목을 잘못 적은 게 아니라, 문제 이름이 박성원이다.. 심지어 solved ac 공식 standard 문제! 풀이 이 문제는 3가지 부분 문제가 포함되어 있다고 볼 수 있다. 무려 길이가 최대 50인 자연수에 K로 나눈 나머지를 어떻게 구할 것인가 기약 분수 형태 출력은 어떻게 하는 게 빠를까? 위에 두 개 알았는데.. 그래서 어떻게 푸는데..? 우선 하나씩 해결해보자. 1. 큰 수(BigInteger) 나누기 우린 초등학교 3학년 때 구구단을 외우고, 4학년 때 나누는 방법을 배운다. 초4 수환이 큰 수 111111을 3으로 나누면 이런 방식으로 나눌 것이다. 이 과정을 살짝 프로그래밍적으로 분석하면 과정은 이러하다. 가장 앞자리 (자릿수가 가장 큰)부터 시작한다. 갖고 있는 수에 10을 곱한 후, ..
![]()
본 포스팅은 Fundamentals of Data Structures in C++ 책에 있는 내용을 바탕으로 정리한 글입니다. Index 시스템 생명 주기 객체 지향 설계(Object-Oriented Design) 데이터 추상화와 캡슐화 c++의 기초 표준 템플릿 라이브러리(STL) 0. 개요 프로그램 과정 프로그램은 Input -> processing -> output 순서로 이루어져 있다. Input Input에는 데이터(값, 타입)가 들어가며 데이터 타입을 정의할 때는 각각 명세와 구현 방법이 있다. 명세는 데이터의 논리적 정의를 의미하며, 데이터가 무엇이고 각 연산은 무슨 기능을 수행하는지 정의한다. 구현은 실제 데이터가 어떻게 컴퓨터 저장장치에 표현되고 각 연산이 어떻게 구현되는지 정의한다. p..
![]()
문제를 풀다가 다른 사람 코드를 봤더니 queue를 쓰던 map을 쓰던 새로운 요소 혹은 객체를 삽입할 때 make_pair, make_tuple을 이용해 객체를 만들고 push 하는 것이 아니라 그냥 emplace 함수를 이용해 간편하게 넣는 걸 보고 간편하다고 생각되어 찾아보니 효율도 대체적으로 좋은 듯하여 따로 찾아 정리를 해본다. (안 좋은 경우도 있다고 합니다.) 1. 정의 c++ reference 에서 emplace를 찾아보니 이러한 설명이 나왔다. 컨테이너에 키가있는 요소가 없는 경우 지정된 인수로 구성된 컨테이너에 새 요소를 삽입한다. emplace를 주의해서 사용하면 불필요한 복사 또는 이동 작업을 피하면서 새로운 요소를 구성할 수 있다. 반복자 및 참조자가 무효화되지 않는다. 여기서 말..
![]()
문제 링크 :https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 가장 간단한 LCS(Longest Common Subsequence)를 찾는 문제입니다. LCS 문자열 찾기 : https://suhwanc.tistory.com/80 LCS 알고리즘 1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다...
![]()
문제 링크 : https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCR www.acmicpc.net 풀이 가장 간단한 LCS(Longest Common Subsequence)를 찾는 문제입니다. LCS 문자열 찾기..
![]()
문제 링크 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 가장 대표적이고 기본적인 LCS 길이 찾기 문제이다. LCS 길이 찾기 방법 : https://suhwanc.tistory.com/80 LCS 알고리즘 1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence..
1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence)이란 어떤 단어에서 연속되지 않는 부분 문자열을 뜻하는데 연속된 부분 문자열을 나타내는 부분 문자열(Substring) 도 있다. (따라서 string 헤더파일의 substr()은 substring을 의미한다) 두 부분 문자열의 차이는 예를 들자면 pringles sangeles 이렇게 두 문자열이 있을 때 가장 긴 Subsequence는 pringles sangeles "ngles" 가 되고 가장 긴 Substring은 pringles sangeles "les" 가 된다. 위에서 알 수 있듯 가장 긴 Substring은 ..
![]()
문제 링크 : https://www.acmicpc.net/problem/1042210422번: 괄호‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 www.acmicpc.net문제 설명괄호 문자열의 길이가 주어졌을 때, 올바른 괄호 문자열의 개수를 구하는 문제이다.출력에서 10억+7로 나눈 나머지를 출력..
![]()
문제 링크 : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 문제 요약 여러 파일들이 주어졌을 때 파일들을 두 개씩 합쳐서 여러 장들이 연속이 되도록 파일을 합쳐나가 최종적으로..
아마 이 문제 때문에 찾아오신 분들은 시간 초과 때문에 화가 나서 검색해 들어오셨을 텐데 문제 풀이는 생략하고 시간을 줄이는 방법에 대해 설명하겠습니다.ㅠㅠ 우선, class를 만들어 vector로 저장하든, 그냥 각각을 배열로 저장하든, 큰 차이는 없어 보입니다. (물론, vector가 조금 더 느리긴 하나, 깔끔하게 구현된 vector는 정답이 가능합니다) c++의 경우, cin, cout을 마구 쓰면 참가자의 정보(0과 1)를 저장할 때 최대 400만 번 입력을 받아야하기 때문에 무조건 시간초과입니다. 하지만 printf, scanf를 써도 400만번 입력은 2초 안에 정답을 낼 수 없습니다. 그렇기 때문에 cin.tie(0), sync_with_stdio(false)를 쓴 후 cin, cout을 ..
![]()
문제 링크 : https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 풀이 시뮬레이션 문제입니다! 이 문제는 조건이 조금 까다로운데, 나는 4가지 조건 중 c,d 번 먼저 해결하려고 하..
![]()
문제 링크 : https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 풀이 브루트 포스 문제입니다! 문제 난이도에 비해 생각보다 쉽지 않아서 많이 고전했던 문제이다. 이 문제는 개인적으로는 그 전 시리즈 문제 (BOJ 14888번 연산자 끼워넣기 https://www.acmicpc.net/problem/148..
