반응형 알고리즘27 [프로그래머스 고득점Kit] 전화번호목록(해시) - c++ 접근 처음에 문제를 보고 길이순으로 정렬한 다음에 비교하면 되겠다 라고 생각하고 코드를 짰다. 길이가 같으면 서로 같은 문자열은 없으므로 비교할 필요가 없으니 continue를 해주면 효율성을 충분히 고려하는거라고 생각했는데 정확성은 다 통과하지만 효율성 3, 4번을 통과하지 못했다. 오답코드 #include #include #include using namespace std; bool compare(string a, string b){ if(a.size()==b.size()){ return false; } else { return a.size() 2021. 9. 18. [Javascript]순열과 조합(Permutation & Combination) 순열(javascript) 처음 순열을 배운게 언제였더라. 중학생이었나 초등학생이었나. 고등학생때 까지는 순열과 조합을 자주 헷갈렸고 대학교에 오고 나서는 구분은 잘 하는데 공식을 맨날 까먹는다. 매번 공식을 검색하는것도 지긋지긋. 이번 정리를 계기로 다신 순열조합 문제를 풀 때 검색하는 일이 없었으면 하면서 시작하는 정리글. (춤추는개발자 님의 JavaScript로 순열과 조합 알고리즘 구현하기 포스팅을 참고했습니다.) 순열(Permutation) 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수. (네이버 두산백과) 굳이 예를 들자면 서로 다른 10가지 맛의 마카롱이 눈 앞에 있다. 하지만 마카롱의 칼로리는 어마무시하니까 우리는 이 중 4개만 먹을 것이다. 마카롱을 먹는 순서 또한 .. 2021. 9. 17. [프로그래머스 고득점Kit] 위장(해시) - Javascript 실제 조합을 일일히 구해서 계산하면 아마 통과하지 못할것이다. 처음에 조합으로 풀고 제출했더니 테케 1번이 오답이 떴고 질문하기를 가보니까 나같은 사람들이 우글대고있었다. 찾아보니까 훨씬 더 간단하게 해결할 수 있는 방법이 있었다. function solution(clothes) { var type = new Map(); var arr = []; var i=0; clothes.map((value, idx) => { if(type.get(value[1])===undefined){ arr[i]=2; type.set(value[1], i++) } else { arr[type.get(value[1])]+=1; } }) var answer = 1; arr.map(value => { answer*=value; }).. 2021. 9. 16. BOJ 4179 ) 불! (C++) 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net BFS로 풀리는 문젠데 예외 처리 하는 부분에서 미처 고려하지 못한 부분이 있어 좀 헤맸다. 1. 불의 이동경로에 대한 큐와 지훈이의 이동 경로에 대한 큐를 각각 만들어주고 입력을 받으면서 시작점들을 각 큐에 입력해준다. 그리고 지훈이의 이동 시간을 체크할 배열(dist)과 불의 이동 시간을 체크할 배열(burn)에 이동 가능한 좌표를 -1로 체크해준다. (따로 체크하지 않은 좌표는 0으로 초기화 되어 있으므로 추후 방문여부 체크 시 해당 좌표가 .. 2021. 7. 28. BOJ 1012 ) 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net DFS로 간단히 해결 할 수 있는 문제. 왠진 모르지만 예전에 풀려고 시도했다가 실패한 흔적이 남아있었다. 벡터를 이용해 밭의 크기를 런타임에 지정해주고 배추는 1로 표시한다. 방문여부는 배추가 없는 곳은 방문할 필요가 없으므로 기본은 모두 0으로, 배추가 있는 곳은 배추 위치를 표시하면서 같이 방문여부를 1로 변경해준다. 그 이후에는 반복문을 돌면서 배추가 심겨진 곳을 dfs로 탐색한다. 다음 칸을 방문할지 말지는 배추가 있는지와 방문한적이 없는지를 모두 고려해준다. #i.. 2021. 3. 12. BOJ 1003 ) 피보나치 함수 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 간단한 DP로 해결할 수 있는 문제다. '피보나치 + 제한시간이 짧음' 에서 바로 DP가 생각나서 그렇게 풀었다. 그냥 피보나치문제를 풀 수 있다면 어려움 없이 풀 수 있는 문제. #include #include #define pii pair #define x first #define y second using namespace std; int T,N; pii fib[42]; void makefib(){ fib[0]={1,0}; fib[1]={0,1}; for(int i=2;i>T; makefib(); while(T--){ cin>>N; cout 2021. 3. 12. 이전 1 2 3 4 5 다음 반응형
