공부하자

Symmetric Pairs | HackerRank Symmetric Pairs | HackerRank Write a query to output all symmetric pairs in ascending order by the value of X. www.hackerrank.com Advanced Join 문제다! 문제 이해하는데 시간이 좀 걸렸다. Symmetric Pairs는 어떤 함수 F에 대해 F(X1) = Y1, F(X2) = Y2 일 때, X1 = Y2이고 X2 = Y1인 두 항을 말한다. 즉 위의 함수에서는 (첫 번째, 두번째), (세 번째, 여섯 번째), (네 번째, 다섯 번째)의 세 쌍의 Symmetric Pairs가 나온다. 이때, 한 쌍 안에서 X 1 OR F1.X < F1.Y OR..

Placements | HackerRank Placements | HackerRank Write a query to output the names of those students whose best friends got offered a higher salary than them. www.hackerrank.com Advanced Join 문제이다! STUDENTS 테이블은 학생, FRIENDS 테이블은 그들의 가장 친한 친구, 그리고 PACKAGES에는 그들의 월급 정보가 저장돼 있다. 이때, 베프가 본인보다 월급이 높은 학생의 이름을 출력해야 한다. 왜 이런 자해 행위를... 우선 학생과 베프를 찾아야 하기 때문에, ID로 조인을 건다. 그리고 월급 정보가 들어있는 PACKAGES를 두 번 사용하여 ..

17281번: ⚾ (acmicpc.net) 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 시뮬레이션, 브루트포스 문제이다. 문제 설명은 현행 야구 규칙과 동일하다. 주어지는 이닝은 모두 공격일 때의 타자 정보이므로, 수비는 생각하지 않아도 된다. 문제 하단에 pypy3 1.5초라고 명시돼 있는 것이 매우 싸늘한 분위기를 자아낸다... 파이썬으로는 택도 없다는 소리이기 때문이다. 시간초과를 잡기 위해 처음 코드에서 다음과 같은 사항을 고쳤다. 진루 상황을 저장하는 변수: 정수 → 리스트 → 정수 하나의 타순에 대해 ..

13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 두 가지 방법으로 풀 수 있다! 다익스트라 (Heap, Priority Queue 활용) 0-1 BFS (Deque 활용) 다익스트라는 힙에서 다음 위치를 꺼낼 때 우선순위를 고려해야하므로, (걸린 시간, 위치)의 형태로 삽입을 하게 된다. 이에 반해 BFS는 가중치(수빈이가 다음 위치로 가는 데 걸리는 시간, 여기서는 0과 1뿐이다.)에 따라 큐에 삽입하는 위치를 달리해서 위의..

1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 문제 특정 출발점으로부터 특정 도착점까지의 최소비용을 묻고 있기 때문에, 하나의 출발점에 대한 비용행렬을 만들면 된다!! (1차원 행렬) 📢 주의해야 하는 점 방향 그래프이다!! (처음에 무방향 그래프라고 생각했다가 틀렸다...😥) 한 노드로부터 다른 노드로 가는 간선이 여러 개일 수 있다!! 예를 들어, 입력이 다음과 같이 주어지면, 1 2 3 1 2 10 비용이..

코딩테스트 연습 - 순위 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 처음에는 딕셔너리와 세트로 풀이했는데 시간 초과가 났다. (시초 안 나는 풀이도 있다!!) 기왕 문제 종류가 그래프인만큼 다른 풀이 방법을 떠올려 보려고 했지만 쉽지 않았다... 그런데 질문을 보니 어떤 천사분께서 플로이드-와샬을 써보라고 하신 것을 보고... 바로 풀렸다!! 플로이드-와샬 알고리즘은 원래 모든 노드로부터 다른 노드까지의 최단 거리를 저장하는 알고리즘이다. 이때, 전체 알고리즘은 삼중 반복문으로 수행되는데 다음과 같다. # n = 노드 개수 for k in range(n):# ..

코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 합승 택시 요금 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 그래프 문제 다익스트라와 플로이드-와샬 두 방법으로 풀 수 있다. 대부분 테스트 케이스에서 다익스..

20208번: 진우의 민트초코우유 (acmicpc.net) 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 백트래킹, 브루트포스 주어지는 보드 위에 장애물이 없기 때문에, 우유가 있는 위치까지의 맨하탄 거리를 계산하면 된다. 네 방향으로 탐색하는 알고리즘은 시간초과가 발생하게 된다. 아래와 같은 과정으로 풀이했다. 보드 상의 우유 위치를 리스트에 저장한다. 우유 리스트를 순회하며 다음 조건을 검사한다. 현재까지 마시지 않은 우유인가 현재 체력으로 도달할 수 있는 위치인가 두 조건을 만족하면 ..

코딩테스트 연습 - [1차] 셔틀버스 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 시뮬레이션 문제이다. 카카오에서는 이런 다중 조건을 만족시켜야 하는 문제가 꼭 출제되는 것 같다. 어떻게든 간단하게 풀어보려고 노력했으나... 아직 더 좋은 아이디어가 없으므로... timetable에 저장된 승객들의 도착 시간과 버스 도착 시간을 각각 deque에 넣었다. 두 개의 큐가 모두 빌 때까지 schecule이라는..