본문 바로가기

전체 글275

[백준] 11568번 - 민균이의 계략 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 민균이의 계략 https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 www.acmicpc.net 11053번 - 가장 긴 증가하는 부분 수열 문제와 같은 문제입니다. 현재 idx에서 만들 수 있는 가장 긴 부분 수열의 길이를 memoization하여 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/11568_%EB%AF%BC%EA%B.. 2022. 3. 11.
[백준] 10159번 - 저울 (C++) 문제 및 풀이 문제) 백준 - 플루이드 와샬 - 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net N이 최대 100이므로 플루이드 와샬(O(N^3))로 충분히 해결할 수 있습니다. 대소 관계가 중요하므로 그 관계에 따라 1 또는 -1로 표현합니다. 만약 같은 t, i, j에 대하여 (i, t)와 (t, j)의 관계가 같으면 (i, j)의 관계로 표현합니다. C++ 소스코드) 2022. 3. 11.
[백준] 21920번 - 서로소 평균 (C++) 문제 및 풀이 문제) 백준 - 수학 - 서로소 평균 https://www.acmicpc.net/problem/21920 21920번: 서로소 평균 첫 번째 줄에 입력될 수들의 개수 $N$이 주어진다. $(2 \le N \le 500,000)$ 두 번째 줄에는 수열 $A$를 이루는 자연수 $A_{i}$ 가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 수열 $A$에 $X$와 서로 www.acmicpc.net 서로소를 만족하는 수들의 평균을 구하는 문제였습니다. 유클리드 호제법을 통해 서로소를 판별합니다. C++ 소스코드) 2022. 3. 11.
[백준] 13164번 - 행복 유치원 (C++) 문제 및 풀이 문제) 백준 - 그리디 - 행복 유치원 https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 인접한 학생들의 키의 차이를 저장하여 오름차순으로 정렬합니다. 그 중 제일 작은 N - K 개를 더하면 해결할 수 있습니다. C++ 소스코드) 2022. 3. 11.
[백준] 14863번 - 서울에서 경산까지 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 서울에서 경산까지 https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net 도보로 이동하거나 자전거를 이용하는 방법을 택하여 제한 시간 이내에 얻을 수 있는 최대 모금액을 구하는 문제였습니다. 동적 계획법을 통해 해당 구간과 제한 시간을 memoization 하여 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_So.. 2022. 3. 8.
[백준] 9024번 - 두 수의 합 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 두 수의 합 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 주어진 숫자 배열에서 두 개의 수를 뽑았을 때, K에 가장 가까운 쌍의 개수를 찾는 문제였습니다. N이 최대 100만이기에 O(NlogN)의 시간 복잡도로 해결할 수 있어야 합니다. 정렬 + 이분 탐색으로 K에 가장 가까운 수의 합을 탐색하며 갱신하면 해결할 수 있습니다. C++ 소스코드) 2022. 3. 7.
[백준] 21940번 - 가운데에서 만나기 (C++) 문제 및 풀이 문제) 백준 - 플루이드 와샬 - 가운데에서 만나기 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net N이 최대 200이기 때문에 플루이드 와샬로도 충분히 해결할 수 있습니다. C++ 소스코드) 2022. 3. 6.
[프로그래머스] SQL 고득점 Kit - Null 처리하기 (MySQL) 문제 및 풀이 문제) 프로그래머스 - Null - Null 처리하기 https://programmers.co.kr/learn/courses/30/lessons/59410 코딩테스트 연습 - NULL 처리하기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr If 조건문을 통해 Name 칼럼에 Null이 존재할 경우 No name을 표시하게 합니다. 풀이) 2022. 3. 4.
[백준] 1251번 - 단어 나누기 (Python) 문제 및 풀이 문제) 백준 - 구현 - 단어 나누기 https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net Python 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/1251_%EB%8B%A8%EC%96%B4%EB%82%98%EB%88%84%EA%B8%B0.py GitHub - Chocochip101/BOJ_Solution: BOJ Solutions BOJ Solutio.. 2022. 3. 4.
[백준] 14430번 - 자원 캐기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 자원 캐기 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 현재 칸에서 오른쪽, 아래쪽으로 갔을 때 얻을 수 있는 최대 광석 수를 동적 계획법을 통해 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/14430_%EC%9E%90%EC%9B%90%EC%BA%90%EA%B8%B0.c.. 2022. 3. 4.
[백준] 9996번 - 한국이 그리울 땐 서버에 접속하지 (Python) 문제 및 풀이 문제) 백준 - 문자열 - 한국이 그리울 땐 서버에 접속하지 https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net Python 소스코드) 2022. 3. 3.
[백준] 22943번 - 수 (Python) 문제 및 풀이 문제) 백준 - 수학 - 수 https://www.acmicpc.net/problem/22943 22943번: 수 0부터 9까지 $K$가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다. 서로 다른 www.acmicpc.net 소수 판별을 이용해 다양한 조건을 만족하는 수의 개수를 찾는 문제였습니다. 0부터 9까지 K개로 이루어진 수를 찾기 위해 itertools에 내장된 permutation을 활용했습니다. 만약 뽑힌 수의 앞 수가 0일 경우 만족하지 않으므로 무시합니다. 그 후, 에라토스테네스의 체를 활용한 소수 판별을 바탕으로 문제에 주어진 조건대로 확인합니다. Python 소.. 2022. 3. 2.
[백준] 18405번 - 경제적 전염 (C++) 문제 및 풀이 문제) 백준 - BFS - 경제적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net BFS를 통해 바이러스를 전염시킵니다. 매 초마다 전염을 하는데 1번부터 K번 순서대로 전염시켜야 되기 때문에 각 초마다 q_size의 좌표를 벡터에 넣어 정렬을 진행합니다. 정렬을 했다면 BFS를 진행하여 바이러스를 퍼트립니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BO.. 2022. 3. 2.
[백준] 17609번 - 회문 (C++) 문제 및 풀이 문제) 백준 - 구현 - 회문 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 글자의 앞과 뒤를 비교하여 회문 여부를 판단합니다. 만약 앞(l), 뒤(r) 글자가 같지 않으면 회문이 아니므로 유사 회문 판단을 진행합니다. 유사 회문 판단은 l+1번째 글자부터 r번째 글자의 회문 여부와 l 번째 글자부터 r - 1번째 글자의 회문 여부를 판단합니다. 전자는 l번째 글자를 제외할 경우의 유사 회문 판단이고 후자는 r번째 글자를 제외할 경우의 유사회문 판단입니다. C++ 소스코드.. 2022. 3. 1.
[백준] 20162번 - 간식 파티 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 간식 파티 https://www.acmicpc.net/problem/20162 20162번: 간식 파티 서울이는 입맛이 까다로운 고양이다. 입맛이 까다로운 서울이는 전에 먹었던 간식보다 더 맛있는 간식만 먹는다. 서울이는 간식의 평점이 높을수록 맛있다고 느낀다. 집사는 서울이에게 N 일 www.acmicpc.net 가장 합이 큰 증가하는 부분 수열을 구하는 문제였습니다. 워낙 잘 알려진 동적 계획법 문제라서 비슷한 유형을 풀어보셨다면 접근 방법은 어렵지 않게 찾으실 수 있습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/20162_%EA%B0%84%EC%8B%9D.. 2022. 3. 1.
반응형

티스토리툴바