본문 바로가기

전체 글

 (2344)
(C++) - 백준(BOJ) 11561번 : 징검다리 답 www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이분탐색문제였습니다. 풀이방법 1. 최대의 징검다리를 밟을 경우는 무조건 이전거리보다 1만큼만 더 뛰는 것입니다. 따라서 매번 뛰는 횟수들을 계산했을 때 1의 등차를 가진 수열의 형태로 뛸 거리가 정해집니다. 징검다리 개수를 m개라고 했을 때 m(m+1)/2 > n; cout
(Python) - 백준(BOJ) 5052번 : 전화번호 목록 답 www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 �� www.acmicpc.net 문자열을 다루는 문제였습니다. 풀이방법 문자열을 사전순으로 정렬한 후 i+1번쨰에 있는 문자열에서 i가 있는 것을 확인만 한다면 O(n)만에 일관성 여부를 검사할 수 있습니다. 마지막으로 접두사의 의미를 정확히 알아야합니다. 만약 전화번호 목록에 211, 11211 이런식으로 있다면 11211에 211이 포함이 되어있음에도 접두사가 아니므로 일관성이 있습니다. YES를 출력해야하나 ..
(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..

티스토리툴바