728x90 프로그래밍43 [백준 시리즈] 13413번 : 실버 4 - 오셀로 재배치 / Python 제목 : 오셀로 재배출처 : 백준 / https://www.acmicpc.net/problem/13413사용 알고리즘 : 그리디문제 설명초기 상태목표 상태○●●○○○●○●○1. 오셀로 말의 앞면은 흰색이고 뒷면은 검정색이다.2. 말을 뒤집는 작업이나 두 말의 위치를 바꾸는 작업을 할 수 있다.3. 초기 상태와 목표 상태가 주어졌을 때 목표 상태에 도달하는 최소 작업의 수를 구하라. 제한시간 제한 : 2초메모리 제한 : 256 MB 입력테스트 케이스 수 T오셀로 말의 개수 N (1초기 상태 1줄목표 상태 1줄 출력입력받은 데이터에 대해 한 줄씩 결과 출력문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N의 최대 크기가 100,000이므로 O(NlogN) 이하의 알고리즘이 요구된다. 2단계 : 하나의 케이스.. 2024. 9. 5. [네트워크 시리즈] 네트워크란 무엇일까 : Network Overview 네트워크란 무엇일까목차1. 네트워크라는 용어의 의미2. 네트워크의 구성요소3. 네트워킹을 위해 사용되는 장비4. 네트워크 연결 구조와 데이터 전송 방식4-1. ISP5. 네트워크 성능 평가 척도6. 네트워크 보안네트워크라는 용어의 의미 컴퓨터 공학에서 네트워크는 컴퓨터 간 연결되어 자원과 정보를 공유하기 위해 구축된 연결망을 의미한다. 공유 주체와 공유 방법의 차이만 있을 뿐 사전적 의미와 다르지 않다.네트워크의 구성요소네트워크는 노드, 링크, 패킷, 프로토콜로 구성되어 있다. 1. 노드 : node자원과 정보를 공유하는 주체를 의미한다.동의어 : host, end point, access point, 단말 2. 회선 : link데이터가 전송되는 통로이다. 2-1) 회선의 소재광 섬유: fiber광통신.. 2024. 9. 5. [백준 시리즈] 14606번 : 실버4 - 피자 (Small) / Python 제목 : 피자 (Small)출처 : 백준 / 14606번: 피자 (Small) (acmicpc.net) 사용 알고리즘 : 다이나믹 프로그래밍문제 설명1. 식탁 위에 N ( 1 2. 식탁 위에 놓여있는 모든 피자판의 높이가 1이 될 때까지 둘로 나눈다.3. 탑을 둘로 나누는 행위에서 나누어진 두 탑의 높이의 곱만큼 즐거움을 얻는다고 할 때, 즐거움의 총합의 최댓값을 구해라. 제한시간 제한 : 1초메모리 제한 : 512 MB문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N의 크기가 10 이하이기 때문에 시간 복잡도 제한이 없다. 2단계 : 하나의 케이스에 대해 답을 어떻게 구할 수 있는가? X+Y = Z의 방정식을 가지는 X, Y에 대해서 X*Y는 X와 Y는 Z/2일 때 항상 최댓값을 가진다. 따라서, 탑.. 2024. 9. 3. [DB] 데이터베이스 개론 데이터 베이스여러 사람들이 공유하는 중앙화된 데이터 저장 공간 특징1. 실시간으로 접근할 수 있다.2. 실시간을 데이터가 변할 수 있다.3. 여러 사람들이 하나의 데이터를 동시에 접근할 수 있다.4. 내용 기반으로 참조가 가능해야 한다. 파일 시스템으로 DB를 만들면 안될까?파일 시스템은 우리가 일상에서 가장 많이 사용하는 데이터 베이스 형태이다. 하지만, 실무에서 파일 시스템 DB를 채택하기에는 무리가 있다. 1. 중복과 일관성 문제동일한 내용에 대해 여러 파일로 생성될 수 있으며, 동일한 데이터를 담고자 한 두 파일의 내용이 같을 것이라는 보장이 없다. 2. 어려운 데이터 접근각 파일의 데이터 저장 구조가 모두 동일할 것이라는 보장이 없기 때문에, 데이터 접근의 비용이 증가한다. 3. 무결성 문제데이.. 2024. 9. 2. [운영체제] Deadlock 들어가며Deadlock 현상은 Synchronization으로 인해 발생한다. Race Condition을 해결하기 위해 Synchronization이 필요하기 때문에, 우리는 Deadlock을 방지하고 해결할 수 있는 방법을 찾아야 한다. Deadlock서로가 서로에 의해 어느 프로세스도 실행되지 못하는 상황을 의미하며 한국어로는 교착 상태라고 한다. Dining Philosphier Problem을 떠올리면 된다. Deadlock의 성립 조건Mutual Exclusion : 공유 자원에 대해 한번에 하나의 프로세스만 접근한다.Hold and Wait : 자원을 쥐고있더라도 필요한 모든 자원을 얻은 후에 실행한다.No preemption : 스케쥴러에 의해 실행 권한을 빼앗기지 않는다.Circular .. 2024. 8. 14. [운영체제] Synchronization Examples 들어가며동기화가 필요한 상황에 동기화를 어떻게 적용했는지 알아봅시다.The Bounded-Buffer Problem (Producer-Consumer Problem)구성 요소N size buffer : 크기가 유한한 버퍼Producer thread : 버퍼에 데이터를 추가하는 쓰레드Consumer thread : 버퍼의 데이터를 소모하는 쓰레드 문제 상황버퍼가 비었을 때 Consumer thread가 데이터를 소모하려고 하거나, 버퍼가 가득 차있을 때 Producer thread가 데이터를 추가하는 것을 막아야 한다. 해결책당연한 이야기지만, 버퍼가 가득 차 있을 때는 Producer thread가 데이터를 추가하지 못하도록 막고, 버퍼가 비어있을 때는 Consumer thread가 데이터를 사용하지 못.. 2024. 8. 11. [운영체제] Synchronization 배경 지식Race Condition두 개 이상의 job이 Shared Memory의 데이터에 동시에 접근하여 실행 결과가 모호해지는 상태를 의미한다. 동시에 접근한다는 것의 의미프로그래머가 의도한 실행 절차가 끝나기 전에 해당 데이터를 사용하는 다른 코드가 중간에 실행되는 것을 의미한다.따라서 Race Condition은 Multicore 환경뿐만 아니라 Single-core 환경에서도 발생할 수 있다. 실행 순서가 보장되어 있지 않은 경우 모든 Shared Memory에 대해 Race Condition이 발생할 수 있다. Race Condition이 발생할 수 있는 Shared Memory 환경MultithreadIPC through shared MemoryKernel spaceSynchronizati.. 2024. 8. 2. [알고리즘 시리즈] 동적 계획법 : Dynamic Programming 동적 계획법 : Dynamic Programming목차1. 다이내믹 프로그래밍의 목적2. 다이나믹 프로그래밍의 적용 절차3. 다이나믹 프로그래밍의 적용 조건4. 다이나믹 프로그래밍이 적용된 형태5. 다이나믹 프로그래밍과 분할 정복의 차이점6. 다이나믹 프로그래밍을 적용한 대표적인 문제들1. 다이나믹 프로그래밍의 목적재계산을 피한다. 2. 다이나믹 프로그래밍의 적용 조건1) Optimal Substurcture부분 문제의 최적의 값으로 전체 문제의 최적의 값을 구할 수 있는가 2) Overlapping Subproblems동일한 부분문제가 반복해서 나타나는가 3. 다이나믹 프로그래밍의 적용 절차전체 문제를 부분 문제로 나눈다.부분 문제를 해결하고 결괏값을 저장한다.부분 문제의 답과 해결 방식을 이용하여 전.. 2024. 7. 31. [안드로이드] DataBinding을 위한 DataHolder 클래스들 들어가며안드로이드 개발에는 DataBinding을 위해 데이터의 변경을 관찰할 수 있는 다양한 자료구조를 제공하고 있습니다. 이를 Data Holder라고 하는데, LiveData, MutableState 등등 DataBinding 시 사용할 수 있는 데이터 홀더가 너무 많습니다. 이번 포스트에서 저와 같이 어떤 데이터 홀더가 있는지 알아보고, 무엇을 사용해야 할지 결정해 봅시다. Data Holder의 종류제가 찾아본 바로는 안드로이드에서 자주 사용하는 데이터 홀더 클래스는 LiveData, MutableLiveData, StateFlow, MutableStateFlow, MutableState가 있는 것 같았습니다. 데이터 홀더마다 개발된 맥락은 다르지만 모두 같은 역할을 수행하기 때문에 비교 우위가.. 2024. 7. 27. 이전 1 2 3 4 5 다음 728x90
