본문 바로가기

Algorithm39

[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.
[C++] 코드그라운드 연습문제 프로그래밍 경진대회 문제풀이 문제링크 코드그라운드 연습문제 프로그래밍 경진대회 codeground Codeground is a real-time coding website open to those interested in software development and algorithms. www.codeground.org 간단하지만 효율적인 알고리즘이 잘 떠오르지 않는 문제이다. 문제에서 각 라운드 마다 받은 점수의 합이 제일 높은 사람이 우승한다고 하였는데 이는 우승자가 여러명일 수도 있다는 이야기이다. 이 조건이 이해가 되지 않아 질문이 많은 문제이다. 구하려는 것은 우승이 가능한 사람의 수이므로 각 점수에다 최대치(N)를 더한 점수가 어떤 기준점수를 넘는지 안넘는지 판단하면 된다. 여기서 기준점수는 다른 모든 점수들을 최저로 만.. 2019. 6. 19.
[C++,구현,BFS,DFS] 백준 15686번 치킨 배달 문제풀이 문제링크 백준 15686번 치킨 배달 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net DFS,BFS를 모두 쓴 조금은 힘든? 문제이다. 최대 M개의 치킨집을 고르는 건 DFS, 치킨집을 골라 최소거리를 구하는 건 BFS로 구현하였다. 밑에 코드에 나.. 2019. 5. 25.
[C++,구현] 백준 16234번 인구 이동 문제풀이 문제 링크 백준 16234번 인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 문제를 풀고 나서 생각해보니 연합을 만들 때 DFS/BFS 어느 방법으로 해도 상관없을것 같다. 나는 DFS를 사용하였다. side case에 걸리지 않고 한번에.. 2019. 5. 24.
[C++,구현] 백준 17143번 낚시왕 문제풀이 문제 링크 백준 17143번 낚시왕 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 코테에서 2문제 "완벽히" 풀 자신이 없다면 선택적으로 한문제 완벽히 맞추고 넘어가야 한다! 명심 또 명심! 1 2 3 4 5 6 7 8 9 10 11 12 13 14.. 2019. 4. 28.
[C++,구현] 백준 17144번 미세먼지 안녕! 문제풀이 문제링크 백준 17144번 미세먼지 안녕! 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 이문제 1솔 했다고 생각했는데 결과는 불합이었다...ㅜ 수행시간이 문제였던건가ㅜ 아쉽다. 좀더 실력을 갈고 닦자 지금 다시 풀어보니 백준에서는 통과가 .. 2019. 4. 25.
[C++,구현] 백준 14890번 경사로 문제풀이 문제 링크 백준 14890번 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 오늘 종일 고민한 문제이다. 다른일이랑 같이 하려니 정신이 분산되어 머리만 더 복잡해지는거 같다ㅜㅜ 앞으로 조용한 곳에서 단시간 집중하고 해치워야겠다. 아이디어가 생각 나지 않아 구현이 어려웠다. 찾아보니 핵심아이디어는 현재까지 연속된 높이의 계단수를 세는것! 아이디어를 얻어 완성한 후 한번 WA를 받았는데 조건에 계단의 높이가 1일 차이일때만 경사로를 설치할 수 있다는 조건이 있었다. 문제도 제대로 읽자..ㅜ 1 2 3 4 5 6 7 8 9 10 1.. 2019. 4. 6.
[C++,완탐] 백준 14500번 테트로미노 문제풀이 문제 링크 백준 14500번 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 완전탐색 문제이다. DFS 재귀방식으로 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24.. 2019. 3. 30.

티스토리툴바