본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 17836번 : 공주님을 구해라! https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net bfs문제였습니다. (첫 글자 대문자 언어 이름 ) - 문제 명 답 풀이방법 문제에서는 (1,1)에서 출발해 (n,m)에 도착하는 최소시간으로 나와있으니 (0,0)에서 출발해 (n-1, m-1)에 도착하는 최소시간으로 생각할 수 있습니다. 1. 입력을 받은 후 bfs를 두 번 수행합니다. 1-1. 첫 번째 bfs는 (0,0)에서 출발해 그람이 있는 곳으로 가는 최단시간을 구합니다...
(C++) - 2019 카카오 개발자 겨울 인턴십 : 호텔 방 배정 https://programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr union find 문제였습니다. 풀이방법 이분탐색으로 시행하는 것을 생각할 수 있으나 요청한 방이 이미 있는 방에 경우 배정할 방을 정하기 어렵습니다. 2번방부터 10번방까지 다차있는 경우 2번방에 대한 요청이 들어왔을 때 11번방을 바로주지 못한다면 O(n)의 시간이 걸려 순차적으로 탐색해야하기 때문입니다. 또한 10^12로 k가 매우 크므로 배열로 방 번호를 잡을 수 없습니다. 따라서 map으로 해당방을 이미 이용하는지 아닌지를 알아보는 방법을 선택했습니다. 또한 대체로 줄 수 있는 방번호를 찾을 수 있는알고리즘으로 union - f..
(C++) - 백준(BOJ) 2467번 : 용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net two pointer문제였습니다. 풀이방법 1. l = 0, r = n-1로 시작해 두 용액의 합을 찾습니다. 2. 두 용액의 합에 대해 절댓값이 더 작다면 현재 합을 갱신해줍니다. 그리고 정답에 대한 index 또한 갱신해줍니다. 3. 현재 l과 r의 값 합이 0이면 loop를 탈출, 양수라면 양수가 있을 확률이 있는 r을 --, 음수라면 더 큰 값을 더해야하므로 l을 ++해주면서 원하는 ..
(C++) - 백준(BOJ) 2981번 : 검문 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net gcd구한 후 약수를 구하는 문제였습니다. 풀이방법 1. gcd 구하기 : 나누어 나머지가 같은 m의 의미는 각 수의 차이들에 대해 최대공약수를 찾는 다면 이들의 약수가 모두 m이 된다는 뜻입니다. 2. 약수 구하기 : i * i > n; for(int i = 0; i > num[i]; for(int i = 1; i < n; i++) m = gcd(abs(num[i] - num[i-1]..
(C++) - 백준(BOJ) 3649번 : 로봇 프로젝트 https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 이분탐색 문제였습니다. 풀이방법 1. 입력 : 구멍의 단위가 cm으로 주어지기 때문에 nm으로 변경합니다. 1천만을 곱해주면됩니다. 이를 length라는 변수에 저장합니다. 이후 vector형 변수 lego에 n만큼 lego의 길이들을 입력받습니다. 2. lego를 오름차순으로 정렬합니다. 현재 확인하고 있는 한쪽 lego의 길이가 lego[i]일 때 length - le..
(C++) - 프로그래머스(2021 카카오 채용연계형 인턴십) : 표 편집 https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 자료구조 활용해 푸는 구현문제였습니다. 풀이방법 삽입 삭제가 빈번해질 경우 해당 연산이 이뤄질 때마다 정렬을 하는 map같은 자료구조는 시간초과가 납니다. hash map또는 double linkedList로 구현해야합니다. Code 양방향 Linked-List #include using namespace std..
(C++) - 프로그래머스(2021 카카오 채용연계형 인턴십) : 거리두기 확인하기 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr bfs로 풀었습니다. 풀이방법 1. 모든 수험자에 대해 bfs를 수행합니다. bfs를 수행..
(C++) - 프로그래머스(2021 카카오 채용연계형 인턴십) : 숫자 문자열과 영단어 https://programmers.co.kr/learn/courses/30/lessons/81301?language=cpp 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 간단한 문자열 문제였습니다. 풀이방법 1. map에 각 대응 문자와 숫자를 저장합니다. 2. 단어를 읽으며 적절히 매칭되었다면 정답에 문자를 추가해줍니다. 3. 문자를 수로 바꿔 반환합니다. Code #include using namespace std; int solution(string s) { map m; m["zero"] ..

티스토리툴바