프로그래머스/고득점키트/해시/위장 https://programmers.co.kr/learn/courses/30/lessons/42578 알고리즘 연습 - 위장 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 약간의 경우의 수의 계산에 대한 센스가 필요한 문제다. 우선 알고리즘 설계는, 각 clothes의 벡터내 string vector 원소에 대하여, 두 번째 값인 의상의 종류를 key값으로 갖는 unordered_map 을 만들어서 푼다. 이 때 value는 key값이 나올 때마다 map[key] ++; 로 1씩 증가시켜준다면, 의상의 종류 별로 몇 개를 갖고 있는지(value)를 정리할 수 있다. 여기서 answer = 1로 수정한 뒤, 각 의상 종류별로 (의상 갯수 + 1) 를 곱해준다. (기본적으로.. 프로그래머스/고득점키트/해시/전화번호목록 https://programmers.co.kr/learn/courses/30/lessons/42577 알고리즘 연습 - 전화번호 목록 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 해시 두 번째 문제이다. 전화번호 목록의 어떤 번호가 하나라도 목록내의 다른 번호의 접두사가 된다면, (즉 어떤 번호의 전체가 다른 번호의 앞 전체가 되는 것이다.) false를 리턴해주고, 그게 아니면 true를 리턴해주면 된다. 해시를 쓴다기보단.. 아래와 같이 알고리즘을 설계하였다. 1. 먼저 phone_book을 오름차순으로 sorting하자. 이렇게 한다면, phone_book의 크기를 순회하면서 인접 원소끼리 접두사가 되는지 확인하면 문제 해결을 할 수 있을 것이다. [구현코드] #.. 프로그래머스/고득점키트/해시/완주하지못한선수 #include #include #include #include using namespace std; string solution(vector participant, vector completion) { string answer = ""; unordered_map map; //참여한 선수의 순회 for(auto& i: participant){ map[i]++; } //완주한 선수의 순회 for(auto& i: completion){ map[i]--; } // 다시 참여자를 순회하여, map[i] > 0보다 큰 경우는 Completion되지 않고 남은 선수로 생각하여 답 출력 for(auto& i: participant){ if(map[i] > 0){ answer = i; break; } } return .. 프로그래머스/고득점키트/BFS/DFS/단어변환 오늘 날씨가 좋다. 문제 풀기 좋은 날씨다. https://programmers.co.kr/learn/courses/30/lessons/43163 알고리즘 연습 - 단어 변환 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 해당 문제는 DFS, or BFS를 활용하는 문제다. Words 의 각 원소 Node 들을 서로 변형이 가능한(간선으로 연결이 가능한) Node끼리 이어 붙여서, 시작 단어를 기점으로 DFS or BFS탐색을 해준 뒤, 찾고자하는 타겟 단어를 먼저 탐색하였는지 판별하고, 타겟 단어가 탐색되었으면 시작점으로부터 떨어진 거리를 반환해준다. 말은 쉬운데, Node가 string형태로 와있는게 참 생소해서 구현에 어려움을 겪을 수 있다. 이해한다. 아래와 같이.. 백준온라인저지(BOJ)/#7562/나이트의이동/BFS https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net 기존의 2차원 좌표에서 BFS, DFS를 할 때 상하좌우 좌표에서 확장하여 생각할 수 있다. 위의 그림과 같이 체스 위의 나이트는 .. 백준온라인저지(BOJ)/#7576/BFS/토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 토마토 문제이다. 토마토는 처음에 특정 좌표만 익어있고, 이후 하루 지날 때마다 익은 토마토를 기점으로 인접 좌표의 토마토들로 익은 것이 .. 백준온라인저지(BOJ)/#2644/촌수계산/BFS https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대 www.acmicpc.net 간선으로 이어진 노드간 거리를 측정하기 위해선 BFS가 효과적이다. 측정하고자 하는 시작 노드(Start)와 도착지점 노드(Target).. 프로그래머스/고득점문제키트/탐욕법(Greedy)/구명보트 #include #include #include using namespace std; int solution(vector people, int limit) { int answer = 0; sort(people.begin(), people.end()); int light_idx = 0; int heavy_idx = people.size()-1; int double_cnt = 0; //light_idx 가 heavy_idx와 같아지는 순간은 나오도록 한다. //어차피 double_cnt 만 헤아리면 되기 때문이다. while (light_idx < heavy_idx){ if(people[light_idx]+people[heavy_idx] 이전 1 ··· 6 7 8 9 10 11 다음 목록 더보기
