전체 글199 투 포인터 연속된 자연수의 합(백준 2018) 1.문제분석 자연수 N에 대해서 몇개의 연속된 자연수 합으로 나타낼 수 있는 가짓수 구하기 ex) N=15 -> 15, 7+8, 4+5+6, 1+2+3+4+5 총4개 N = 5 -> 5, 1+4(X), 2+3 총2개 시간제한 5초, N의 최댓값은 10,000,000으로 최소 O(N) 알고리즘으로 풀어야 함 2.문제풀이 예시1) N=3 일때의 가짓수 1.연속된 자연수 합을 계산할 SUM변수 (sum의 초기값은 1로 시작 N의 최솟값이 1이므로) 2.두 개의 포인터 사용 start_index sum이 N보다 큰 경우 오른쪽으로 한 칸 이동후 그 배열의 값에서 sum을 뺌 end_index sum이 N보다 작은 경우 오른쪽으로 한 칸씩 이동하면서 가리키는 배열의 값을 sum에 추가하면서 sum이 N과 동일하면.. 2024. 1. 16. 멀티쓰레드 Lock 구현 방식 1. SpinLock Lock을 얻기 위해 계속해서 Lock 획득을 할 때 까지 루프를 돌면서 수행하는 방식으로 하나의 쓰레드가 Lock을 오랜시간동안 점유하고 있다면 다른 쓰레드는 Lock을 획득하기 위해서 루프를 돌면서 Lock이 풀렸는지 계속 확인하므로 CPU에 부담이 가해진다. SpinLock 코드 using System; using System.Net; using System.Net.Sockets; using System.Text; using System.Threading; namespace ServerCore { class SpinLock { // volatile 키워드를 사용해서 가시성 역할 수행 volatile int _locked = 0; public void Acquire() { // .. 2024. 1. 15. 구간 합 구간 합은 합 배열을 이용하여 시간복잡도를 줄이기 위해 사용하는 알고리즘 1. 구간 합 구하는 방법 합 배열 구하기 공식 : S[i] = S[i - 1] + A[i] // 배열은 인덱스 0부터 시작하므로 크기를 한 칸 늘린 배열을 만들어서 첫번째부터 데이터가 담기도록 만듬 int[] A = {0, 1, 2, 3, 4, 5} int[] S = new int[A.length + 1] // 반복문을 1부터 A배열의 길이만큼 돌면서 합 배열 만듬 S[1] = S[0] + A[1] S[2] = S[1] + A[2] S[5] = S[4] + A[5] // 합 배열을 구할 공간을 따로 만들지 않고 기존에 배열에다가 합 배열 데이터를 덮어씌워도 됨 A[1] = A[0] + A[1] A[2] = A[1] + A[2] A.. 2024. 1. 9. 알고리즘 코테 준비 자료구조(배열, 리스트, 벡터) 배열 연속적인 메모리 공간에 값이 채워져 있는 자료구조 형태 특징 인덱스를 통해 값에 빠르게 접근 할 수 있다 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움 (배열의 마지막 인덱스 부근에서 삽입, 삭제를 하는게 아니라면 값을 이동시키는 과정이 너무 많아지기 때문에 속도가 엄청 느려짐) 배열의 크기는 선언시 지정하고 한 번 선언하면 크기를 늘리거나 줄일 수 없음 리스트 값과 포인터(주소)를 묶은 노드라는 것을 포인터로 연결한 자료구조 형태 특징 인덱스가 없으므로 해당 값에 접근하려면 Head 포인터부터 순서대로 접근해야 되므로 배열에 비해 접근 속도가 느림 데이터 삽입, 삭제 속도가 배열보다 빠름 크기를 지정할 필요가 없고 크기가 변하기 쉬운 데이터를 다룰 때 적절 포인터를 저장할 공간이.. 2024. 1. 7. 일반화(Generic) 일반화 프로그래밍이란? 특수한 개념으로부터 공통된 개념을 찾아 묶는 방법을 일반화라고 한다. 사람, 돼지, 고래, 오리너구리는 사는 곳이 다르다. 사람과 돼지는 땅 위에서 생활하고 고래는 물속에서 생활하고 오리너구리는 땅과 물 양쪽에서 생활한다. 번식 방법도 다른데 사람, 돼지,고래는 새끼를 낳지만 오리너구리는 알을 낳는다. 이렇게 각자 다른 특징을 갖는 동물이지만, 새끼에게 수유라는 것을 통해 양분을 공급하는 방식이 동일하므로 이들을 묶는 공통 개념을 포유류 라고 한다. 프로그래밍에서 일반화(Generic)는 데이터 형식을 의미한다. 만약에 제네릭을 사용하지 않고 데이터를 복사하는 메소드를 만든다고 했을 때 데이터의 타입이 달라지는 경우 그에 맞춰서 새로운 메소드를 만들어줘야 된다. using Syst.. 2023. 11. 11. C# Delegate(대리자) 대리자란? 상현이가 비서에게 사장님이 돌아오면 전화 해달라고 메모를 전달했다. 비서는 사장님 방에 상현이가 준 메모를 놓았고 사장님이 돌아와서 방에 있는 메모를 확인하고 상현이한테 전화한다. 메모를 비서에게 전달하는 행위는 상현이가 작성한 메모(callback)를 다른 코드에 맡겨 대신 실행하도록 요청하는 것이다. 사장님이 메모를 확인하고 상현이한테 전화를 하는 행위는 이벤트(callback)이 발생했다는 의미이다. C# 에서 callback을 맡아 실행하는 것을 대리자가 담당한다. 대리자는 해당 메소드를 참조하는 방식으로 대리자에 메소드의 주소를 할당한 후 대리자를 호출하면 이 대리자가 메소드를 호출한다. 대리자 사용방법 1. 대리자 선언 delegate [반환타입] 대리자이름 (매개변수 목록) del.. 2023. 11. 10. 이전 1 ··· 9 10 11 12 13 14 15 ··· 34 다음
