본문 바로가기

프로그래밍181

코드포스 블루, 삼성 SW역량 B형 정도의 실력을 갖기위한 공부방법 안경잡이 개발자님의 동영상을 참고하였다. 나는 이렇게 공부할 것이다. 1. 코드업에서 기초 100제를 품 (C++/Python) 2. 백준에서 그리디, 탐색, 기초 동적 프로그래밍 문제를 50개씩 품 (C++/Python) 3. 기출문제들을 품 (C++/Python) 참고 : 백준->삼성 기출문제 프로그래머스 -> 카카오 기출문제 2021. 3. 28.
[알고리즘] 최대 Subarray 찾기 아래와 같은 배열(집합)이 있다. 1 -3 2 4 -1 5 -3 이 배열의 부분집합중에, 합이 가장 큰 것은 무엇인가? 답은 2, 4, -1, 5 를 더한 10이다. 이것을 어떻게 빨리 구할 수 있을까? --------- 내가 생각한 방법은 이렇다. - 양수로 시작, 양수로 끝. 목록을 만들어보자면 이와 같다. 1, -3, 2, 4 2, 4, -1, 5 4, -1, 5 5 하지만 모두가 음수이거나, 양수이면? 음수일 때 : 최솟값 1개가 정답. 양수일 때 : 모든값을 더한것이 정답. 알고리즘 시간복잡도는 O(N^2)일 것이다. --------- 제시하는 알고리즘은 다음과 같다. Count 변수가 있다. Count 변수는 배열을 더해간다. 만약 Count 변수가 음수가 된다면, 0으로 초기화 한다. 이렇게.. 2021. 3. 26.
[알고리즘] 32비트에서 1인 비트를 세기 32비트 unsigned int에서 1인 비트는 몇개인가? ex) 0011 1000(56) -> 3개 1010 1010(170) -> 4개 Solution 1 : Shift 하면서, 한비트씩 확인. 너무나도 쉽게 생각할 수 있는 알고리즘이다. Shift한 값을 &연산을 하여 1이면 Count를 추가시키면 될 것이다. Solution 2 : x와 x-1을 And 함. 0이 될 때까지 아래는 x(56)을 x-1과 &연산한 과정이다. 1) 0011 1000 & 0011 0111 = 0011 0000 2) 0011 0000 & 0010 1111 = 0010 0000 3) 0010 0000 & 0001 1111 = 0000 0000 총 3번의 과정을 거쳐서, 비트가 1인게 3개 있다고 판단할 수 있다. Solut.. 2021. 3. 25.
[알고리즘] 혼자인 값 찾기 2N+1개의 값이 배열에 저장되어 있다. 단 하나의 값을 제외한 N개의 값들이 두번씩 나타난다. 한번만 나타나는 값은 무엇인가? 답 : 모든 값을 XOR했을 때 나온 값이 정답. 이유 : xor은, 비트연산으로 비트가 서로 다를 때 1이 된다. 하지만 같은 값들끼리는 비트도 당연히 같을 것이기 때문에 항상 0이다. 따라서 XOR값이 결국에는 다른 1개의 값만 남게 될 것이다. 2021. 3. 25.
[알고리즘] Linked list에서 Cycle 찾기 (잘못된부분 찾기) 보통 Linked list라는 것은, list들이 이어져서 만들어진다. Start list와, End list 사이의 list들이 서로서로의 주소를 가리키면서 이어져 있는데, 만약 어떠한 list의 가리키는 주소가, 다음 list가 아닌 이전 list라면, Linked list의 특성상 무한적으로 돌 수 밖에 없다. 이를 Cycle이라고 정의하겠다. 그렇다면 이 Cycle을 어떻게 발견을 하고, 수정을 할 것인가? 총 6개의 아이디어가 있다. 1. Linked Listd를 따라가면서 모든 주소를 배열에 저장. 그 후 정렬을 하며 같은 값이 있는지 확인. 이는 가장 흔하게 생각 할 수 있는 방법중 하나이다. 하지만 조금만 생각해보면 무한으로 도는 List에서, 어떻게 모든 주소를 배열에 저장하겠는가? 불가.. 2021. 3. 25.
[알고리즘] 달리기(Merge Sort를 활용) 자신보다 앞에서 달리고 있는 사람들 중 자신보다 실력이 낮은 사람은 몇명인가? - 입력 : 크기 N인 배열 A가 주어진다. A[1]은 현재 1등인 사람의 평소실력, A[2]은 현재 2등인 사람의 평소실력을 나타낸다. 문제 : 어떤 사람 A[i]보다 실력이 낮은 사람이, A[1] ~ A[i-1]에 몇명이나 있는가? ex) 1등 3 2등 4 3등 1 4등 2 5등 6 6등 8 7등 5 8등 9 9등 10 10등 7 Merge Sort를 이용한 접근방법. 잘게 쪼개어서, 합쳐지는 과정에 현재 숫자가 왼쪽에 N개보다 크면 N개를 저장. 이 사진과 같이 표현이 가능하다. 작은 숫자는 오른쪽에서 왼쪽으로 넘어가면서, 자신보다 큰 숫자를 만난경우 해주는 count 이다. 이렇게 한다면, 결과를 도출해낼 수 있다. 2021. 3. 24.

티스토리툴바