나의 프로그래밍 개발일기

2023. 10. 5. 15:58 Algorithm/Simulation, Implement

문제 https://www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 문제 접근 여러 조건에 따라 데이터를 정렬하는 문제 데이터만 잘 저장해 놓으면 나머지는 조건에 따라 정렬식을 구현하면 되는 문제였다. 필자의 경우 람다를 활용하여 정렬식을 구현하였다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; pu..

[백준][BOJ 2422] - Ice Cream

2023. 10. 4. 17:04 Algorithm/BruteForce

문제 https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 문제 접근 1부터 $N$까지의 수들 중 3개를 뽑는 경우의 수를 구하는 문제 단 제약 조건이 달려 있는데 섞어먹으면 안되는 조합이 존재한다는 것이다. 만약 1은 2와 섞일 수 없다 라고 한다면 (1, 2, X) 로 되어 있는 모든 조합은 카운팅되지 않는다는 것이다. 즉 3개를 뽑은 뒤 각각의 수가 섞일 수 없는 수에 포함되어 있는지를 한 번 더 체크해야 ..

[백준][BOJ 1251] - 단어 나누기

2023. 10. 4. 12:59 Algorithm/BruteForce

문제 https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 문제 접근 입력으로 주어진 단어에 대해 문자열을 나누어 뒤집고, 이를 다시 조합하는 것이 가장 핵심적인 로직이다. 이때 만들 수 있는 모든 단어를 만들어야 하므로 어떻게 문자열을 나눌 것인지를 생각해야 한다. 모든 경우의 수를 따져보아야 하므로 문제에서 제시된 조건인 각각의 문자열은 적어도 길이 1 이상이어야 한다를 만족하도록 문자열을 나누어 주면 된다. 2중 for문으로 만들어낼 수 있다. ..

[백준][BOJ 1448] - 삼각형 만들기

2023. 10. 4. 12:15 Algorithm/Greedy

문제 https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 문제 접근 삼각형 세 변의 길이의 합의 최댓값을 구해야 한다. 이때 삼각형의 조건을 만족할 수 있어야 한다. 즉 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작아야 한다는 조건을 만족해야 한다. 가장 나이브한 풀이는 완전 탐색을 사용하여 N개 빨대 중 3개를 선택하여 삼각형의 조건에 부합하는지를 검사하고, 통과한다면 그 합을 구해 최대 값을 갱신하는 방식이다. ..

[백준][BOJ 9017] - 크로스 컨트리

2023. 10. 3. 20:12 Algorithm/DataStructure

문제 https://www.acmicpc.net/problem/9017 9017번: 크로스 컨트리 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의 www.acmicpc.net 문제 접근 점수를 구할 때 6인보다 적은 팀은 점수 계산에 상정되지 않는다는 것을 유의해야 한다. 이는 즉 입력에서부터 각 팀원당 몇 명이 소속 되어 있는지를 확인해야 한다. 또한 상위 4인 까지의 점수의 합으로 먼저 판단한 뒤 동점이 나올 시 5번째로 들어온 사람의 점수를 사용하여 최종적으로 판별하는 것을 유의해야 한다. Map을 사용하면 매우 쉽게 구현이 가능한 문제였다. 정렬을 통해 ..

[백준][BOJ 20920] - 영단어 암기는 괴로워

2023. 10. 3. 15:21 Algorithm/DataStructure

문제 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 문제 접근 자주 나오는 단어일수록 앞에 배치된다. 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 이때 길이 $M$미만의 단어는 무시한다. 먼저 빈도수를 잘 계산하기 위해 key-value로 $O(1)$ 시간에 접근이 가능한 map을 사용하였다. 이후 위의 우선순위에 맞도록 정렬을..

[백준][BOJ 10431] - 줄세우기

2023. 10. 3. 14:10 Algorithm/Simulation, Implement

문제 https://www.acmicpc.net/problem/10431 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 문제 접근 삽입 정렬의 구현을 조금 변형하여 구현하는 문제였다. 현재 데이터 보다 큰 데이터가 앞에 있는 그 즉시 큰 데이터를 포함하여 그 뒤에 있는 모든 데이터를 한 칸씩 뒤로 옮기는 부분이 가장 핵심적인 기능이었다. 모든 데이터를 한 칸 뒤로 옮기게 되면 현재 데이터보다 큰 데이터가 있던 자리에 현재 데이터를 삽입(insert)하는 방식으로 구현하면 끝나는 문제였다. 정답 코드 import j..

[백준][BOJ 2502] - 떡 먹는 호랑이

2023. 10. 2. 19:07 Algorithm/DP

문제 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 문제 접근 점화식이 이미 문제에서 주어져 있다. 점화식은 다음과 같이 주어진다. $A_k = A_{k - 1} + A_{k - 2}$ 문제에서 요구하는 답은 특정 시점과 떡의 개수가 주어질 때 초기값을 구하라는 것이다. 이때 문제 조건에서 항상 $A_1 \leq A_2$를 만족한다는 것을 유의하라 $A_1$은 특정 시점에 주어진 떡의 개수를 $K$라고 할 때 $K/2$까지 될 수 있..

[백준][BOJ 1969] - DNA

2023. 10. 2. 14:29 Algorithm/BruteForce

문제 https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 문제 접근 주어진 DNA입력들에 대해 Hamming Distance가 최소가 되는 DNA를 우리가 만들어야 한다. Hamming Distance의 경우 우리가 만든 DNA를 $s$라고 할 때 이 $s$의 각 부분과 주어진 DNA들의 각 부분을 비교해 다른 글자의 개수로 정의된다. 따라서 Hamming Distance를 최소화 시키기 위해서는 주어진..

[백준][BOJ 4134] - 다음 소수

2023. 10. 2. 13:06 Algorithm/BruteForce

문제 https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net 문제 접근 $N$보다 크거나 같은 소수 중 가장 작은 소수를 구하는 문제 $N$이 최대 4억까지 주어질 수 있고, 어디까지 진행되는지도 알 수 없기 때문에 수 자체는 넉넉하게 long으로 잡았다. 생각해보면 그냥 int도 21억까지 지원하기 때문에 int로 해도 무방할 것 같기도 하다 이후에는 N을 1씩 증가시키며 소수인지를 판별했다. 소수를 판별하는 방식은 여러가지가 있지만 나는 루트를 적용하여 범위를 줄이는 방식을 사용하였다. 정답 코드 import java.io.Buf..

티스토리툴바