알고리즘_개념 및 문제풀이 (42) 썸네일형 리스트형 프로그래머스/윈터코딩2018기출/쿠키구입/C++ https://programmers.co.kr/learn/courses/30/lessons/49995 알고리즘 연습 - 쿠키 구입 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr m번째 바구니를 기준(시작점)으로 두 아들이 m번째 바구니부터 각각 좌우로 순회하면서 쿠키 갯수를 서로 더해가면서 양아들의 쿠키갯수가 같아지면서 동시에 이것이 최대값일 경우 max값을 갱신해주는 방식으로 코드를 구현할 수 있다. 시간 초과가 걸리는 문제가 있는데, 중간에 주석으로 달아놓은 설명대로 break를 사용하여 불필요한 순회를 하지 않는다면, 효율성 테스트 케이스 부분까지 모두 통과할 수 있다. [구현코드_C++로 구현] #include #include #include using names.. 프로그래머스/윈터코딩2018기출/방문길이/해시를 이용한 풀이/C++ https://programmers.co.kr/learn/courses/30/lessons/49994 알고리즘 연습 - 방문 길이 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 내 기준으로는 호락호락하지 않은 문제다. 핵심은 단순 경로가 아니고, 중복되지 않은 '경로 궤적'의 길이를 구해야 한다는 점이다. 이를 구현하기 위해 한 점에서 이동을 할 때 시작점 -> 도착점, 도착점->시작점 이 두 가지 경로에 대해 방문이 되지 않은 경우만, 경로의 길이에 합산하였다. 그리고, 굳이 -5~5값을 갖는 범위로 하지 않고, 0~10 까지의 좌표를 갖는 좌표계로 옮겨서 생각하였다 (그럼 시작점도 0,0 에서 5,5로 이동될 것이다.) 저 시작점 -> 도착점, 도착점->시작점은 ma.. 프로그래머스/윈터코팅2018/스킬트리 https://programmers.co.kr/learn/courses/30/lessons/49993 알고리즘 연습 - 스킬트리 | 프로그래머스 실행 결과가 여기에 표시됩니다. programmers.co.kr 드디어 프로그래머스 코딩테스트에 나왔던 기출문제를 건드리고 있다. 이 문제는 각 skill_trees 원소의 string을 차례로 탐색하면서 핵심 skill에 해당하는 char가 있으면 이를 차례대로 queue에 집어 넣었다가, queue에서 다시 한개씩 꺼내서 q의 사이즈만큼 순회하면서 핵심 스킬의 앞부분과 하나씩 비교하는 방식으로 가능한 스킬트리인지를 확인하였다. 아직, 그래프의 위상정렬은 익숙하지 않기 때문에 queue의 특성을 이용하여 풀어보고자 하였는데, 간신히 통과하였다 .. (공부가 많.. 프로그래머스/고득점키트/해시/위장 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를 할 때 상하좌우 좌표에서 확장하여 생각할 수 있다. 위의 그림과 같이 체스 위의 나이트는 .. 이전 1 2 3 4 5 6 다음
