전체 글80 [Baekjoon - 22862] 가장 긴 짝수 연속한 부분 수열 (large) with Python 주저리 주저리 투 포인터 문제 중 대표적인 문제 중 하나라고 생각한다. 이런 유형의 문제는 꼭 풀어봐야 생각하는게, 만약 코테에 이런 문제가 나올 시 이것이 투포인터 인지 아닌지 애매해서 못 풀수도 있을 거 같다라는 생각을 든다. 다들 알다시피 투 포인터는 대충 두 점을 같은 위치에서 시작하느냐 or 양 끝으로 시작하느냐의 문제가 대부분인 듯 하다. 난 개인적으로 같은 위치에서 시작을 하는 경우는 이제 특정 조건에 만족하는 길이를 구할때의 문제에 적용하고, 양 끝은 이제 양 끝에서 부터 접근해서 풀면 쉬울것 같다(?) 라고 판단시에 푸는 듯 한다. 문제 해결 이 문제는 k개의 원소를 지워 가장 긴 짝수 의 수열을 만드는 것이다. 그럼 당연하게도... 지우는 원소는 뭐가 되겠는가 => 홀수다 그래서 이 문.. 2023. 4. 25. 세마포어 vs 뮤텍스 참고 영상 우아한테크의 10분 테코톡 와일더의 Mutex vs Semaphore를 보고 정리해 보았습니다. 아래 영상은 꼭 봐주세요! https://www.youtube.com/watch?v=oazGbhBCOfU 사전 지식 교착 상태 두가지 이상의 작업이 서로 상대방의 작업이 끝나기를 하염없이 기다리는 상태 예를 들어 A, B가 존재하고, 각각 연필과 종이를 가져갔다 가정해보자. (점유) 그러나 필기를 위해서는 둘다 필요하니 A와 B는 각각 종이와 연필을 요청한다.(대기) 당연히 A, B는 필기를 위해 줄 수 없으니 자원을 요청하지만 이 요청을 무한히 대기하는 상태를 교착상태라한다. 연필과 종이는 공유자원이라 한다. 이런 공유 자원이 속해 있는 공간은 임계영역이라 한다 임계 영역 : 교착 상태가 발생 가.. 2023. 4. 3. 23032 - 서프라이즈~ with Python 주저리 주저리 맞춘 사람 43명 안에 든 행복이 든다? 문제는 두 그룹을 만들고, 그 그룹들의 무게 합의 차가 제일 작게한다. 대신 그룹원들은 서로 번호가 연속되어야한다... 고민이 많이 필요한 문제였다. 문제 해결 일단 이 문제에선 중요한 것은 그룹을 만들고, 그 들의 스테이크의 합의 차가 제일 작게 만들어야 한다. 따라서 그룹을 만드는 것이 제일 중요하다 볼 수 있다. 생각해보자 그룹을 만드는데 겨우 2그룹만 만들것이다. 그럼 간단하게 중간을 기준으로 삼아 그룹을 나누면 된다. 즉 mid값으로 시작해 1~n까지 돌면서 mid의 왼쪽과 오른쪽으로 그룹을 나누어 주면 된다. 여기서 중요한 점이 누적합 개념이다. 만약 그냥 저 그룹만 나누고 sum이런 것을 이용해 합을 구하면 시간 초과이다. (당연히도) .. 2023. 3. 30. 17609 - 회문 with Python 주저리 주저리 이 문제를 보자마자 그대로 문자를 뒤집어서 계산하는 것은 안 될까 싶었다. 하지만 유사 회문 덕에 모든 문자열을 탐색해야 함으로 O(n**2)이 걸릴 거라 생각하고 한번 짜봤는데, 역시 시간 초과... 당연히 다른 접근으로 접근해보자 문제 해결 회문을 탐색하는 방법으로는 그냥 맨 앞과 맨 뒤에 포인터를 두고 만약 두개의 포인터가 가리키는 문자가 서로 같으면 한 칸씩 움직이는 아주 간단한 방법이 존재한다. 다만 여기서는 유사 회문이 존재한다. 따라서 그냥 만약 다르다! 그러면 왼쪽과 오른쪽 둘 중 한 곳만 움직이게 해서 그 다음을 체크하면 될 것이다. 한번 코드로 직접 보면 더 이해가 쉽게 간다. 코드 import sys input = sys.stdin.readline t = int(inpu.. 2023. 3. 30. 이전 1 ··· 4 5 6 7 8 9 10 ··· 20 다음 728x90