공부하자

12904번: A와 B (acmicpc.net) 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 아무리 생각해도 브루트포스로 풀면 시간초과가 나올거 같아 생각을 하던 중, S에서 T를 만들지 말고 T에서 S를 만드는 방법으로 생각하니 금방 풀렸다. 풀이 T에서 S로 만드는 알고리즘으로 바꾸어 생각해보자. 그렇다면 적용할 수 있는 연산은 T의 마지막 글자에 따라 무조건 하나로 정해지게 된다. case 1. T의 마지막 글자가 A인 경우 : pop_back() case 2. T..

1918번: 후위 표기식 (acmicpc.net) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 저번 학기 자료구조 수업때 배웠던 중위표기식 -> 후위표기식 변환 알고리즘을 복습할겸 다시 풀어보았다. 자료구조 수업때는 JAVA 환경에서 직접 stack 함수를 만들어 구현하였는데, 이번에는 C++환경에서 stack 라이브러리를 가져와 새로 구현하게 되었다. 오랜만에 구현하는 내용이라 그런지, stack에 담긴 연산자 우선순위를 고려하여 처리해주는 부분에서 조금 버벅거렸다. 구현 #include #in..

17609번: 회문 (acmicpc.net) 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net #1254에서 다뤘던 팰린드롬 관련 문제이기도 했고, 애초에 그리 어려운 문제는 아니었지만, 중간에 반례를 찾던중 접근 방식을 한번 갈아 엎어서 시간이 오래 걸렸다. 팰린드롬 (palindrome) / 회문 (回文) 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. #1254 팰린드롬 만들기와 같은 내용을 담고있어서 접근하기엔 수월했다. 처음엔 #1254에서의 코드를 조금 고쳐 함수 하나로 처리하도록 만들었다. 기존 C++ 코드 (함..

1254번: 팰린드롬 만들기 (acmicpc.net) 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 이해를 하고나면 쉬운 문제이다. 팰린드롬 (palindrome) 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. #include using namespace std; string s; int len; bool F(int a) { for (int i = 0; a+i < len-1-i; i++) { if (s[a+i] != s[len-1-i]) return false; } return true; } ..

4948번: 베르트랑 공준 (acmicpc.net) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 베르트랑 공준 문제를 풀기 위해서는 이 에라토스테네스의 체를 활용한 소수판별법을 먼저 알아야한다. 이 방법을 이용하지 않고 기존의 방법처럼 무식하게 풀다보면 시간 초과가 나오게 된다. 에라토스테네스의 체 (Sieve of Eratosthenes) 에라토스테네스의 체란 소수를 대량으로 빠르고 정확하게 구하는 방법이다. 시간 복잡도는 O(N^(1/2)). 이는 다음과 같은 절차로 진행된다. 원하는 숫자까지의..

7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS 알고리즘을 이용하여 구현하는 그래프 탐색 문제이다. 알고리즘을 구상하고 코드로 직접 옮기는 과정에서, 행렬로 되어있는 입력 예시들을 그래프로 바꾸어 이해하는 단계가 좀 껄끄러웠다. 게다가 문제에서 익은 토마토의 개수가 여러개인 경우도 고려하여 구현해야 되기 때문에 이것또한 생각을 많이 해야했다. C++ / vs code 환경에서 구현하였다. #include #include using namesp..

1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS의 구현을 묻는 아주 간단한 문제이다. 우선, DFS와 BFS의 의미는 다음과 같다. DFS : Depth-First Search (깊이 우선 탐색) / BFS : Breadth-First Search (너비 우선 탐색) DFS는 함수의 재귀 호출을 이용하여 소스코드로 구현하게 되지만, BFS의 경우엔 자료구조 Queue를 사용하여 소스코드로 구현하는것이 일..

Vector 란? Vector는 C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너로, 사용자가 손쉽게 사용하기 위해 정의된 class이다. Vector는 쉽게 말해 크기가 가변적으로 변하는 배열이라고 할 수 있다. 속도적인 측면에서는 배열에 비해 떨어지지만 메모리를 효율적으로 관리할 수 있다는 장점이 있어 굉장히 많이 사용한다. vector는 배열과 마찬가지로 원소들이 하나의 메모리 블록에 연속하게 저장된다. 그렇기에 원소가 추가되거나 삽입될 때 메모리 재할당이 발생할 수 있고 상당한 부하가 발생하게 된다는 점은 단점으로 꼽히고 있다. Vector의 구조 Vector를 생성하면 메모리 heap에 생성되며 동적할당된다. front() : 첫번째 원소 back() : 마..

STL : 표준 템플릿 라이브러리 (Standard Template Library) C++를 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. C++ 표준 라이브러리 (C++ Standard Library) C++과 C++ ISO 표준 자체로 쓰여진 클래스들과 함수들의 집합이다. C++ 표준 라이브러리는 여러 Generic 컨테이너들, 그리고 이러한 컨테이너들과 함수 객체, Generic 문자열, stream, 몇몇 언어 특징 그리고 power 연산 같은 작업을 위한 함수들을 제공한다. C++ 표준 라이브러리의 특징은 namespace 내에 선언된다는 것이다. (.h 헤더가 아님) C++ 표준 라이브러리와 STL이 많은 특징들을 공유하지만, 둘 중 어느것도 다른 하나의 상위 집합은..

배열 (Array) : 여러 데이터를 하나의 이름으로 그룹핑하여 관리하기 위한 자료구조 배열의 장점 배열의 단점 크기가 정해져 있다. (이미 정해진 크기로 인해 작고 가벼우며, 메모리 또한 작음) 크기가 정해져 있다. (미리 크기 지정 필요, 크기보다 큰 인덱스에 접근하면 에러 발생) 기능이 없다. (단순함, 좋은 구성요소가 될 수 있음) 기능이 없다. (불편함, 데이터의 삭제, 추가 등이 불가능) 리스트 (List) : 순서가 있고, 값의 중복을 허용하는 자료구조 추가하는 경우 Array는 지정 인덱스에 추가할 경우, 크기가 제한되어 있어 데이터가 덮어 씌워진다. List는 지정 인덱스에 추가할 경우, 유동적으로 한칸 뒤로 밀고 끼어든다. 삭제하는 경우 Array는 지정 인덱스를 삭제할 경우, 그 인덱..