[백준] 9576번 책 나눠주기 C++ 문제풀이

문제 풀이 이번 소마 1차 코테 4번 문제를 시간이 부족해 못풀었는데, 오픈채팅방에서 이분매칭이라는 알고리즘 관련된 문제라고 해서 이분매칭에 대해 공부도 할 겸 풀어보았다. "이분 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘입니다." - 나동빈 각 사람이 원하는 항목이 정해져 있을 때 모든 사람 각각이 원하는 항목을 하나씩 선택하여 가장 많이 연결되는 경우를 찾는 문제입니다. 위와 같이 A라는 집단에서 B라는 집단의 항목들에 대한 선호도가 있을 때, 어떻게 해야 A집단과 B집단을 연결할 수 있을까를 푸는 문제라고 생각하면 된다.. 문제를 푸는 방식은 맨 위의 사람부터 오른쪽 물건에 대해 연결한다 그리고 2번째 사람이 연결을 하려는데 1번 사람이 1번 물건을 점유하고 있으므로 1번에게 다른 ..

• format_list_bulleted 알고리즘
• · 2024. 2. 26.

[프로그래머스] 두 원 사이의 정수 쌍 C++ 문제풀이

문제 풀이 문제 풀이 자체는 그리 어렵지 않았다. 두 원 사이의 점이기 때문에 xy축 4분면에 동일한 점들이 생길것이다. 그러니깐 하나의 사분면을 구한 뒤 * 4를 해주면 되는 문제였다. for문을 통해 y를 하나씩 증가시키면서 x축상의 점의 갯수를 구했다. 그러나 테스트케이스 7,8,9,10에서 계속 실패해서 뭐지...? 하느라 시간이 오래걸렸다. 이유를 알고보니 y*y를 하는 과정에서 overflow가 발생한것이다. 이를 방지하기 위해 캐스팅이라는걸 사용했는데... 캐스팅이 뭐냐하면 int i = 10; long long c = i; // 묵시적 캐스트 long long c = (long long) i; // 명시적 캐스트 (c-style) 이런식으로 자료형 간 형변환시 사용되는 거라고 한다. (처음..

• format_list_bulleted 알고리즘
• · 2024. 2. 22.

[프로그래머스] 12세 이하인 여자 환자 목록 출력하기 SQL 문제풀이

문제 풀이 조건 1 : 전화번호가 없는 경우, 'NONE'으로 출력 NVL(컬럼, 값) Oracle SQL의 NVL 함수는 컬럼의 값이 Null인 경우 'NONE'으로 출력하게 한다. 다른 Null인값을 바꾸는 함수로는 NVL2함수가 있다. NVL2(expr1, expr2, expr3) NVL2 함수는 expr1이 널이 아닌 경우 expr2값 반환, expr1이 널인 경우 expr3 반환 조건 2 : 12세 이하인 여자환자 WHERE AGE

• format_list_bulleted 카테고리 없음
• · 2024. 2. 22.

[프로그래머스] 달리기 경주 C++ 문제풀이

문제 풀이 맨 처음에는 vector의 함수인 find, erase, insert 함수로 풀었는데, 정답은 나오지만 몇몇 테스트케이스에서 시간초과가 발생했다. 어떻게 시간초과를 줄일 수 있을까 고민해본 결과 내 코드에서 find하는 작업과 순서를 바꾸는 erase, insert 작업이 비효율적인 것을 알게 되었다. Player의 순서를 찾는 과정을 HashTable인 map을 이용해 O(1)로 바꾸고 순서를 바꿔주는 과정인 erase, Insert를 swap 함수를 통해 바꾸니 시간초과 없이 모든 테스트케이스를 통과할 수 있었다. 소스 코드 #include #include #include #include using namespace std; map myMap; vector solution(vector pl..

• format_list_bulleted 알고리즘
• · 2024. 2. 13.

[백준] 1753번 최단경로 구하기 C++ 문제풀이

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 풀이 출발점이 명시된 최소 간선 찾기 문제이므로 다익스트라를 이용해 문제를 해결했다. 다익스트라 설명은 이전 문제에 설명했으므로 생략한다. https://itcodeheaven.tistory.com/87 [백준] 1916번 최소비용 구하기 C++ 문제풀이 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 ..

• format_list_bulleted 알고리즘
• · 2024. 2. 4.

[백준] 1916번 최소비용 구하기 C++ 문제풀이

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이 최소 경로 찾기 문제에 자주 사용되는 알고리즘 2개가 있다. 1. 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 모든 정점들간의 최단거리를 계산하는 알고리즘으로 시간복잡도가 O(N^3) 으로 크다. 2. 다익스트라 알고리즘 다익스트라 알고리즘은 한 정점으로부터 다른 모든 정점까지의 최단거리를 계산하는 알고리즘으로 O(ElogV)로 훨씬 빠르다 이 문제..

• format_list_bulleted 알고리즘
• · 2024. 2. 4.