성장하는 코딩블로그

프로그래밍 언어에 익숙해지고 싶어서... 코딩테스트를 준비하기 위해... 등등 여러 가지 이유로 백준 알고리즘에서 문제를 풉니다. 오늘은 효율적으로 백준 알고리즘 문제를 선정하고 푸는 방법을 소개하고자 합니다. 1. 백준 단계별로 풀어보기 백준 알고리즘에서 제공하는 문제집입니다. 유형별로 정리가 잘 되어있으며 백준을 처음 시작한다면 꼭 풀어보시기 바랍니다. 1~15단계가 언어를 익히기 위한 단계이고 16단계부터는 자료구조, 알고리즘을 배우는 단계입니다. 모든 문제를 다 풀지는 못하더라도 15단계까지는 풀어봅시다. 2. Solved.ac CLASS 문제 백준 문제들에 티어로 난이도를 매겨주는 사이트인 Solved.ac에서 제공하는 문제모음입니다. 각각의 클래스마다 컨셉이 있으며 클래스 1은 기본 문제 클래..

백준 알고리즘에는 여러 티어가 있습니다. 브론즈, 실버, 골드, 플레티넘, 다이아몬드, 루비, 마스터... 오늘은 백준에서 티어 분포가 어떻게 이루어져 있는지 확인해 봅시다. 24년 3월 19일 기준입니다. 일단 Solved.ac에 연동되어 있는 사람 수는 대략 147546명 정도입니다. 실버 5를 달성한 인원은 91128명입니다. 상위 70 %입니다. 실버를 달성하기 위해서는 200점이 필요합니다. 골드 5를 달성한 인원은 40615명입니다. 상위 31.13 %입니다. 골드를 달성하기 위해서는 800점이 필요합니다. 플레 5를 달성한 인원은 7627명입니다. 상위 5.86%입니다. 플레티넘을 달성하기 위해서는 1600점이 필요합니다. 다이아 5를 달성한 인원은 1099명입니다. 상위 0.85 %입니다...

오늘은 백준 11726번 문제인 2×n 타일링을 풀어보겠습니다. 이러한 타일링 문제는 다이나믹 프로그래밍(DP)을 응용할 수 있는 좋은 기본 문제로 뽑히고 있습니다. 아래에서 문제를 한 번 확인해 봅시다. 문제 링크: 11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ..

오늘은 백준 1463 : 1로 만들기를 풀어보려고 합니다. 실버 3 난이도로 다이나믹 프로그래밍을 연습하는 좋은 문제인데요, 한번 풀어봅시다. 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 해설 문제를 처음 보면 감이 안 잡힐 수도 있습니다. "12부터 시작한다면 12에서 3으로 나누기, 2로 나누기, 1 빼기 중에 어..

오늘은 백준 10989 수 정렬하기 3문제에 대해 알아보는 시간을 가지겠습니다. 문제를 풀면 분명 맞다고 생각되는데 계속 시간초과나 메모리초과가 나오기에 당황하셨을 겁니다. 오늘은 왜 틀리고 어떻게 해야 하는지 C언어에서 알아보겠습니다. 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 해설 문제 조건을 보면 N은 1~ 1천만 까지 주어집니다. 그리고 메모리 제한은 8mb입니다. 만약 N만큼 배열을 선언하여 수를 입력받으..

백준 1152 : 단어의 개수(C, C++) 문제 링크 : 1152번: 단어의 개수 (acmicpc.net) 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net C언어와 C++ 두 가지 모두 해설이 준비되어 있습니다. 문제 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1..

백준 2884 : 알림 시계(C, C++) 문제 링크 : 2884번: 알람 시계 (acmicpc.net) 2884번: 알람 시계 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, www.acmicpc.net 문제 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해 보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다. 이런 상근이를 불쌍하게 보던 창영이는 자신이 사용하는 방법을 추천해 주었다. 바로 "45분 일찍 알람 설정하기"이다...

문제 링크 : https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 문제 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다. 버튼을 K번 눌렀을 ..

문제 링크 : 9655번: 돌 게임 (acmicpc.net) 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 해설 구하는 방법은 크게 두가지가 있습니다. 1. 직접..

문제 링크 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인..