알고리즘 풀이/그래프
-
백준 2529번 부등호 :: 마이구미알고리즘 풀이/그래프 2017. 12. 30. 15:58
이 글은 백준 알고리즘 문제 2529번 "부등호" 를 풀이한다.정올 초등부에서 출제된 문제이다.본인은 백트래킹을 활용해서 문제를 해결했다.문제 링크 - https://www.acmicpc.net/problem/2529 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A => 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0이 상황에..
-
백준 11559번 Puyo Puyo :: 마이구미알고리즘 풀이/그래프 2017. 12. 11. 11:10
이 글은 백준 알고리즘 문제 11559번 "Puyo Puyo" 를 풀이한다.시뮬레이션 문제로써, 시나리오를 정확히 이해한 후 그대로 구현하면 된다.본인은 그 과정속에 DFS를 통해 해결했다.문제 링크 - https://www.acmicpc.net/problem/11559 뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이..
-
백준 14889번 스타트와 링크 :: 마이구미알고리즘 풀이/그래프 2017. 10. 29. 14:42
이 글은 백준 알고리즘 문제 14889번 "스타트와 링크" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.본인은 DFS를 활용해 문제를 해결했다.문제 링크 - https://www.acmicpc.net/problem/14499DFS 참고관련 문제 - http://mygumi.tistory.com/191DFS 이해 - http://mygumi.tistory.com/102 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 ..
-
백준 14888번 연산자 끼워넣기 :: 마이구미알고리즘 풀이/그래프 2017. 10. 29. 00:12
이 글은 백준 알고리즘 문제 14888번 "연산자 끼워넣기" 를 풀이한다.2017 삼성 SW 역량 테스트의 문제 중 하나이다.본인은 DFS로 문제를 풀이할 것이다.문제 링크 - https://www.acmicpc.net/problem/14499DFS 참고관련 문제 - http://mygumi.tistory.com/191 DFS 이해 - http://mygumi.tistory.com/102 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이 때, 주어진 수의 순서를 ..
-
백준 1726번 로봇 :: 마이구미알고리즘 풀이/그래프 2017. 10. 28. 22:44
이 글은 백준 알고리즘 문제 1726번 "로봇" 을 풀이한다.본인은 BFS를 통해 문제의 풀이를 설명할 것이다.문제 링크 - https://www.acmicpc.net/problem/1726BFS 이해 - http://mygumi.tistory.com/102 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.명령 1. Go k - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.명령 2. Turn dir - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.공장 내 궤도가 설..
-
백준 14503번 로봇 청소기 :: 마이구미알고리즘 풀이/그래프 2017. 10. 28. 17:34
이 글은 백준 알고리즘 문제 14503번 "로봇 청소기" 를 풀이한다.삼성 SW 역량 테스트 문제 중 하나의 문제이다.본인은 BFS를 활용한 풀이를 설명할 것이다.문제 링크 - https://www.acmicpc.net/problem/14503BFS 이해 - http://mygumi.tistory.com/102 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는..
-
백준 9518번 로마 카톨릭 미사 :: 마이구미알고리즘 풀이/그래프 2017. 10. 15. 22:33
이 글은 백준 알고리즘 문제 9518번 "로마 카톨릭 미사" 를 풀이한다.본인은 BFS를 응용하여 문제를 풀이하였다.9518번 - https://www.acmicpc.net/problem/9518BFS 이해 - http://mygumi.tistory.com/102 로마 카톨릭 미사에서 가장 멋진 부분은 사람들이 서로 악수를 하면서 "평화가 함께하기를" 이라고 말하는 평화 의식이다.성당에는 R개의 벤치가 한 행에 하나씩 있고, 각 벤치에는 총 S명이 앉을 수 있다. 성당의 좌석 배치는 크기가 R × S인 행렬로 나타낼 수 있고, 행렬의 각 원소는 사람이 있는지 없는지로 나타낼 수 있다. 모든 사람은 자신의 이웃과 악수를 한다고 가정한다. 이웃은 사람이 있는 칸과 인접한 칸 여덟개이다. (칸이 존재하지 않을..
-
백준 3055번 탈출 :: 마이구미알고리즘 풀이/그래프 2017. 10. 15. 22:09
이 글은 백준 알고리즘 문제 3055번 "탈출" 을 풀이한다. 본인은 BFS를 활용하여 문제를 해결하였다. 3055번 - https://www.acmicpc.net/problem/3055 기본 DFS, BFS - http://mygumi.tistory.com/102 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S..