본문 바로가기

Algorithm

 (2139)
(C++) - 프로그래머스(고득점 kit - Greedy) : 체육복 programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr greedy문제였습니다. 풀이방법 1. 학생별 체육복 보유 여부를 판별하기 위한 vector선언 2. 체육복을 잃어버린 학생들은 해당 vector의 index를 0으로 만들어줍니다. 3. 그 후 체육복 여분을 가지고 학생의 index를 1씩 증가시켜줍니다. 4. n까지 학생들을 loop를 돌며 확인합니다. 만약 i번째 학생이 체육복이 없다면 양 옆 여분이 있는 학생(체육복 보유..
(C++) - 백준(BOJ) 6996번 : 애너그램 www.acmicpc.net/problem/6996 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수(> testCase; while(testCase--){ string a,b; cin >> a >> b; int cnt[26], cnt2[26]; int *alpha = getAlpha(a,cnt); int *alpha2 = getAlpha(b,cnt2); if(isAnagram(alpha,alpha2)) cout
(C++) - 백준(BOJ) 10174번 : 팰린드롬 www.acmicpc.net/problem/10174 10174번: 팰린드롬 팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 단어나 숫자들을 말한다. 일반적으로 대소문자를 구분하지 않지만, 공백은 구분한다. 다음은 팰린드롬의 예시이다. Anna Harrah Arora Nat tan 9998999 123 www.acmicpc.net 풀이방법 1. 처음 줄 수에 대한 입력을 받은 후 '\n'가 cin의 버퍼에 남아있을 때 비워주기 위해 ignore함수를 호출해줍니다. 2. cin의 에러비트를 초기화해주고 문장을 입력받습니다. 3. 대문자가 있다면 소문자로 변환해줍니다. 4. 팰린드롬 여부를 검사한 후 출력합니다. Code #include using namespace std; string toLowerCase(s..
(C++) - 백준(BOJ) 2303번 : 숫자 게임 www.acmicpc.net/problem/2303 2303번: 숫자 게임 N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이 www.acmicpc.net dfs 혹은 backtracking하며 brute force하는 문제였습니다. 풀이방법 1. 한 사람마다 5개의 카드를 입력 받은 후 3개의 숫자카드를 dfs로 뽑습니다. 뽑은 후에는 가장 일의자리가 큰 값을 return합니다. 2. 가장 큰 카드의 값, 사람번호 를 pair로 하여 vector에 push 합니다. 3. 가장 큰 카드의 값이 vector의 처음으로 오도록 내림차순, 그리고 만약 카드의 값이 ..
(C++) - 백준(BOJ) 2659번 : 십자카드 문제 www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 모든 경우의 수를 확인하는 brute force문제였습니다. 풀이방법 1. 1111부터 9999까지의 모든 숫자카드를 확인합니다. 2. 한 숫자카드의 시계수를 구합니다. dqeue을 이용해 4개의 경우로 시계수를 만든 후 가장 작은 시계수를 반환합니다. 3. 한 시계수가 이전 시계수들보타 크다면 ans++ 후 값을 그 시계수로 갱신해줍니다. 4. 만약 현재 시계수가 입력받은 십자카드로부터 나온 시계수와 같다면 답을 출력하고 loop를 탈..
(C++) - 백준(BOJ) 13163번 : 닉네임에 갓 붙이기 www.acmicpc.net/problem/13163 13163번: 닉네임에 갓 붙이기 첫 번째 줄에는 닉네임의 수 N(1 ≤ N ≤ 100)이 주어진다. 두 번째 줄부터 N개의 줄에는 음절 단위로 쪼갠 닉네임이 주어진다. 각 줄은 알파벳 소문자와 공백만으로 이루어지며, 쪼갠 닉네임의 총 www.acmicpc.net 간단한 문자열 처리 문제였습니다. 풀이방법 1. cin은 '\n'를 포함해 버퍼에 넣기 때문에 처음 n을 입력받은 후 cin.clear()로 버퍼를 비워줍니다. 2. 이후 사용하는 getline함수 또한 cin을 사용하기 때문에 ignore()함수를 이용해 개행문자를 무시해줍니다. 3. 이후 첫 음절을 god으로 바꾼 후 나머지 문자를 띄어쓰기 없이 붙인 후 출력하시면 됩니다. Code #i..
(C++) - 프로그래머스(고득점 kit - (DFS/BFS)) : 타겟 넘버(DFS) 답 programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr dfs로 푼 문제였습니다. 풀이방법 1. 빼거나 더해서 depth == size까지 target과 같다면 1을 반환, 아니라면 0을 반환 2. dfs함수 호출 후 cnt를 반환 Code #include using namespace std; int dfs(int depth, int num, vector &numbers, in..
(C++) - 프로그래머스(고득점 kit - (DFS/BFS)) : 네트워크 답 programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr bfs문제였습니다. 풀이방법 1. bfs의 호출 개수가 곧 네트워크의 개수가 됩니다. 2. 연결된 인접행렬의 정점을 계속 q에 push하면서 ck배열로 방문했음을 체크해줍니다. Code #include using namespace std; void bfs(int x, int ck[], vector &computers){ queue q; q.push(x); ck[x] = ..

티스토리툴바