전체 글
-
백준(BOJ) 2294번 동전 2알고리즘 풀이/백준(Boj) 2019. 8. 13. 16:27
문제 : https://www.acmicpc.net/problem/2294 문제n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 나의 풀이:반복적 동적 계획법을 통해 해결해보자 . cache[i] 는 i 원을 만들 수 있는 최소 동전의 수로 놓고 동적 계획법을 짜보자 예제 ) 코드 ( C++ ) #include #include using namespace std;int n, k;int coin[101];int cache[10001];const int INF = 987654321;int solve()..
-
백준(BOJ) 1620번 나는야 포켓몬 마스터 이다솜알고리즘 풀이/백준(Boj) 2019. 8. 12. 15:13
문제 : https://www.acmicpc.net/problem/1620 문제 오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네. 나의 풀이: N과 M이 10만 이기때문에 완전탐색으로는 10만 * 10만이 되어서 시간 내에 불가능하다. 이분탐색으로 접근하여야 가능하다. 그런데 숫자가 주어젔을 경우 에는 이분탐색으로 접근하지 않고 바로 인덱스로 접근해도 해결이 가능하다. 따라서 숫자시 인덱스로 바로 접근 , 알파벳일시 이분 탐색으로 접근해주자. ..
-
다익스트라 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 11. 18:11
다익스트라의 최단 경로 알고리즘 다익스트라 알고리즘은 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. 다익스트 라 알고리즘은 너비 우선 탐색과 유사한 형태를 가진 알고리즘으로 가까운 순서대로 정점을 방문해 가지만 가중치가 있는 그래프에서는 너비 우선 탐색을 그대로 적용할 수 없다. 너비 우선 탐색은 각 정점을 발견한 순서대로 방문하지만 다익스트라 알고리즘은 더 늦게 발견 한 정점이라도 더 먼저 방문할 수 있어야 한다. 코드 ( C++ )// 우선순위 큐를 이용해서 구현한 다익스트라 알고리즘#include #include #include #include using namespace std;const int MAX_V = 100;const int INF =..
-
백준(BOJ) 7569번 토마토알고리즘 풀이/백준(Boj) 2019. 8. 11. 02:04
문제 : https://www.acmicpc.net/problem/7569 문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된..
-
백준(BOJ) 1389번 케빈 베이컨의 6단계 법칙알고리즘 풀이/백준(Boj) 2019. 8. 10. 02:27
문제 : https://www.acmicpc.net/problem/1389 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-..
-
백준(BOJ) 2437번 저울알고리즘 풀이/백준(Boj) 2019. 8. 9. 16:23
문제 : https://www.acmicpc.net/problem/2437 문제하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 나의 풀이: 사용 가능한 무게추들을 오름차순 정렬한다. 그 후 정렬된 가장..
-
백준(BOJ) 1405번 미친 로봇알고리즘 풀이/백준(Boj) 2019. 8. 9. 02:01
문제: https://www.acmicpc.net/problem/1405 문제통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남) 나의 풀이: 상하좌우로 최대 14번 갈 수 있으므로 MAX를 넉넉히 30으로 잡자. 방문경로를 나타내는 vis..
-
2019 데이터베이스 공부 시작은?DB 2019. 8. 8. 23:58
데이터베이스를 배우기에 앞서 그에 맞는 트렌드를 우선적으로 파악하고 공부한다면 더 효율적이기에 조사를 해 보았다. 아래 표는 db-engines ranking 에 따른 랭킹 분석표이다. 1위는 오라클 2위는 MySql 3위는 Microsoft SQL Serer 이고 4위 5위로 PostgreSQL 과 MongoDB가 있다. 또 2019년에 가장 인기있는 데이터베이스는 무엇입니까? 라는 질문에 개발자들은 MySQL이 38.9%, MongoDb 24.6% PostgreSQL은 17.4% Redis는 8.4% Cassandra는 3.0%를 기록했다. https://scalegrid.io/blog/2019-database-trends-sql-vs-nosql-top-databases-single-vs-multip..