분류 전체보기 (108) 썸네일형 리스트형 2021 프로그래머스 데브매칭 웹 백엔드 개발자 챌린지 (하반기) 후기 이직을 하려는 건 아니고 요즘 알고리즘 많이 풀어서 실력 체크 삼아 프로그래머스 웹 백엔드 개발자 챌린지에 참여하였다 상반기꺼는 참여는 못하고 나중에 올라온 문제만 풀어봤었는데 이번에는 운좋게 시간이 괜찮았다 4문제를 푸는데 1시간 30분 정도 걸렸고 저번 상반기보다는 어려웠던 것 같다 1번은 1번이니까~하고 대충풀려다가 시간초과 날 것 같아서 map을 사용했다 나중에 들어보니 진짜 대충 풀면 시간초과 났다고 한다ㅋㅋㅋ 2번은 시간복잡도 계산해보니 괜찮을 것 같아서 완탐으루ㅎㅎ 3번은 삼성 코테 준비하면서 비슷한 문제를 풀어봤어서 금방 풀 수 있었다 ( 백준 모노미노도미노 2 20061번) sql을 풀 때 문제 설명에 나온 예시와 똑같이 만들어야 하는줄 알고 10분정도 날려서 아쉬웠다 이런 메일이 왔는데.. [C++] 가장 가까운 두 점 백준 2261번이다 직무 교육 들으면서 추가로 풀어보았던 문제 solved ac 플레 3이라는 꽤나 높은 난이도의 문제였다 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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 #include #include #include #include #include #define ll long long using namespace std; typedef struct pair pii; pii points.. [SWEA] 균형점 처음에는 방정식을 푸는 문제인 줄 알았지만 식을 좀 써보니 계산용이 아니라 그냥 오차범위 내의 값을 찾는 것 같았다 parametric search를 이용해 풀어야겠다는 생각이 들었다 이 때 범위를 구해주어야 하는데 뭔가 각 점들의 사이이지 않을까 하는 생각이 들어서 input을 까봤다 SW 아카데미는 인풋, 아웃풋을 많이 알려줘서 좋다ㅎㅎ.. 안좋은 습관 고쳐야하는데... 아무튼!! input, output을 까봤더니 정말 각 점들의 사이가 답이었다 이유는 조금 더 생각해봐야 할 것 같다 각 점들의 사이를 범위로 주고 parametric search를 통해 오차범위 내의 답을 구해보았다 모든 자성체에서 동일한 G와 균형점의 무게가 될 m1은 무시했다 코드에 문제가 없어 보였지만 왜인지 모르게 segme.. [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. 벽이 있고 아직 벽을 부수지 않았다 이때 벽을 부순 칸을 다시 방문하는 것은 최단 경로가 아닌것이 .. 이전 1 2 3 4 5 6 ··· 14 다음
