Algorithm

    [1992번] 쿼드트리
    Algorithm/백준 문제 풀이

    [1992번] 쿼드트리

    백준 1992번: 쿼드트리 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다. www.acmicpc.net 분할 정복(Divide-&-Conquer)의 대표적인 문제 중 하나입니다. 이전에 포스팅했던 [2630번] 색종이 만들기와 같은 알고리즘을 씁니다. 다만 이번에는 개수를 세는 것이 아니라 4등분 후 해당 면이 모두 같은 숫자로 채워져 있다면 그 숫자가 그 분면을 대표하는 숫자라 할 수 있겠죠. 그래서 그 숫자로 압축을 하는 것입니다. 재귀 함수를 쓰고 출력 형식만 ..

    [2630번] 색종이 만들기
    Algorithm/백준 문제 풀이

    [2630번] 색종이 만들기

    백준 2630번: 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net 가장 기본적인 Divide-&-Conquer(분할 정복) 문제 중 하나라고 할 수 있습니다. 한 변의 길이가 $2^n$인 정사각형을 입력받은 후에 정확히 4등분을 해서 온전히 0 또는 1로 이루어진 색종이를 얻습니다. 그리고 0으로만 이루어진 색종이와 1로만 이루어진 색종이의 개수를 각각 세기만 하..

    [1012번] 유기농 배추
    Algorithm/백준 문제 풀이

    [1012번] 유기농 배추

    백준 1012번: 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 이번 문제는 Graph를 다루는 문제입니다. 예전에 이와 매우 유사한 문제를 만난 적이 있죠? [2667번] 단지번호붙이기 이번에도 BFS를 이용해서 1로 이루어진 구역..

    [1712번] 손익분기점
    Algorithm/백준 문제 풀이

    [1712번] 손익분기점

    백준 1712번: 손익분기점 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 www.acmicpc.net 단순히 계산하는 문제입니다. 조건에만 잘 맞춰서 결과를 반환하면 됩니다. [소스 보기]

    [2798번] 블랙잭
    Algorithm/백준 문제 풀이

    [2798번] 블랙잭

    백준 2798번: 블랙잭 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 기존에 저희가 알고 있던 블랙잭이라는 게임의 조건을 조금 바꾼 문제라고 할 수 있습니다. 처음에 저는 $N$개의 카드 중에서 3개를 뽑아야 한다는 조건 때문에 조합의 개념으로 생각..

    [4447번] 좋은놈 나쁜놈
    Algorithm/백준 문제 풀이

    [4447번] 좋은놈 나쁜놈

    백준 4447번: 좋은놈 나쁜놈 4447번: 좋은놈 나쁜놈 문제 비키니시티에 초능력을 가진 수퍼 히어로들로 바글바글하다. 스폰지밥과 패트릭은 주어진 문자열로 좋은놈과 나쁜놈을 골라내려 한다. 스폰지밥: 우와, 문자열에서 강한 힘이 느껴지는데! 근데 좋은 놈인지 나쁜 놈인지 알 길이 없네. 패트릭: 아니, 쉬운 것 같은데? 그냥 이름에서 'g'의 개수와 'b'의 개수만 세면 돼. 'g'가 더 많으면 좋은 놈. 'b'가 더 많으면 나쁜 놈. 위대하신 히어로 중의 히어로 'Algorithm Crunching Man' www.acmicpc.net 단순히 한 줄 string을 입력받은 뒤 각 문자에 대해 g(G), b(B)의 개수를 셉니다. 이후 그 개수를 비교해 출력만 해주면 되는 간단한 문제입니다. [소스 보기]

    [4153번] 직각삼각형
    Algorithm/백준 문제 풀이

    [4153번] 직각삼각형

    백준 4153번: 직각삼각형 4153번: 직각삼각형 문제 과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오. 입력 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. 출력 각 입력에 대해 직각 삼각형이 맞다면 "right", 아니라면 "wrong"을 출력한다. 예제 입력 1 복사 6 8 www.acmicpc.net 피타고라스의 직각삼각형 공식입니다. c^2 = a^2 + b^2 ( c >= a, b / a + b >= c ). 다들 아시죠?ㅎㅎ [소스 보기]

    [1009번] 분산처리
    Algorithm/백준 문제 풀이

    [1009번] 분산처리

    백준 1009번: 분산처리 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 단순히 자연수의 끝자리의 반복 패턴에 대해서만 알면 됩니다. 단, 주의해야 할 점은 10번 컴퓨터가 존재하므로 끝자리가 특수한 경우 출력을 잘 조정해주어야 한다는 점입니다. 그것만 주의하면 그리 어려운 문제는 아니라는 것을 알 수 있습니다. [소스 보기]

    [2667번] 단지번호붙이기
    Algorithm/백준 문제 풀이

    [2667번] 단지번호붙이기

    백준 2667번: 단지번호붙이기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net DFS 혹은 BFS를 이용해 그래프를 탐색하는 문제입니다. 저는 좀 더 효율이 좋다고 알려진 BFS로 접근하였습니다. main에서 BFS() 함수를 부를 때마다 단지를 증가시키고, 함수 내에서는 그..

티스토리툴바