알고리즘 풀이
-
백준 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는..
-
백준 1342번 행복의 문자열 :: 마이구미알고리즘 풀이/수학 2017. 10. 15. 22:55
이 글은 백준 알고리즘 문제 1342번 "행복의 문자열" 을 풀이한다.순열(permutation) 알고리즘을 통해 문제를 해결할 수 있다.순열 알고리즘 이해 - http://mygumi.tistory.com/601342번 - https://www.acmicpc.net/problem/1342 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다. 행복의 문자열의 예는 다음과 같다. aabbbaa=> aba..
-
백준 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..
-
백준 1520번 내리막 길 :: 마이구미알고리즘 풀이/동적계획법 2017. 10. 12. 09:35
이 글은 백준 알고리즘 문제 1520번 "내리막 길" 을 풀이한다.풀이 방법은 DFS + DP(동적계획법) 을 통해 해결한다.DFS - http://mygumi.tistory.com/1021520번 - https://www.acmicpc.net/problem/1520 단순히 모든 경로를 탐색한다면, 시간 초과를 경험하게 된다.시간을 줄일 수 있는 방법은 다음과 같다.20 지점에 오면 더이상 탐색할 필요가 없이 경로가 존재한다는 것을 찾을 수 있다.존재하는 경로를 활용하는 방법으로써, 동적계획법을 이용할 수 있다. dp[y][x] = (y, x) 지점일 때 존재하는 경로의 갯수 DFS를 완벽히 이해하고 있다면, 쉽게 코드를 이해할 수 있다.* dp배열을 -1로 초기화한 이유는 방문여부를 위함이다. 1234..