전체 글

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net [문제] [풀이] x => y => ... 로 가는 간선이 있을 때 , x 를 넘어뜨리면 이와 연결된 모든 도미노가 넘어간다. 즉 , inDegree 가 0인 부분을 선택해서 카운팅 해줘야 하는 문제이다. 그런데 만약 사이클이 있는 경우는 inDegree를 정의하기가 어렵기 때문에 사이클이 있는부분은 어느 하나만 건드리면 나머지도 다 넘어지기 때문에 이 사이클을 하나의 노드로 봐야 한다. 그래서 SCC (강한 결..

https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net [문제] [풀이] 다익스트라 응용해서 풀었다. 1. 최단거리 알고리즘인 다익스트라의 조건을 최장거리로 변형시켜서 distance 설정 2. 도착지에서 distance[cur]-cost = distance[next] 의 조건을 만족하는 노드를 찾아가며 역추적 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

https://programmers.co.kr/learn/courses/30/lessons/81302#fnref1 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr [풀이] 2차원 map을 만들어서 P 와 P 사이의 거리가 2이하인 것을 발견..

https://programmers.co.kr/learn/courses/30/lessons/72412

https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr [문제] [풀이] 탐색+조합+정렬 문제이다 .. 주문마다 구할수 있는 모든 조합을 course의 개수에 맞춰서 뽑아낸다. 그런다음 제일 많이 뽑힌 조합을 카운트해서 리턴 하면된다. menuMap 로 나온 모든 조합을 다 집어 넣는다. resultMap 로 제일 많이 나온 메뉴의 카운트가 몇개 인지 카운팅해서 넣는다. 그런다음 me..

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr [문제] [풀이] 처음에 두 가지 방법을 떠올렷다. 1. 플로이드 와샬 2. 다익스..

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr [문제] [풀이] 트리구조로 짜여진 다단계 구조에서 자기가 수익을내면 10%는 부모에게 올라가고 부모도 그 부모에게 10%가 올라가는 방식이다. 처음엔 단순 dfs 로 하려고 했다가 실패했다 .. 한 사람이 두 번 이상 판매해서 수익을 발생시키고 그 수익금을 합쳐서 올리는게 아니라 따로따로 계산해서 1원미만 단위가 나오면 취급하지 않기 때문인데 .. 이게 ..

https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net [문제] [풀이] 평범한 이진트리 만드는 문제이다. 하지만 시간제한과 메모리에 비해 주어지는 N을 보니 곱해 통과하지 않을듯 하다 .. 결국 시간초과 왜 ..? 보통 노드의 수를 N이라고하면 탐색하는데 걸리는시간은 O(logN)이다. 하지만 만약 연속된 수만 나와서 편향된 트리가 만들어진다면 .. ? => O(N) 편향된 트리가 되지 않게하기 위한 균형잡힌 트리가 있다. => Red-blac..