본문 바로가기

Algorithm/문제 풀이 (Problem Solving)29

[C++, 완전탐색] 프로그래머스 양궁대회 문제 https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr 풀이 완전탐색 문제이다. 총 11개의 점수(0점 ~ 10점) 에서 라이언이 해당 점수를 선택하냐 선택하지 않느냐로 나눌 수 있다. 구현이 쉬운 dfs로 풀이하였다. 해당 문제에서 주의해야 할 점이 있다. 문제를 꼼꼼히 읽어보면 알 수 있는데 예시에도 나와있듯이 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 .. 2022. 4. 7.
[C++, 문자열, 슬라이딩 윈도우] 프로그래머스 추석 트래픽 문제 https://programmers.co.kr/learn/courses/30/lessons/17676 2022. 4. 5.
[C++, 문자열] 프로그래머스 오픈채팅방 문제 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 해답 Stringstream과 hash를 이용해 풀이하였다. #include #include #include #include #include using namespace std; unordered_map nameMap; class tans{ public: string ac; string h; }; vector solution(vector record) { .. 2022. 4. 4.
[C++, 문자열] 프로그래머스 다트게임 문제 https://programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 해답 stringsteam을 잘 활용하니 parsing을 쉽게 할 수 있었다. #include #include #include #include using namespace std; int solution(string dartResult) { stringstream ss(dartResult); int answer = 0; int answerList[3] = { 0, }; int strIdx = 0; for (int i = 0; i < 3; i++) { //parsing int score = 0; char bonus = 0, opt.. 2022. 3. 31.
[C++, 문자열] 프로그래머스 신규 아이디 추천 문제 https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 해답 문자열 연습하기 정말 좋은 문제라고 생각한다. 해답 밑에 해답에서 사용한 std 함수들을 간략하게 설명하였다. #include #include #include using namespace std; string solution(string new_id) { //1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. for (int i .. 2022. 3. 23.
[C++, 세그먼트 트리, 데이터추가 반영] 백준 2042번 구간 합 구하기 www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 21.02.17 데이터 추가 반영하였습니다. 세그먼트 트리의 입문문제라고 할 수 있다. 따라서 세그먼트 트리 초보자에게 구현이 간편한 방법을 소개하고자 한다. update함수와 query함수 단 2개의 함수만 이용해서 해결할 수 있는 방법이다. 세그먼트 트리 초기화를 update문을 이용해서 구현하면 실행시간은 늘어나지만 구현이 간편해진다는 장점이 있다.. 2020. 11. 22.
[C++,구현, 중복 순열] 백준 17825번 주사위 윷놀이 문제풀이 https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 주사위 윷놀이, 구현에서도 어려운 축에 속한다고 생각한다. 주사위에서 나올 수 있는 10개의 수 순서에 각각 4개의 말들을 매칭 시킨다고 하면 중복 순열이다. 전체의 경우의 수는 4^10 가지가 나온다. 처음에는 아래와 같이 풀이하였다. #include #include using namespace std; typedef struct lo { int x, y; }; int pan[4][30] = { { -1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 3.. 2020. 6. 1.
[C++, Hash] 프로그래머스 베스트앨범 문제 풀이 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 | 프로그래머스 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 play programmers.co.kr 풀이 참고하지 않고 스스로 한 번에 풀어서 더욱 뿌듯한 문제이.. 2019. 12. 12.
[C++, Hash] 프로그래머스 위장 문제 풀이 문제링크 https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 | 프로그래머스 programmers.co.kr 풀이 기본적인 접근은 맞았는데 응용력이 부족했던 문제이다. 조합을 구성할 때 선택하지 않는다는 선지도 같이 포함시켜 계산한다는 것이 포인트이다. 대분류의 조합들을 hash를 통해 count하고 선택하지 않는다는 선지를 포함시켜 각각 +1 해준 뒤 곱하면 되는 것이다. 그리고 스파이가 하루에 최소 한 개의 의상은 입으므로 모두 입지 않는다는 경우의 수를 빼면 답이 된다. #include #include #include using namespace std; int solution(vector clothes) { int answ.. 2019. 12. 11.
[C++, Hash] 프로그래머스 전화번호 목록 문제 풀이 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 | 프로그래머스 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 r programmers.co.kr 풀이 코딩테스트에서 해시관련 문제가 좀 약한 느낌이 들어서.. 2019. 12. 10.
[C++, Trie] 프로그래머스 가사 검색 문제 풀이 https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 | 프로그래머스 programmers.co.kr 재밌는 문제이다. 이 문제로 인해 트라이 자료구조를 알게 되었다. 트라이는 문자열의 검색에 효율적인 자료구조이며 트리구조로 되어 있다. 처음에 문제를 보면 따로 트라이라는 자료구조를 공부한적 없는 분이라면 대부분 아래와 같은 해답을 떠올릴 것이다. 나 역시 그랬다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include #include using name.. 2019. 11. 3.
[C++, DFS, Bitmask] 백준 17471번 게리맨더링 문제풀이 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 해설 비트마스크라는 참신한 풀이법을 익힌 문제이다. 그래프 문제에서 유용하게 쓰일 수 있는 기법을 발견했다. 선거구 즉, 총 노드의 개수만큼 비트를 할당하여 방문할 노드 선정하는 방법이다. 코드에서 i는 노드에 방문할 총 가짓수를 나타내고 j는 실제 방문한 노드를 나타내어 dfs기법으로 각 노드를 탐색한다. 여기서 특정할 만한 건 i를 반전시켜 2개로 나눈 그룹의 인구를 다시 빼준다는 것이다. 끝에 모두 방문했는.. 2019. 10. 4.

티스토리툴바