Sa-gom Blog

No bottom

[Algorithm] 백준 1932번 숫자 삼각형

백준 온라인 저지 1932 번 숫자 삼각형 문제 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 ...

Posted by Sa-gom Blog on April 18, 2018

[Algorithm] 백준 1463번 1로 만들기

백준 온라인 저지 1463 번 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출...

Posted by Sa-gom Blog on April 18, 2018

[Algorithm] 백준 1149번 RGB거리

백준 온라인 저지 1149 번 RGB거리 문제 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용...

Posted by Sa-gom Blog on April 17, 2018

[Algorithm] 백준 3190번 뱀

백준 온라인 저지 3190 뱀 문제 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이 때, 톱니바퀴를 총 K번 회전...

Posted by Sa-gom Blog on April 13, 2018

[Algorithm] 백준 14891번 톱니바퀴

백준 온라인 저지 14891 번 톱니바퀴 문제 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이 때, 톱니바퀴를 총...

Posted by Sa-gom Blog on April 13, 2018

[Algorithm] 백준 14503번 로봇청소기

백준 온라인 저지 14503 번 로봇청소기 문제 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중...

Posted by Sa-gom Blog on April 13, 2018

[Algorithm] 백준 7576번 BFS

백준 온라인 저지 7576 번 토마토 문제 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다....

Posted by Sa-gom Blog on April 9, 2018

[Algorithm] 백준 2667번 DFS

백준 온라인 저지 2667 번 단지번호 붙이기 문제 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 ...

Posted by Sa-gom Blog on April 8, 2018

[Algorithm] 백준 10451번 DFS

백준 온라인 저지 10451 번 순열사이클 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 와 같다. 순열을 배열을 이용해 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다. 순열 그...

Posted by Sa-gom Blog on April 7, 2018

[Algorithm] 교환정렬, 합병정렬

교환정렬, 합병정렬 n개의 데이타 (키값은 1~1000 사이의 자연수)를 정렬하는 문제 n개의 데이타를 random으로 생성 O(n^2) 인 exchange sort 알고리즘(A)와 O(n log n) 알고리즘인 merge sort 알고리즘(B)를 구현 특정 n 에 대해 알고리즘 A, B 가 종료될...

Posted by Sa-gom Blog on March 18, 2018