PS
BOJ 1157 - 단어 공부
https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 처음 이 문제를 풀었을 때는, algorithm 헤더의 count 함수를 이용해서 문자열에 포함된 각 문자들의 갯수를 카운팅하려 했다. 그러나 한가지 간과한것이 있었는데, algorithm 헤더의 count() 함수에 대한 시간 복잡도가 O(N) 이기 때문에 입력 받은 문자열 기준 한바퀴를 도는 포문 O(N) 과 겹쳐서, O(N^2) 의 시간 복잡도를 갖는 코드가 되었고, 계속 시간초과가 발생하였다 그래서 다음과 같이 수정해서 코..
BOJ 2231 - 분해합
https://www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 브루트포스 를 이용해서 푸는 문제로, 조건만 잘 맞추면 어렵지 않게 풀 수 있는 문제다 나 같은 경우엔 1 부터 백만까지의 수(i) 를 돌려서 그 수(i) + 그 수의 각 자리수의 합 (i 의 자리수 합) 을 구한다음 그 값이 입력받은값 N 과 동일하면 값을 출력하고, 전체 다 돌았음에도 값을 찾지 못하는 경우 0 이 출력되도록 해주면 풀렸다. - c++ #include ..
BOJ 2042 - 구간 합 구하기
https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 세그먼트 트리를 이용한 문제. 세그먼트 트리는 배열 같이 연속적인 데이터가 주어졌을 때, 일부 구간 마다의 합을 구해서 트리로 표현하는 자료구조다. http://arkainoh.blogspot.com/2018/06/segment.tree.html [Algorithm] 세그먼트 트리 (Segment Tree) 세그먼트 트리(Segment..
BOJ 2309 - 일곱 난쟁이
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net Brute Force 알고리즘에 대한 기초 연습을 할 수 있는 문제 - c++ #include #include using namespace std; int keys[9]; int sum; bool checked; int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); for (int i = 0; i > keys[i]; sum += keys[i];..
BOJ 1002 - 터렛
https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원 사이의 교점의 갯수를 구하는 문제로 공식을 알고 있으면 풀 수 있는 문제다 두 원의 중심좌표간 거리를 s 라 할때, s 는 아래의 식으로 구해진다. 그리고 두 원 사이의 교점의 갯수는 1. 두 원의 중심좌표가 서로 같은 경우 (x2 == x1 && y2 == y1) -1) r1 != r2 이면 교차하는 점의 갯수가 0 -2) r1 == r2 이면 교차하는 점의 갯수가 원이므로 무한대 2. 1이 아닐때 -1) abs(r1 - r2) < s &&..
BOJ 1759 - 암호 만들기
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 처음에 이 문제를 풀때, 다음과 같은 제한조건들을 생각해보았다 1. 모음의 갯수가 한개 이상 2. 자음의 갯수가 두개 이상 3. 사전순(오름차순) 으로 정렬되야 한다 4. L 개의 문자를 다 탐색하면 백트래킹 탈출 조건으로 잡는다. 라고 생각해서 처음엔 아래와 같이 코드를 짰었다. - c++ #include #include #define MAX 16 using namespace std; int L, C..
BOJ 3613 - Java vs C++
https://www.acmicpc.net/problem/3613 3613번: Java vs C++ 문제 Java 예찬론자 김동규와 C++ 옹호가 김동혁은 서로 어떤 프로그래밍 언어가 최고인지 몇 시간동안 토론을 하곤 했다. 동규는 Java가 명확하고 에러가 적은 프로그램을 만든다고 주장했고, 동�� www.acmicpc.net 예외 사항에 대해서 여러가지 생각해야 되는게 많은 문제였다. - 첫글자나 마지막 글자에 '_' 나 대문자가 오는가 - '_' 다음에 대문자가 오는가 - '_' 가 연속으로 나오는가 - c++ 이라 처리 했는데 대문자가 나오거나 - java 라 처리 했는데 '_' 가 나오거나 혼자서 문제풀때는 사실 이 모든 예외사항에 대한 부분들을 전부 생각해내지 못했다. 아래의 블로그를 보고나서..
BOJ 1919 - 애너그램 만들기
https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs� www.acmicpc.net - c++ #include #include using namespace std; int alphabet1[26], alphabet2[26]; int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); string str1, str2; cin >> str1 >> str2; // 아래의 두 for 문은 각 str 이 ..