본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 11286번 : 절댓값 힙 답 www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0� www.acmicpc.net make_pair를 이용해 priority queue를 사용하는 문제였습니다. 풀이방법 priority queue의 기본 자료구조는(선언시 3번째 인자로 아무것도 설정하지 않거나 less설정을 줬을 때)은 max heap입니다. 이는 priority queue에 들어가는 원소가 pair의 형태를 하고 있어도 같습니다. 따라서 greater로 min heap을 인자로 줌으로써 min hea..
(C++) - 백준(BOJ) 9375번 : 패션왕 신해빈 답 www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 자료구조 map을 이용해 푸는 문제였습니다. map은 key,value가 한 쌍으로 이루어진 자료구조입니다. map header를 추가(#include )해주시면 map이라는 자료구조와 내장함수를 사용할 수 있습니다. map변수이름.내장함수명으로 해당 멤버함수를 사용할 수 있습니다. Member 설명 begin() 첫 ..
(C++) - 백준(BOJ) 9205번 : 맥주 마시면서 걸어가기 답 www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net floyd warshell을 사용해 푸는 문제였습니다. 풀이방법 1. 모든 좌표 사이의 거리를 계산한 후 거리가 1000이하라면 1, 아니면 0으로 저장합니다. 2. 모든 거리 정보들을 floyd warshell로 탐색합니다. i에서 k로 가는 경로 와 k에서 j로 가는 경로 모두 갈 수 있다면 i에서 j로도 갈 수 있으므로 정보를 갱신해줍니다. 즉, [i][j]를 1로 만들어 줍니다. 3. 목적지까지 갈..
(C++) - 백준(BOJ) 2638번 : 치즈 답 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net bfs를 이용해 치즈가 모두 녹는 시간을 출력하는 문제였습니다. 풀이방법 1. 가장자리에 치즈를 놓는 경우는 없으므로 (0, 0)은 무조건 외부공기에 해당합니다. 이를 시작점으로 bfs를 진행합니다. 2-1. bfs함수 안에서 인접한 상하좌우 칸이 공기(0)라면, check해준 후 air queue에 넣어줍니다. 2-2. 인접한 칸이 치즈(1)라면, cheese queue에 무조건 넣어줍니다. 이를 통..
(Javascript) - 백준(BOJ) 11816번 : 8진수, 10진수, 16진수 답 www.acmicpc.net/problem/11816 11816번: 8진수, 10진수, 16진수 첫째 줄에 X가 주어진다. X는 10진수로 바꿨을 때, 1,000,000보다 작거나 같은 자연수이다. 16진수인 경우 알파벳은 소문자로만 이루어져 있다. www.acmicpc.net 문자열을 다루어 8, 10, 16진수로 되어있는 문자열을 10진수로 바꾸어 출력하는 문제였습니다. 풀이방법 1. javascript언어가 굉장히 간편한 점들 중에는 진수변환이 내장함수를 사용하면 1줄의 code만으로 해결이 가능합니다. 2. parseInt 함수 : parseInt(string변수명, string으로 표현된 진수번호)를 통해 10진수의 number자료형으로 바꿀 수 있습니다. * Code에 사용되지는 않았으나 to..
(C++) - 백준(BOJ) 13703번 : 물벼룩의 생존확률 답 www.acmicpc.net/problem/13703 13703번: 물벼룩의 생존확률 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 www.acmicpc.net dp문제였습니다. 풀이방법 생존할 경우 : 제한시간 n초 안에 수면에 가지 않을 때 생존 경우 수 추가 생존 경우 수 : 위로튈때 생존경우 수 + 아래로 내려갈때 생존경우 수 Code #include #include #define ll long long using namespace std; ll height,second; ll flee[1000][1000]; ll dp(ll k,ll n){ ll &ret..
(C++) - 백준(BOJ) 14720번 : 우유축제 답 www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후�� www.acmicpc.net dp문제였습니다 풀이방법 d[n][k] : 위치 n에서 k종류의 우유를 마셨을 때 최대 마신 우유 개수 답 : max(만약 현재위치 n에서 k종류를 마실 차례가 되었다면 그 우유를 마셨을 때 개수, 현재 위치 우유를 마시지 않았을때의 우유 개수) Code #include using namespace std; int num, n; int d[1000][3]; int milk[1000]; int dp(int n,i..
(C++) - 백준(BOJ) 10653번 : 마라톤 2 답 www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net dp로 푼 문제였습니다. 풀이방법 d[n][k] : n번째 체크포인트를 선택했을 때 k개만큼 건너뛰었을 때의 최소 거리일 때 점화식은 다음과 같습니다. 0 k; for(int i = 1; i > v[i].first >> v[i].second; } memset(d,-1,sizeof(d)); for(int i = 1; i

티스토리툴바