본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 17178번 : 줄서기 www.acmicpc.net/problem/17178 17178번: 줄서기 아이즈원의 팬인 시온이는 드디어 티켓팅에 성공하여 콘서트를 갔다. 콘서트장에 일찍 도착한 시온이는 기대하며 입장을 위해 줄을 섰다. 하지만 아이즈원의 인기대로 시온이를 포함한 많은 www.acmicpc.net stack으로 구현한 문제였습니다. 풀이방법 1. 입장 순서 정렬 먼저 입장해야하는 순서를 티켓정보를 정렬함으로써 알아낼 수 있습니다. 정렬시 주의해야할 점은 티켓의 정보 중 앞 알파벳이 같은 티켓이라면 -다음 숫자가 적은 것이 앞으로 와야합니다. 함수로 정렬 기준을 마련하지 않고 그냥 sort하게 된다면 A-102가 A-4보다 뒤로가게 됩니다. string으로는 A-102가 A-4보다 큰 값이기 때문입니다. 따라서 subs..
(C++) - 백준(BOJ) 17825번 : 주사위 윷놀이 www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net brute force로 푼 문제였습니다. 풀이방법 1. 먼저 윷판을 만듭니다. 각 위치를 파란색 글씨로 넣어 보았습니다. 해당 위치에는 6개의 정보가 들어있는 2차원 배열로 표현합니다. 정보는 배열의 한 인덱스(위치) => {해당 위치의 점수, 주사위 1이 나왔을 때 다음위치, 2가 나왔을때, 3... , 4... , 5... }가 됩니다. 2. 4개의 말의 위치정보를 비트로 표현합니다. 한 턴당 비트 2개로 ..
(C++) - 백준(BOJ) 4470번 : 줄번호 www.acmicpc.net/problem/4470 4470번: 줄번호 텍스트에서 줄을 입력받은 뒤, 줄 번호를 출력하는 프로그램을 작성하시오. www.acmicpc.net 공백을 포함하여 입력받는 문자열 처리 문제였습니다. 풀이방법 1. 줄 수를 입력받은 후 cin버퍼의 개행문자를 지우기 위해 ignore()해줍니다. C언어의 fflush(stdin)와 같은 기능을 하는 함수입니다. 2. 공백을 포함하여 입력받습니다. getline()을 이용하면 됩니다. 3. getline()으로 입력받은 후에는 cin의 오류비트를 clear()해줍니다. 4. 그 후 출력합니다. Code #include using namespace std; int main(){ int n; cin >> n; cin.ignore(); ..
(C++) - 프로그래머스(고득점 kit - 정렬) : H-index 답 programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 모든 경우를 탐색하는 brute force로 풀었습니다. 풀이방법 논문의 수는 최대 1000까지이므로 h-index는 1000까지가 최대입니다. 1000까지 h-index를 증가시키며 가장 큰 h-index를 찾아주시면 됩니다. Code #include #include using namespace std; int solution(vector c..
(C++) - 프로그래머스(고득점 kit - 완전탐색) : 까펫 programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr brute force문제였습니다. 풀이방법 다음 공식이 성립합니다. yellow = (answer.first - 2) * (answer.second - 2) brown = answer.first * answer.second - yellow yellow에 대입한다면 brown = answer.first * answer.second - (answer.first - 2) * (..
(C++) - 프로그래머스(고득점 kit - 완전탐색) : 소수 찾기 programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr dfs를 이용한 완전탐색 문제였습니다. 풀이방법 1. num.size()만큼 있는 종이 조각들을 1개부터 ~ num.size()까지 뽑아봅니다. 조합으로 뽑는게 아닌 순서가 상관있는 순열로 뽑으므로 내가 뽑았던 index를 check하기 위한 배열이 필요합니다. 2. 정해진 개수만큼 뽑았다면 해당 수의 소수여부를 판별합니다. 이때 뽑은 수가 이미 판별된 수라면 ..
(C++) - 백준(BOJ) 1120번 : 문자열 www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 문자열 비교를 적절히 구현하는 문제였습니다. 풀이방법 테스트 케이스를 통해 설명드리겠습니다. a문자열 : adaabc b문자열 : aababbc 일 때 a문자열 앞과 뒤에는 b와 같은 알파벳을 넣는것이 최적의 방법입니다. 따라서 굳이 직접 a문자열의 앞 또는 뒤에 알파벳을 추가한 뒤 비교할 필요가 없습니다. a문자열을 오른쪽으로 한칸씩 옮기며 b문자열과 비교해 차이의 최소..
(C++) - 프로그래머스(연습문제) : 3 x n 타일링 programmers.co.kr/learn/courses/30/lessons/12902 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr dp문제였습니다. 풀이방법 점화식 : d[i] = 3 * d[i-2] + 2 * d[d[0] + d[2] + .... + d[i-4]] Code #include using namespace std; using ll = long long; int solution(int n) { int answer = 0; vector d(n+1,0); d[0] = 1; for(int i = 2; i

티스토리툴바