본문 바로가기

Algorithm

 (2139)
(C++) - 프로그래머스(연습문제) : 최솟값 만들기 programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr 수학 문제였습니다. 풀이방법 1. 두 수의 곱들의 합이 최소가 되려면 최소값 * 최대값들의 합으로 만들어주면 됩니다. 2. A를 오름차순 정렬, B를 내림차순 정렬한 뒤 차례대로 A[i] * B[i]한뒤 answer에 더해줍니다. Code #include using namespace std; int solution(vector A, vector B) { ..
(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 방문길이 programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 단순 구현문제였습니다. 풀이방법 1. 현재 위치에서 이동시에 좌표평면 바깥으로 넘어가지 않는다면 걸어갈 수 있는지 판단할 수 있습니다. 2. 넘어가지 않는다면 명령어를 시행한 후의 다음위치 X,Y를 nextX, nextY변수에 저장해줍니다. 3. 다음 각자 가는 방향에 따라 판단해줍니다. 3-1. 'U'인경우 현재위치에서 올라가는 방향이 이미 간 길이 아니라면 새로운 길이므로 answer++; 그리고 다음위치에서 내려가는 방향 또한 같은 길이기 때문에 갱신해주어야합니다. 3-2. 'D'인경우 현재위치에서 내려가는 방향이 이미 간 길이 아니라면 새로운 길이므..
(C++) - 프로그래머스(찾아라 프로그래밍 마에스터) : 게임 맵 최단거리 programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr bfs문제였습니다. 풀이방법 1. bfs 수행 : d배열을 선언해서 0,0에서 출발하여 벽이 아닌 부분을 이동하며 거리를 저장합니다. 2. 도착했을 때 해당 부분의 값이 0이라면 갈수 없으므로 -1을 반환합니다. 아니라면 d[n-1][m-2]를 반환합니다. Code #include using namespace std; us..
(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 영어 끝말잇기 programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr 구현문제였습니다. 풀이방법 1. 이전 단어의 끝 알파벳이 현재 단어의 처음 알파벳과 다르거나 map..
(C++) - 백준(BOJ) 1080번 : 행렬 www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net greedy문제였습니다. 풀이방법 1. 왼쪽 상단부터 a가 b와 다르다면 a의 해당 위치에 연산함수를 실행합니다. 이렇게 b와 같도록 결정하게 되면 다시 살펴볼 필요가 없습니다. 실행과 함께 ans변수를 ++해줍니다. 2. 행렬 크기만큼 loop를 돌며 만약 a와 b가 서로 다르면 만들 수 없으므로 -1을 출력합니다. Code #include using namespace std; int a[51][51],b[51][51],n..
(C++) - 백준(BOJ) 1946번 : 신입 사원 www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 매 테스트 케이스마다 n개의 서류심사, 면접심사 성적 순위를 pair로 한 data를 vector에 입력합니다. 2. 그 후 서류심사 성적 순위를 기준으로 오름차순으로 정렬합니다. 이렇게 되면 0번째 지원자를 제외한 나머지 인원들은 무조건 성적이 0번째보다 더 낮으므로 두번째 면접점수만 비교하면 됩니다. i번째 지원자의 면접성적이 i-1번째 지원자의 ..
LCS(Longest Common Subsequence) 최장 공통 부분 문자열입니다. 부분이라는 뜻은 연속하지 않아도 된다는 뜻입니다. 이 문제는 두 문자열이 겹치는 문자들의 최장 길이를 구하는 문제입니다. 띄엄띄엄 겹치더라도 이들을 모아 각각 하나의 문자열을 만들었을 때 두 문자열이 같다면 공통 부분 문자열이고 이 문자열의 길이가 곧 LCS에서 구하는 답 입니다. www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 대표적인 백준 문제를 예시로 이해해 봅시다. 나와 있는 ..
(C++) - 백준(BOJ) 2565번 : 전깃줄 www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net dp(lis) 문제였습니다. 풀이방법 1. a, b가 pair형태로 저장되는 vector v변수를 선언 후 n개의 젓깃줄 정보를 입력받습니다. 2. a를 기준으로 sort해줍니다. 3. 교차하지 않으려면 봐야할 정보는 1가지 입니다. 이미 a는 오름차순으로 정렬되어 있으니 b만 연속해서 오름차순으로 되어 있는지, 그 길이는 몇인지 확인하면 됩니다. 4. n - 길이가 답이고 이를 출력합니다. Code #include ..

티스토리툴바