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

알고리즘 풀이

• 백준 1744번 수 묶기 :: 마이구미

  알고리즘 풀이/그리디 2017. 9. 18. 20:59

  이 글은 백준 알고리즘 문제 1744번 "수 묶기" 를 풀이한다.문제의 접근 방법은 그리디 알고리즘으로써, 어떠한 자료구조를 요구하지는 않는다.하지만 정답 비율이 낮은 문제로써, 까다로울 수 있다.1744번 "수 묶기" - https://www.acmicpc.net/problem/1744그리디 알고리즘 - http://mygumi.tistory.com/121 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 어떤 인접한 원소끼리를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구..

  Read More

• 백준 5052번 전화번호 목록 :: 마이구미

  알고리즘 풀이/수학 2017. 9. 17. 12:55

  이 글은 백준 알고리즘 문제 5052번 "전화번호 목록" 을 풀이한다.해싱, 트리와 같은 자료구조를 통해 해결할 수 있다.본인은 논리적 사고를 통한 센스로 문제를 쉽게 풀이하는 것을 다뤄본다.5052번 "전화번호 목록" - https://www.acmicpc.net/problem/5052 전화번호 목록이 주어진다. 이 때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자긴급전화: 911상근: 95 625 999선영: 91 12 54 26이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 ..

  Read More

• 백준 1941번 소문난 칠공주 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 15. 23:52

  이 글은 백준 알고리즘 문제 1941번 "소문난 칠공주" 를 풀이한다.기본적인 DFS를 통한 백트래킹을 활용해서는 이 문제를 해결할 수 없다.문제 접근에 있어, 아이디어가 필요한 문제이다.1941번 - https://www.acmicpc.net/problem/1941DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지..

  Read More

• 백준 2023번 신기한 소수 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 15. 22:54

  이 글은 백준 알고리즘 2023번 문제 "신기한 소수" 를 풀이한다.백트래킹을 통한 문제 풀이가 된다.백트래킹에 대한 기본적인 이해가 필요하다면, 다음 글을 참고바란다.http://mygumi.tistory.com/1912023번 신기한 소수 - https://www.acmicpc.net/problem/2023DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수 7331이다.7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터..

  Read More

• 백준 2858번 기숙사 바닥 :: 마이구미

  알고리즘 풀이/수학 2017. 9. 12. 20:32

  이 글은 백준 알고리즘 문제 2858번 "기숙사 바닥" 을 풀이한다.문제 풀이는 수학적 접근과 브루트 포스를 활용한다.문제 링크 - https://www.acmicpc.net/problem/2858 상근이는 기숙사 생활을 한다. 상근이의 방의 크기는 L*W 이다.수업시간에 타일 채우기 경우의 수를 계산하던 상근이는 자신의 방도 1*1크기 타일로 채우려고 한다. 이 때, 가장자리는 빨간색으로, 나머지는 갈색으로 채우려고 한다.아래 그림은 상근이의 방의 크기가 4*3일 때 이다.어느날 상근이네 방에 하근이가 놀러왔다. 하근이는 아름다운 타일 배치에 감동받았다. 다시 방으로 돌아온 하근이는 빨간색과 갈색 타일의 개수는 기억했지만, 방의 크기는 기억해내지 못했다.빨간색과 갈색 타일의 개수가 주어졌을 때, 상근이..

  Read More

• 백준 1644번 소수의 연속합 :: 마이구미

  알고리즘 풀이/수학 2017. 9. 10. 12:04

  이 글은 백준 알고리즘 문제 1644번 "소수의 연속합" 을 풀이한다.접근은 에라토스테네스의 체를 통해 소수를 구하고, 투 포인터 또는 슬라이드 윈도우를 적용했다.투 포인터 및 슬라이드 윈도우의 개념은 중요하지 않다.본인 또한 구현하니 위와 같이 불리는 방식이였다.에라토스테네스의 체는 다음 링크를 참고하자.소수를 위한 에라토스테네스의 체 - http://mygumi.tistory.com/661644번 문제 - https://www.acmicpc.net/problem/1644 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+1..

  Read More

• 백준 2661번 좋은수열 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 9. 21:49

  이 글은 백준 알고리즘 문제 2661번 "좋은수열"을 풀이한다.접근 방식은 백트래킹을 활용해 문제를 해결한다.문제 링크는 다음과 같다.https://www.acmicpc.net/problem/2661DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.다음은 나쁜 수열의 예이다.3332121323123123213다음은 좋은 수열의 예이다.232321231232123길이가 N인 좋은 수열들을 N자리의 정수로 보아 ..

  Read More

• 백준 1759번 암호 만들기 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 9. 15:04

  이 글은 백준 알고리즘 문제 1759번 "암호 만들기" 를 풀이한다.접근 방법은 백트래킹을 활용해 문제를 풀이한다.6603번 로또 문제와 흡사하다.조금 응용된 문제로써, 백트래킹을 잘 모른다면 먼저 참고하길 바란다.6603번 로또 - http://mygumi.tistory.com/191문제 링크는 다음과 같다.https://www.acmicpc.net/problem/1759DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보..

  Read More