알고리즘 (55) 썸네일형 리스트형 [SWEA] 소수 완제품 확률 삼성 SW 아카데미 1266번 소수 완제품 확률 확률과 통계에 대한 기본 개념이 있어야 풀 수 있는 문제였던 것 같다 두 가구 장인이 만든 완제품의 수가 최소 한 명이라도 소수일 확률은 1 - 둘다 소수가 아닐 확률이라는 점을 먼저 생각해보았다 A,B는 독립시행이므로 둘다 소수가 아닐 확률은 A가 소수가 아닐 확률 * B가 소수가 아닐 확률이다 장인이 만든 완제품이 소수가 아닐 확률을 구하기 위해서 not prime 배열을 선언해 18이하의 소수가 아닌 수들을 모아보았다 완제품을 만들 수 있는 확률이 p일 때 18개중 n개의 완제품을 만들기 위해서는 $ C(n,r) \times (p^n) \times ((1-p)^(18-n)) $을 계산해주면 된다 combination 값을 몇개만 쓰기때문에 매번 구하는.. [C++] 개미굴 백준 14725번 삼성 프로를 따기 위해 다시 알고리즘을 열심히 해야겠다 아직 수업을 안들어서 뭘 할까 하다가 백준 알고리즘 분류에서 내가 좋아하는 트라이를 골라서 풀어봤다 이 문제는 개미들이 타고 내려간 정보를 보고 개미굴의 전체 모습을 파악하는 문제 전형적인 트라이라기 보다는 트라이를 알면 쉽게 풀 수 있는 문제였던 것 같다 map과 vector를 사용하면서 프로 시험에 이제 stl 허용인것이 행복했다 노드별로 string을 키로 갖고 노드 포인터를 value로 갖는 map을 만들어주었다 로봇개미가 찾은 경로는 insert 함수를 재귀적으로 불러 차례차례 넣어주었다 이때 이미 한 번 이상 찾은 경로는 map에서 찾아서, 처음 가는 경로는 새로운 노드를 만들어 재귀함수를 불렀다 출력 또한 재귀적으로 함.. [C++] 특정한 최단 경로 백준 1504번 다익스트라를 응용한 문제였다 최단 경로는 경로인데 특정한 두 지점을 꼭 지나간 최단 경로 찾기 따라서 최단 경로를 저장하는 배열을 한 지점만 들른 경우, 두 지점 모두 들른 경우 나누어서 만들어주었다 예전에 비슷한 문제를 푼 적 있어서 dist 배열을 다차원 배열로 status 별로 나누는 것은 금방했지만 조건 체크에서 실수를 해서 몇번 틀렸다 꼭 들러야하는 점이 1인 경우 시작점이 1이라 자동적으로 들르게되지만 처음의 코드에서는 해당 케이스를 잡지 못했다 start status를 만들어 시작점이 1인 경우를 따로 체크해주었더니 정답처리되었다 최단 경로를 상황별로 나누어 저장하는 것과 시작점이 특정 지점인 경우만 체크해주면 될 듯한 문제! 1 2 3 4 5 6 7 8 9 10 11 12 .. [C++] 최소비용 구하기2 백준 11779번 다익스트라로 풀어본 최소비용 구하기 문제 가장 기본적인 다익스트라는 거리(비용)만 구하는데 경로까지 구해야 하는 문제였다 경로를 우선순위큐에 vector로 다 넣어주었는데 간단하게 풀고싶어서 그렇게 풀긴 했지만 좋은 풀이는 아닌 것 같다 메모리를 줄이기 위해 다른 풀이가 있는지 찾아보았더니 특정점 a를 가기 위한 최적 경로가 b를 통해서라면 route[a] = b와 같이 저장해서 쓰는 방법이 있었다 이렇게하면 모든 경로를 벡터로 갖지 않아도 역추적이 가능하다 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 44 45 46 .. [C++] 벽 부수고 이동하기 백준 2206번 solved ac 클래스 3이 끝나서 클래스 4 문제들을 풀기 시작했다 한참 많이 풀었던 bfs 유형이라 금방 풀 수 있었다 먼저 문제에서 요구하는 최단경로라는 키워드를 통해 bfs를 쓰면 되겠다고 판단했다 그 다음 벽을 단 한번만 부술 수 있으니 벽을 이미 부순 상태인지, 앞으로 부술 수 있는지만 나누어주었다 visit 배열 또한 벽을 부순 상태로 방문한 것인지, 부수지 않고 방문했는지 따로 저장했다 반복문 안에서의 조건은 아래와 같이 세가지로 나누었다 1. 벽도 없고 방문한 적도 없으며 앞으로 벽을 부술 수 있다 2. 벽이 없고 이미 벽을 부수었고 벽을 부순 상태로는 처음 방문한다 3. 벽이 있고 아직 벽을 부수지 않았다 이때 벽을 부순 칸을 다시 방문하는 것은 최단 경로가 아닌것이 .. [C++] 리모컨 백준 1107번 dfs로 문자열을 열심히 만들다가 뭔가 이상하다는 느낌이 들어서 방법을 고쳤다 처음 생각한 방법은 문제에 있는 예시처럼 5457이면 먼저 5를 쓸수 있는지 확인해서 5, 그다음 54, 545, 5455 이런식으로 문자열을 늘려갔다 하지만 999와 같은 경우는 1000 - 1이 유리한데 내 방식은 찾지 못할 것 같았다 예외 처리를 해주기에는 이런 상황이 너무 많을 수 있다는 생각이 들어 제한 조건을 다시 살펴보았다 채널은 총 500000개이고 한 문자열을 만들 수 있는지 없는지 확인하는데에는 최대 6밖에 들지 않았다 따라서 만들 수 있는 전체 문자열을 확인하는것이 예외처리도 없고 간편하겠다는 생각이 들었다 다만 입력으로 들어오는 채널은 500000이하이지만 500001 - 1 이런식으로 만.. [C] Z 백준 1074번 solved ac 클래스 문제를 전부 풀어보기를 시작했다 재귀를 이용하여 풀었던 Z 문제 풀면서 예전에 Icpc 기출인 philosopher's walk 문제의 쉬운버전이라고 느껴졌다 문제는 오랜만에 알고리즘을 다시 해서 그런가 long long 신경안써서 overflow 일어난 것과 부등호 부주의 했던 점ㅠㅠ 바빠도 일주일에 몇문제씩은 꼭 풀어야지 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 #include #include long long int dfs(long long int N, int r, int c){ if(N==2){ if(r==0 && c==0) return 0; else if(r==0 && c==1).. [프로그래머스] 2021 Dev-matching : 웹 백엔드 개발자 풀이 데브매칭 문제가 공개되었길래 풀어보았다 이 날 라인 코테였나...? 날짜가 겹쳐서 하나만 나가느라 데브매칭은 신청 못했는데 문제가 공개되다니!! 1. 로또의 최고 순위와 최저 순위 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 #include #include using namespace std; int get_rank(int i){ if(i>=6) return 1; else if(i==5) return 2; else if(i==4) return 3; else if(i==3) return 4; else if(i==2) return 5; else return 6; } vector solution.. 이전 1 2 3 4 5 ··· 7 다음
