본문 바로가기

분류 전체보기

 (99)
[백준] 9576번 책 나눠주기 C++ 문제풀이 문제 풀이 이번 소마 1차 코테 4번 문제를 시간이 부족해 못풀었는데, 오픈채팅방에서 이분매칭이라는 알고리즘 관련된 문제라고 해서 이분매칭에 대해 공부도 할 겸 풀어보았다. "이분 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘입니다." - 나동빈 각 사람이 원하는 항목이 정해져 있을 때 모든 사람 각각이 원하는 항목을 하나씩 선택하여 가장 많이 연결되는 경우를 찾는 문제입니다. 위와 같이 A라는 집단에서 B라는 집단의 항목들에 대한 선호도가 있을 때, 어떻게 해야 A집단과 B집단을 연결할 수 있을까를 푸는 문제라고 생각하면 된다.. 문제를 푸는 방식은 맨 위의 사람부터 오른쪽 물건에 대해 연결한다 그리고 2번째 사람이 연결을 하려는데 1번 사람이 1번 물건을 점유하고 있으므로 1번에게 다른 ..
[프로그래머스] 두 원 사이의 정수 쌍 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) 이런식으로 자료형 간 형변환시 사용되는 거라고 한다. (처음..
[프로그래머스] 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
[프로그래머스] 달리기 경주 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..
[백준] 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번: 최소비용 구하기 첫째 ..
[백준] 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)로 훨씬 빠르다 이 문제..
[백준] 16236번 아기 상어 C++ 문제풀이 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 시뮬레이션 관련해서 구현을 해본 적이 없어 많이 고민했다. BFS를 이용해서 푸는 건 알겠는데, 디테일한 작은 부분부분에서 계속 틀리더라... 풀이는 1) 현재 상어의 위치에서 가장 먼저 1마리를 먹을때까지 BFS를 수행 -> 만약 여러 마리를 먹을 수 있는 경우는 맨 위, 맨 위에서도 맨 왼쪽에 있는 물고기를 먹는다. 2) 1마리를 먹으면 BFS를 종료 후 다시 상어의 위치에서..
[백준] 1766번 문제집 C++ 문제풀이 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 풀이 전형적인 위상정렬 문제다. 위상정렬이란 순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정하는 알고리즘이다. 여기서는 고려해야하는 순서는 2가지였다. 첫 번째는 '먼저 푸는 것이 좋은 문제'의 경우에는 먼저 풀어야한다. 두 번째는 문제집 번호가 낮은 번호부터 큰 번호 순서로 진행되어야 한다. 이 두가지를 고려해 queue에 진입차수가 0인 문제가 하나..

티스토리툴바