티스토리

개발저장소

검색하기

블로그 홈

개발저장소

develrepo.tistory.com/m

개발소 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

[백준 실버 4] 1018번: 체스판 다시 칠하기 문제https://www.acmicpc.net/problem/1018 풀이체스판은 흰색과 검은색이 번갈아가면서 칠해져있어야 한다. 인접한 칸이 같은 색이면 안된다.N X M 크기의 보드를 8 X 8 사이즈로 잘라 체스판을 만드려고 한다.이렇게 잘라서 만든 체스판은 색이 잘못된 경우 새로 칠하려고 한다.자를 수 있는 체스판의 경우 중에서, 새로 칠하는 횟수가 가장 적은 경우의 최소 개수를 출력한다.문제를 풀기 위해선 두 가지 포인트를 해결해야 한다.첫째, N X M 사이즈의 보드를 어떻게 체스판 사이즈로 나눌 것인가.둘째, 새로 칠하는 횟수를 어떻게 구해야 할 것인가. 첫째는 만들어질 수 있는 체스판의 경우의 수는 (N - 7) * (M - 7)이 된다.(0,0)을 첫 번째 칸으로 가지는 체스판부터, (.. 공감수 0 댓글수 0 2024. 6. 17.
[백준 실버 2] 18111번: 마인크래프트 문제https://www.acmicpc.net/problem/18111 풀이마인크래프트의 땅 고르기 작업을 한다. 땅 고르기란, 범위 내의 블록 높이를 같은 상태로 만드는 작업이다.땅 고르기 범위는 N X M 크기이다.하나의 블록을 캐면 2초가 걸리고, 그 블록이 인벤토리에 저장된다.하나의 블록을 설치하면 1초가 걸리고, 인벤토리에서 꺼낸 블록을 사용한다. 인벤토리에 블록이 없다면 설치할 수 없다.땅의 높이는 최소 0, 최대 256이다. 블록은 최대 64,000,000개가 주어질 수 있고, 맵의 크기는 최대 500 X 500이다.맵 전체의 땅을 고르는데 걸리는 최소 시간을 구해야 한다. 만약 시간이 같다면 땅의 높이가 더 높은 경우를 출력한다. 주어진 맵의 크기가 크지 않아 브루트포스 알고리즘을 사용.. 공감수 0 댓글수 0 2024. 5. 23.
[백준 골드 2] 1377번: 버블 소트 문제 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 문제의 코드 버블 정렬을 C++로 구현한 알고리즘이다. 버블 정렬에서 swap이 한 번도 일어나지 않은 루프의 위치를 알아내는 코드이다. 버블 정렬에서 swap이 일어나지 않은 루프가 존재한다는 것은 정렬이 끝났다는 뜻이다. 그러므로 루프를 알아낸 즉시 반복문을 종료하는 것이 좋다. 정렬해야 하는 배열의 크기는 최대 500,000인 자연수이고, 요소의 크기는 최대.. 공감수 0 댓글수 0 2024. 2. 1.
[백준 실버 1] 11286번: 절댓값 힙 문제https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0www.acmicpc.net 풀이0이 아닌 정수 x를 배열에 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고 제거한다.절댓값이 가장 작은 값이 여러 개라면, 그중에 가장 작은 수를 출력하고 제거한다.0이 아닌 수가 주어지면 배열에 입력하고, 0이 주어진다면 위 규칙에 맞게 수를 출력하면 된다.연산의 개수는 1보다 크고 100,000보다 작다.입력되는 정수 x는 -2^31보다 크고 2^31보다 작다.출력.. 공감수 0 댓글수 0 2024. 1. 31.
[백준 골드 5] 13023번: ABCDE 문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 N명의 사람이 0부터 N-1번까지 번호가 매겨져 있고, 이 중 일부 사람들은 친구이다. 이때, A와 B가 친구이고, B와 C가 친구이고, C와 D가 친구이고, D와 E가 친구가 되는 친구 관계 A, B, C, D, E가 존재한다면 1, 아니면 0을 출력한다. 문제 이해가 잘 안됐지만, A -> B -> C -> D -> E 처럼 일렬로 나열할 수 있는 그래프가 존재하는지 판별하는 것이 핵심이었다. 재귀가 몇 번 일어났는지 판별하기 위해서 depth를 사용해서 5번까지 일어난다면 1을 출력하도.. 공감수 0 댓글수 0 2024. 1. 23.
[백준 골드 5] 2023번: 신기한 소수 문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 N자리 숫자 중 왼쪽부터 1자리, 2자리, 3자리, ... N자리까지 모든 수가 소수가 되는 숫자를 모두 출력한다. ex) 7331 => 7, 73, 733, 7331 모두 소수이다. N은 1보다 크고 8보다 작다. 출력되는 소수는 오름차순으로 정렬한다. 1자리씩 점점 숫자를 늘려가며 소수인 경우만 가지를 뻗는 백트래킹 문제이다. 1자리는 2, 3, 5, 7만 가능하기 때문에.. 공감수 0 댓글수 0 2024. 1. 23.
[백준 골드 4] 17298번: 오큰수 문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 크기가 N인 수열 A가 있을 때, 각 원소 Ai에 대하여 Ai보다 오른쪽에 있으면서 큰 수 중에서 가장 왼쪽에 있는 수를 오큰수라고 한다. 수열 A가 있을 때, 각 원소들의 오큰수를 구해야 한다. 오큰수가 없다면 -1을 출력한다. 수열 A의 길이와 각 원소의 크기는 둘 다 1 이상 1,000,000 이하이다. 즉, 다중 for문을 사용한다면 무조건 시간 초과가 일어난다. 스택의 원리를 이해하고 이.. 공감수 0 댓글수 0 2024. 1. 19.
[백준 실버 4] 2567번: 색종이 - 2 문제 https://www.acmicpc.net/problem/2567 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 풀이 가로, 세로 길이가 100인 도화지 위에 길이가 10인 정사각형 색종이를 도화지와 평행하게 붙인다. 이러한 방식으로 색종이를 여러장 붙였을 때, 둘레의 길이를 구한다. 중간에 구멍이 뚫린 모양도 둘레에 포함한다. 수학적인 방법으로 접근하려고 했지만 중간에 둘레가 생기는 경우를 계산하기 위해서 그리디한 방법으로 접근하였다. 도화지를 크기가 100 X 100인 2차원 배열로 생각한다. 이때 배.. 공감수 0 댓글수 0 2024. 1. 14.
[백준 플레티넘 5] 11003번: 최솟값 찾기 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 N개의 수열과 L이 주어진다. 수열의 연속된 숫자 L개 중에서 최솟값을 D라고 할 때, 최솟값들을 구해야 한다. 예를 들어 5개의 수열 1, 2, 3, 4, 5와 L = 3가 주어질 때, (1, 2, 3), (2, 3, 4), (3, 4, 5) 중에 최솟값을 구해서 출력해야 한다. ( 1 2 3 이런식으로) N과 L의 범위가 1 이상 5,000,000 이.. 공감수 0 댓글수 0 2024. 1. 14.
[백준 실버 2] 12891번: DNA 비밀번호 문제 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 풀이 문자열에 ‘A’, ‘C’, ‘G’, ‘T' 만 등장하는 문자열을 DNA 문자열이라고 한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 길이 S의 임의의 DNA 문자열을 만들고, 이 DNA 문자열의 길이가 P인 부분문자열을 비밀번호로 사용하려고 한다. "AAAA" 같은 취약한 비밀번호가 만들어 질 수도 있기 때문에 문자의 개.. 공감수 0 댓글수 0 2023. 12. 8.
[백준 골드 4] 1253번: 좋다 문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 N개의 수가 주어질 때, 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 "좋다"라고 한다. 주어진 N개의 수 중 좋은 수의 개수를 출력해야 한다. 같은 값의 수가 주어질 수도 있지만 서로 다른 수로 취급한다. N은 1에서 2000 사이이고, 주어지는 수는 |Ai| ≤ 1,000,000,000 의 정수이다. 투포인터를 사용해 N개의 수를 탐색하는 방법으로 풀었다. 이때, 수의 범위가 크므로 Long형 배열로 입력.. 공감수 0 댓글수 0 2023. 12. 7.
[백준 골드 3] 10986번: 나머지 합 문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 N개의 수열이 주어졌을 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구한다. Ai + ... + Aj 가 M으로 나누어 떨어지는 순서쌍 (i, j)를 구해야 한다. Si % M과 Sj % M의 값이 같다면 (Si - Sj) % M = 0이 되는 성질을 이용해야 한다. 누적 합을 가장한 모듈러 산술에 대한 문제이다. .. 공감수 1 댓글수 0 2023. 11. 28.
[백준 실버 2] 1699번: 제곱수의 합 문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 자연수 N을 제곱수의 합으로 표현해야 한다. 예를 들어 5 = 1^2 + 2^2, 즉 2개의 항으로 나타낼 수 있다. 이때 N을 제곱수의 합으로 나타낼 때, 최소 항의 개수를 구한다. 모든 자연수 N의 최대 항의 개수는 N개이다. 1^2의 합으로 표현할 수 있기 때문이다. 제곱수 N의 최소 항의 개수는 무조건 1개이다. 제곱해서 N이 되는 수 하나.. 공감수 0 댓글수 0 2023. 11. 21.
[백준 실버 5] 2628번: 종이자르기 문제 https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 풀이 직사각형 모양의 모눈종이가 있다. 1cm마다 점선으로 표시되어 있고, 각 점선에는 순서대로 번호가 부여되어 있다. 직사각형의 가로와 세로의 길이, 그리고 잘라야하는 점선이 주어질 때, 가장 큰 종이 조각의 넓이를 구해야 한다. 가로로 잘라야 하는 점선과 세로로 잘라야 하는 점선을 각각 ArrayList로 입력 받은 다음 순서대로 정렬해서 문제를 해결하였다. 길이를 구해야하므로 처음과 끝도 A.. 공감수 0 댓글수 0 2023. 11. 21.
[백준 골드 4] 1806번: 부분합 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 길이 N의 수열에서 연속된 수들의 부분합 중에 S 이상을 만족하는 것 중, 가장 짧은 경우의 길이를 구한다. N의 범위는 10 이상 100,000 이하이고 S의 범위는 0 초과 100,000,000 이하이다. 입력되는 N이 많기 때문에 이중 for문을 사용한 풀이는 무조건 시간 초과가 일어난다. 투포인터를 사용하면 일차원 배열 위에서 인덱스가 움직이는 방식이기 때문에, 최.. 공감수 0 댓글수 0 2023. 11. 8.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.