목록Algorithm (80)
DOTY
https://leetcode.com/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150처음 문제를 풀 때 단순히 배열에 넣어야겠다고 생각했지만 너무 많은 숫자를 다룰 수 있기에 다른 방법을 생각했다.class Solution {public: int majorityElement(vector& nums) { unordered_map elements; int max = 0, max_num = 0; for(int& i : nums) { elements[i]++; if(max unordered_map을 활용하면 삽입도 O(1), 탐색도 O(..
https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150나의 첫 코드는 이러했다.class Solution {public: int removeElement(vector& nums, int val) { int count = nums.size(); for(int i = 0; i 정답은 맞지만 해당 코드의 문제는 시간 복잡도.O(N^2)를 사용하게 된다.그 이유는 erase 함수. eraseerase 함수는 벡터의 원소를 삭제하는 것 까지는 좋지만 원소들을 하나씩 앞으로 당겨야하기 때문에 최악의 경우 O(N)의 복잡도를 가진다.따라서 시간을 단축시키기 위해서는 새로운 ..
4) LeetCode - Merge Sorted Array
Merge Sorted Array - LeetCode처음 사용해 보는 사이트로 프로그래머스처럼 내가 Input을 넣지 않아 줘도 좋다.그리고 Follow Up 이라는 추가 도전?이라는 것도 있는데 문제를 다 풀어도 더 생각하게 한다. class Solution {public: void merge(vector& nums1, int m, vector& nums2, int n) { int i = 0, j = 0; vector answer; while(i 원래 내가 생각했던 코드.어이쿠야....지금까지 제출한 사람들의 런타임과 메모리를 비교할 수 있다.class Solution {public: void merge(vector& nums1, int m, vector..
코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오랜만에 다익스트라 리마인드할 겸 풀었다. // 1. 다익스트라 사용 // 2. 구해야 할것 // 2-1. 처음부터 혼자 가는 비용 // 2-2. 중간까지 같이 갔다가 혼자 가는 비용 // 3. 2-1, 2-2 가장 작은 수 구하기 #include using namespace std; int vertex[201]; // 정점으로 부터의 비용 저장 vector dij[201]; // 그래프 저장 int INF = 400..
코딩테스트 연습 - 소수 찾기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 예외를 생각 못해서 오래 걸린 문제. #include using namespace std; int check_primNum[10000000] = {0, }; int check[7] = {0, }; string nums; int answer = 0; unordered_set s; void do_primNum(int N) { check_primNum[0] = 1; check_primNum[1] = 1; for(int i = 2..
2151번: 거울 설치 (acmicpc.net) 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net BFS로 푼 문제로 갔던곳은 또 방문 못하도록 해야한다고 생각했지만 반례를 찾아 수정 후 정답을 맞춘 문제 #include using namespace std; int main(void) { int N; int door_x, door_y; cin >> N; char map[50][50] = {0, }; // 0 : not arrive, 1 : arrive, 2 : mirror setting int ch..
1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분탐색을 활용한 문제. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; int num[100001] = {0, }; cin >> N; for(int i = 0; i > num[i]; ..
12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 혼자 해보려고 시도 했다가 시간만 많이 쓴 문제 // DP - Knapsack #include using namespace std; int bag[101][100001] = {0, }; pair object[101]; int main(void) { int N, K, W, V; cin >> N >> K; for(int i = 1; i > W >> V..
2206번: 벽 부수고 이동하기 (acmicpc.net) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 초반에는 벽 부수는 것 때문에 난감했던 문제 #include using namespace std; int x_p[4] = {0, 0, 1, -1}; int y_p[4] = {1, -1, 0, 0}; char maze[1000][1000] = {0, }; // first : length, second : wall_check - 한번도 안지났으면 0, 부쉈으면 1 pair check[..