Algorithm/BeakJoon (24) 썸네일형 리스트형 [BaekJoon 13144] List of Unique Numbers 안녕하세요. 오늘은 백준 13144 List of Unique Numbers라는 문제를 풀어보도록 하겠습니다. 해당 문제는 아래의 링크에서 확인하실 수 있습니다. https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 문제를 살펴보면, 어떠한 수열이 주어지고, 해당 수열에서 같은 숫자가 없는 수열의 개수를 출력하는 문제입니다. 우선 이중 포문으로 구현을 하게 되면 O(N^2)의 시간 복잡도를 갖게 됩니다. N > n; vector v(n); for(int i.. [BeakJoon 1285] 동전 뒤집기 안녕하세요. 오늘은 백준 1285번 동전 뒤집기라는 문제를 풀어보겠습니다. 문제는 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 위 링크에서 보실 수 있습니다. 문제를 요약하면 다음과 같습니다. 초기 상태가 주어졌을 때, 행 혹은 열 단위로 뒤집기를 수행합니다. 그 결과 뒷면이 보이는 수가 가장 적은 경우를 찾는 문제입니다. 저는 처음 이 문제를 보았을 때 인풋의 범위를 보고 당연히 완전 탐색을 해야지라고 생각을 했는데, 문제는 종료 조건.. [BaekJoon 14319] 종이조각 안녕하세요. 오늘은 백준 14319번 종이조각이라는 문제를 풀어보도록 하겠습니다. 해당 문제는 아래의 링크에서 확인하실 수 있습니다. https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 우선 문제를 살펴보면 인풋의 범위가 매우 작습니다. 4x4까지이기 때문에 완전 탐색으로 충분히 풀리는 문제입니다. 또한 이 문제가 완전탐색에 적합한 이유는 가로 방향과 세로 방향밖에 없습니다. 즉 저희가 흔히 생각하는 이런 모양이나 이런 모양은 나오지 않습니다. .. [BaekJoon 3015] 오아시스 재결합 안녕하세요. 오늘은 백준 3015번 오아시스 재결합이라는 문제를 알아보겠습니다. 해당 문제는 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 아래의 링크에서 확인하실 수 있습니다. 문제를 보시면, 시간제한이 1초이고, N의 범위가 500000입니다. 따라서 위 문제는 O(N^2)의 알고리즘으로 해결할 수 없으며, 기본적으로 현재를 기준으로 과거의 값을 돌아보는 형식의 로직이기 때문에 Stack을 사용하는 문제임을 추측할 .. [BaekJoon 15684] 사다리 조작 안녕하세요. 이번 포스팅에서는 백준 15684번 사다리 조작이라는 문제에 대해 포스팅을 해보겠습니다. 해당 문제는 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 이 링크에서 참고하실 수 있습니다. (문제가 너무 길어요 ㅜㅜ) 그렇다면 문제를 읽으셨다고 가정하고, 이 문제를 조금 단계별로 구조화해보겠습니다. 1. 사다리를 배열에 적절히 매핑하기 2. 경우의 수 구하기 3. 모든 경우의 수에 대하여 탐색 1. 사다리를 배열에 적절히 매핑하기 사.. [BaekJoon 2852] NBA 농구 안녕하세요. 오늘은 백준 2852번 NBA 농구라는 문제를 가져왔습니다. 문자열, 구현 쪽 문제입니다. 문제는 다음과 같습니다. Team 1이 골을 넣었는데, 만약에 Team 2가 다음 골을 넣었으면 Team 1이 이기고 있던 시간에 Team 2가 방금 골 넣은 시간 - Team 1 이 마지막으로 넣은 시간을 더해주면서 문제를 해결하면 됩니다. 간단하게 제가 푼 소스코드를 먼저 살펴보겠습니다. #include using namespace std; int n, team; int score[3]; string winning[3]={"00:00", "00:00", "00:00"}; string last_goal, inp; string calc(string cur, string last) { int cur_h=.. [BaekJoon 4659] 비밀번호 발음하기 오늘은 오랜만에 재미있는 문제가 있어서 한번 가져와 보았습니다. (코딩 테스트 준비 재밌....) 바로 백준 4659 비밀번호 발음하기라는 문제입니다. 저번 학기에 제가 본 코딩 테스트 결과를 보았을 때 확실히 제가 문자열 부분이 조금 약한 듯해서 관련 문제를 여러 개 풀어보고 있습니다. 여담은 여기까지 하고 문제를 읽어볼게요! 해당 문제는 이 링크에서 확인하실 수 있습니다. 솔직히 분류는 문자열이긴 한데, 단순 구현 문제와 비슷합니다. 제가 문제를 보고 떠오른 생각은 다음과 같습니다. 1. c++ string.find() 메소드를 확인해서 a, e, i, o, u 가 있는지 없는지 확인 2. 1에서 하나라도 존재한다면, 이제 for loop를 돌며 연속하는 3개의 자음이 있는지, 3개의 모음이 있는지 .. [BackJoon4375] 1 안녕하세요. 이번 포스팅에서는 BackJoon 4375번 문제인 1에 대한 해설을 진행해 보겠습니다. 문제는 다음과 같이 이루어져 있습니다. 우선 n이 2와 5로 나누어 떨어지지 않는다고 명시되어있습니다. 즉 주어지는 n은 10으로도 나누어 떨어지지 않습니다. 그러면 저희는 1부터 1 , 11, 111, 1111,... 11111111 등등 1로 이루어진 수를 계속 테스트하며 n과 나누어 볼 수 있습니다. unsigned long long m = 1; ... m = m * 10 + 1; 위와 같이 10을 곱하고 1을 더해주는 과정을 계속 진행해주면 1로만 이루어진 수를 작은 수부터 차례로 구해나갈 수 있습니다. 하지만 문제가 뭐냐면, 위 방식으로만 코드를 작성하게 되면 시간 초과가 나오게 됩니다. 그 이.. 이전 1 2 3 다음
