목록전체 글 (217)
Study hard
(c++)프로그래머스 코딩테스트 연습 - 등굣길
programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr [풀이] 오른쪽과 아래로만 움직이면 갈 수 있는 지도의 면적이 작게 쪼개지므로 DP를 사용해 풀 수 있다. 점화식 DP[i][j] : (i,j)좌표로 가는 최단 경로의 수 DP[i][j] = DP[i-1][j] + DP[i][j-1] #include #include using namespace std; const int D = 1000000007; int dp[10..
(c++)프로그래머스 코딩테스트 연습 - 정수 삼각형
programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr [풀이] 정확성과 효율성을 둘 다 보는 문제여서 DP를 이용해 풀었다. 바닥부터 꼭대기까지 각 숫자를 선택했을 때 그 숫자 밑으로 얻을 수 있는 최댓값을 저장하면서 올라갔다. dp[0][0]에는 거쳐간 숫자의 최댓값이 저장된다. #include #include using namespace std; int **dp; int Level; int dp_size; void DP(vectortriangle) { for (int i = 0; i < Level; ..
(c++)프로그래머스 코딩테스트 연습 - 카펫
programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 �� programmers.co.kr [풀이] 노란 격자의 모든 가능한 경우에 대해 노란 격자를 감싸는 테두리의 개수가 brown과 같은지 비교하는 방법으로 풀었다. #include #include using namespace std; int Brown,Yellow; vectorAnswer; bool getRowCol(int row, int col){ int tmp=row*2+col*2+4; if(Bro..
(c++) 프로그래머스 코딩테스트 연습 - 소수 찾기
programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 � programmers.co.kr [풀이] dfs순열을 이용하여 나올 수 있는 모든 수에 대해 소수인지 확인하고, set 자료구조를 써서 중복값이 없도록 하였다. 소수는 에라토스테네스의 체를 사용하여 미리 1이상 9999999이하의 모든 소수를 찾아두었다. 2020/06/18 - [백준/여러가지 문제들] - (c++)백준 1929번: 소수 구하기 (c++)백준 1929번: 소수 구하기 htt..
(c++) 프로그래머스 코딩테스트 연습 - 모의고사
programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 �� programmers.co.kr [풀이] 완전탐색으로 각각 학생의 답안과 정답을 비교하여 맞은 개수를 세고, 가장 많이 맞은 사람을 찾는 문제였다. 가장 높은 점수를 받은 사람을 찾을 때는 Max변수에 최댓값을 저장해두고 비교하면서 같으면 벡터에 넣고, 더 높은 점수가 나오면 벡터를 비운 다음 그 학생의 번호를 넣는 방식으로 풀었다. #include #include #include //#include ..
(c++)프로그래머스 코딩테스트 연습 - 단어 변환
programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr [풀이] dfs로 words배열에서 현재 단어와 한글자만 다른 단어를 찾아 현재 단어가 target단어가 될 때까지 탐색하는 방법으로 풀었다. 단계가 현재까지 구한 최솟값보다 커질 경우 가지치기 하여 시간을 단축하였다. #include #include #include using namespace std; vectorWords; int..