백준12

• 백준 11047번 동전0 C++ 풀이 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 현재 가지고 있는 돈을 최소의 지폐로 환산하면 몇 장인지 구하는 문제로, 그리디 알고리즘을 사용할 수 있는 문제이다. 문제의 포인트 문제를 보고 구현할 수 있는가? 최적의 방법을 찾을 수 있는가? 코드 #inc.. 코딩테스트 2022. 12. 13.

• 백준 2178번 미로 탐색 C++ 풀이 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. bfs를 이용하여 왼쪽 위에서 오른쪽 아래까지 이동하기 위해 필요한 이동의 개수를 측정하는 문제이다. 문제의 포인트 bfs를 떠올릴 수 있고, 구현할 수 있는가? 코드 #include #include #.. 코딩테스트 2022. 12. 9.

• 백준 2442번 별 찍기 - 5 C++ 풀이 https://www.acmicpc.net/problem/2442 2442번: 별 찍기 - 5 첫째 줄에는 별 1개, 둘째 줄에는 별 3개, ..., N번째 줄에는 별 2×N-1개를 찍는 문제 별은 가운데를 기준으로 대칭이어야 한다. www.acmicpc.net 첫째 줄에는 별 1개, 둘째 줄에는 별 3개, ..., N번째 줄에는 별 2×N-1개를 찍는 문제 별은 가운데를 기준으로 대칭이어야 한다. 피라미드 출력 문제이다. 이 문제를 풀 때는 공백도 또하나의 문자로 생각하며 줄간의 규칙을 찾아보도록 하자. 헷갈린다면 공백을 +와 같은 문자로 치환해 풀고 바꾸는 것도 좋다. 코드 #include using namespace std; int main() { int n; cin >> n; for (int i .. 코딩테스트 2022. 12. 9.

• 백준 2556번 별 찍기 - 14 C++ 풀이 https://www.acmicpc.net/problem/2556 2556번: 별 찍기 - 14 지금까지 안 나온 별 찍기가 뭐가 있는지 생각해본 후, 별을 적절히 찍으세요. www.acmicpc.net 지금까지 안 나온 별 찍기가 뭐가 있는지 생각해본 후, 별을 적절히 찍으세요. 보자마자 응? 소리 나오는 문제이다. 어떻게 찍어야 할지 안 알려주다니... 이 문제는 사실 정사각형을 찍는 문제로, n이 입력되면 n*n의 정사각형을 출력하면 된다. 코드 #include using namespace std; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout 코딩테스트 2022. 12. 9.

• 백준 18405번 경쟁적 전염 C++ 풀이 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다. 문제 설명이 아주 잘 되어있는 문제로, 이 것을 어떻게,무엇으로 구현할지가 관건인 문제이다. 문제의 포.. 코딩테스트 2022. 12. 1.

• 백준 12015번 가장 긴 증가하는 부분 수열 2 C++풀이 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 최장 증가 부분 수열(LIS)를 구하는 문제이다. {10, 20, 10, 30, 20, 50}의 LIS는 10과 20을 뺀 {1.. 코딩테스트 2022. 12. 1.

• 백준 1027번 게임 C++풀이 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.(중략) X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오. 형택이의 승률이 변하는 게임의 횟수를 구하는 문제이다. 문제의 포인트 문제를 파악하고,.. 코딩테스트 2022. 11. 29.

• 백준 5430번 AC C++ 풀이 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 주말에 할 게 없다고 새로운 언어를 만들어 버린 선영이를 위해 초기값과 수행할 함수가 주어졌을 때 언어의 연산을 거친 최종 결과를 구하는 프로그램이다. 문제 설명 이 언어의 함수는 R, D가 있는데, R은 문자열을 뒤집는 함수, D는 문자열의 첫 번째 수를 버리는 함수이다. 문.. 코딩테스트 2022. 11. 22.

• 

  백준 10799번 쇠막대기 C++ 풀이 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘리고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다. 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오. 쇠막대기 문제는 괄호를 쇠막대기를 겹쳐놓은 모양으로 판단, 쇠막대기를 레.. 코딩테스트 2022. 11. 21.

• 백준 1620번 나는야 포켓몬 마스터 이다솜 C++ 풀이 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네. 이 문제는 들어오는 포켓몬의 이름을 저장시키고, 추후 이름이나 번호.. 코딩테스트 2022. 11. 11.

• 백준 2504 괄호의 값 C++ 풀이 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다. 여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 이 문제는 stack 자료구조를.. 코딩테스트 2022. 11. 9.

• 백준 1302 베스트셀러 C++ 풀이 https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다. 오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오. 이 문제는 컨테이너인 map을 사용하면 아주 빠르고 간편하게 풀 수 있.. 코딩테스트 2022. 11. 9.