마이구미의 HelloWorld 마이구미의 HelloWorld

알고리즘 풀이

• 백준 16234번 인구 이동 :: 마이구미

  알고리즘 풀이/그래프 2018. 11. 25. 14:52

  이 글은 백준 알고리즘 문제 16234번 "인구 이동" 을 풀이한다.문제는 BFS 를 통해 풀이한다.삼성 SW 역량 테스트에서 출제된 문제이다.문제 링크 - https://www.acmicpc.net/problem/16234BFS - http://mygumi.tistory.com/102 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.오늘부터 인구 이동이 시작되는 날이다.인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.국경선을 공유하는 ..

  Read More

• 백준 1325번 효율적인 해킹 :: 마이구미

  알고리즘 풀이/그래프 2018. 11. 21. 00:44

  이 글은 백준 알고리즘 문제 1325번 "효율적인 해킹" 을 풀이한다.문제는 DFS 를 통해 접근한다.DFS 가 익숙하지 않는다면, 아래 관련 링크를 읽어보면 좋다.문제 링크 - https://www.acmicpc.net/problem/1325DFS - http://mygumi.tistory.com/102- 현재 코드(Java)는 최근 재채점으로 인해 시간초과를 발생시킨다 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할..

  Read More

• 백준 15685번 드래곤 커브 :: 마이구미

  알고리즘 풀이/수학 2018. 11. 17. 12:53

  이 글은 백준 알고리즘 15685번 "드래곤 커브" 문제를 풀이한다.삼성 SW 역량 테스트의 문제로 출제된 적이 있다.시뮬레이션 문제로써, 난이도 있는 알고리즘을 요구하는 문제는 아니다.15685번 드래곤 커브 - https://www.acmicpc.net/problem/15685 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.시작 점시작 방향세대0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다...................................................................

  Read More

• 백준 2805번 나무 자르기 :: 마이구미

  알고리즘 풀이/이진 탐색 2018. 9. 9. 19:18

  이 글은 백준 알고리즘 문제 2805번 "나무 자르기" 를 풀이한다.많은 제출량과 비교적 낮은 정답률이지만, 쉽게 풀이할 수 있는 문제이다.문제 풀이 방법으로는 단순 "이분 탐색" 을 이용한다.문제 링크 - https://www.acmicpc.net/problem/2805이분 탐색 - http://mygumi.tistory.com/72 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다.목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터..

  Read More

• 백준 1652번 누울 자리를 찾아라 :: 마이구미

  알고리즘 풀이/수학 2018. 8. 14. 13:57

  이 글은 백준 알고리즘 문제 1652번 "누울 자리를 찾아라" 를 풀이한다.제출량이 많고, 정답 비율이 40% 인 문제.DFS, BFS 문제처럼 보이지만, 쉽게 해결할 수 있는 문제이다.본인에게는 다른 접근을 생각하는 자극을 준 문제이다.문제 링크 - https://www.acmicpc.net/problem/1652 일 년 동안 세계일주를 하던 영식이는 여행을 하다 너무 피곤해서 근처에 있는 코레스코 콘도에서 하룻밤 잠을 자기로 하고 방을 잡았다.코레스코 콘도에 있는 방은 NxN의 정사각형모양으로 생겼다. 방 안에는 옮길 수 없는 짐들이 이것저것 많이 있어서 영식이의 누울 자리를 차지하고 있었다. 영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 한다. 영식이가 누울 수 있는 자리에는 조건이 있다..

  Read More

• 백준 6064번 카잉 달력 :: 마이구미

  알고리즘 풀이/수학 2018. 7. 16. 12:44

  이 글은 백준 알고리즘 문제 6064번 "카잉 달력" 을 풀이한다.일반적으로 시뮬레이션 문제라고 보이지만, 순수하게 접근하면 시간 초과를 초래한다.별도 알고리즘 지식이 아닌, 시간 초과를 해결하는 다른 접근을 요구한다.문제 링크 - https://www.acmicpc.net/problem/6064 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M 과 N 보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 ..

  Read More

• 백준 15686번 치킨 배달 :: 마이구미

  알고리즘 풀이/브루트 포스 2018. 4. 29. 01:14

  이 글은 백준 알고리즘 문제 15686번 "치킨 배달" 을 풀이한다.2018 삼성 SW 역량 테스트 문제이다.접근 방법은 브루트포스와 DFS 를 통해 풀이한다.문제 링크 - https://www.acmicpc.net/problem/15686DFS - http://mygumi.tistory.com/102 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가..

  Read More

• 백준 15683번 감시 :: 마이구미

  알고리즘 풀이/브루트 포스 2018. 4. 28. 18:15

  이 글은 백준 알고리즘 문제 15683번 "감시" 를 풀이한다.2018 삼성 SW 역량 테스트 문제이다.접근 방법은 브루트포스와 DFS 를 통해 풀이한다.문제 링크 - https://www.acmicpc.net/problem/15683DFS - http://mygumi.tistory.com/102 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.1번2번3번4번5번1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 ..

  Read More