아무코딩

문제풀이 위상정렬 공부후 적용을 위해 푼 문제이다. 자료구조에서 위상정렬을 배울 때는 연결리스트를 만들어 사용하였지만. 벡터를 알고있으니 이차원 벡터를 사용한다. graph[from].push(to); input이 들어올때마다 저렇게 추가해준다. 그리고 to기준으로 indegree를 추가할때마다 1씩 증가시켜준다. indegree가 0인 것을 먼저 큐에 삽입한다. 하나씩 빼면서 출력하고 from이 가리키는 to의 indegree를 줄이고 연결도 지워나간다. (-> 위상정렬에서 삭제하는 과정) 계속 반복한다. 언제까지? 큐가 빌때까지 소스코드 더보기 w 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..

문제풀이 트라이를 이용한 문제이다. 실제 공채때는 이렇게 풀지 못해서 많이 효율성 부분에서 점수가 많이 깎였었다. 특이한 점은 ?가 있다는 점인데 트라이를 이용하기 좋게 접미사나 접두사로만 물음표가 주어진다. 자리수 별, 앞뒤 별 트라이 구조를 모두 만들어서 ?가 나오자마자 카운트를 반환하게 한다. 끝의 ?유무를 확인하여 reverse한 트라이를 쓸지 그냥 쓸지 정하면 된다. 소스코드 더보기 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 ..

문제풀이 그냥 회전을 시키면 시간초과가 나는문제이다. 인덱스와 food time을 포함한 구조체(food)를 만들어 정렬한뒤 food time이 낮은거 부터 삭제해나간다. food time 이 낮은수는 그다음 높은 food time 에서 빼가며 계산해 주는걸 잊어서는 안된다. 왜냐하면 그만큼은 다 돌았기 때문에 이러한 점을 고려하여 돌다가 차이만큼 뺄 수없을때 모듈러 연산을 진행한다. 말이 너무 복잡하니 코드를 보면 이해가 쉬울거 같다. ' accumulate는 누적된 시간이라 생각하면되고 spend는 한번에 넘길 턴? 한번에 소비할 시간이라 보면된다. 소스코드 더보기 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 2..

문제풀이 크게 문제풀이는 유일성을 확인 -> 유일성을 만족하는 것중 최소성을 만족하는것을 구하기 순으로 풀이하였습니다. 비트마스크를 이용하였고 비트마스크를 적용하니 이전보다 문제풀이가 훨씬 깔끔해졌습니다. 1. 유일성 확인방법 vector을 키로가지는 Set을 만들어 여러 경우의 키를 가지는 경우를 넣어서 set 의 사이즈가 레코드의 개수와 같을때 유일하다 판단합니다. 여기서 키로 선택된 칼럼은 비트로 1 아닌건 0으로해서 계산하는데 유일성이 만족되면 해당 값을 벡터에 저장합니다. 2. 최소성확인방법 유일성을 만족하는 벡터를 차례로 돌며 & 연산을 진행합니다. a == a&b 일때 a는 b의 부분집합입니다. 그래서 b는 최소성을 만족할수 없기때문에 제외시킵니다. 이와같은 방법으로 모두 비교하여 최소성을 ..

문제풀이 정렬하는 문제이다. 실패율이 같은 경우 번호 순서라서 이미 정렬된 상태라서 stable_sort를 이용하여 따로 번호정렬을 하지않았다. 소스코드 더보기 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 #include #include #include using namespace std; typedef struct Stage{ int num; int arrival; int not_clear; Stage(){} Stage(int n){ num = n; arrival = 0; not_clear = 0; } }Stage; v..

문제풀이 1. 스트링을 " "단위로 잘라준다. 2. 앞의 명령어에 따라 로그 벡터에 를 추가해주면된다. 3. 이름 변경이 가능하다 -> id를 키로가지고 이름을 값으로 가지는 map을 만들어 업데이트를 반영해준다. 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 #include #include #include #include #include using namespace std;..

문제풀이 핵심이되는 부분은 각 타임별 스타트 지점 끝지점을 기준으로 겹치는 부분을 확인하는 것이다. 중간에 포함이 될수도있고, 넘칠수도있고, 뒤만 걸칠수도있고, 앞만 들어갈수도있다. 모든 경우를 다 따져가는 코딩방식이다. 시작지점후 1초, 끝지점후 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 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..

문제풀이 새로운 STL을 많이 적용해 볼수 있는 문제였다. 교집합과 합집합을 구해 나누는 문제이다. 이전에 풀때는 함수를 사용하지 않고 직접 구현하였지만 이번엔 있는 stl을 활용해서 풀어보았다. 아래에 교집합 합집합 stl을 사용 하기전에 각 벡터는 정렬을 해주어야한다. 1. 교집합. vector inter_result; set_intersection(vecA.begin(), vecA.end(), vecB.begin(), vecB.end(), back_inserter(inter_result)); back_inserter를 이용하면 resize를 이용하여 미리 크기를 정해두지 않고 새로운 컨테이너에 삽입할 수 있다. 2. 합집합. vector union_result; set_union(vecA.begin..