lee-soo 님의 블로그

우선순위 큐 정말 bfs나 dfs에서 많이쓰이는 자료구조죠? 특히 queue에 들어온 값 들 내부에서 정렬이 자동으로 되는 구조입니다. 추가나 제거가 lg n의 시간복잡도가 걸린다는 것만 아시고 넘어가볼게요 대부분의 이론적인 내용은 깊게 설명하면 오래걸립니다 ㅠ. 문제 푸는덴 크게 상관이 없고, 컴공학과를 나오셨다면 아마 자료구조 시간에 들어보셨을 구조입니다. 사실 앞선 set과 우선순위큐를 사용하라면 차라리 set을 사용하는게 더 편하지 않나 생각도 들지만뭐.시간이 더빠릅니다 공간효율도 좋고요 백문이불여일견 문제를 풀어봅시다https://www.acmicpc.net/problem/11286 문제는 쉽죠 x가 0이면 출력, 0이아니면 값을 넣어요 근데 연산의 개수가 10만개군요? 10만개라 뭐... 흠 ..

다들 머릿속에 떠오르는 기억이 있을겁니다.. 저는 뭐 대학생때 이진 트리에 대한 삽입과 삭제에 대한 원리를 배우면서 머리가 터질 뻔 했지만 저희는 STL을 간단하게 쓸 겁니다 렛츠고 이진 검색 트리의 한 종류 set, mulitset,map 어? 해쉬때 배운거에서 unordered만 빠졌군요 외우기 훨씬 쉽겠다가봅시다 이진 검색 트리는 원소를 삽입 및 삭제시 균형( sort 같은 )이 자동으로 맞춰집니다. 그래서 언제 시작을 하든 뭐든 다 정렬된 것이라는 것을 아셔야 합니다. 해당 이진검색트리 stl을 사용한 문제를 풀면서 함수들을 알아보도록 하겠습니다https://www.acmicpc.net/problem/7662 넘나 복잡하군요 사실 근데 입력에 대한 설명만 다 읽어도 생각보다 쉬워요 I n은 n을..

저희는 앞에서 수많은 코테를 정말 많이 풀어봤습니다. 지금까지 코테 문제를 풀 때 예를들어 2쌍의 값이 n개 주어진다고 해봅시다1,3 2,43,5 7,64,8 위치에따른 중복값이 없다고 할 때(1,3 이나 1,2처럼 앞선 1이 중복)어떻게 저희는 값을 찾았을까요 진짜 간단하게 arr을 사용했을 겁니다 arr[n]을 만들고입력된 값이 x,y라할떄arr[x]=y 이렇게요 근데 문제는 x의값이 너무너무너무너무커지면요? 10000000000,1이렇게 되면 어떻게 할까요? arr의 값은 최대 범위가 백만 이상이 된다면 메모리 할당 오류나 오버플로우 등으로 인한 오류가 발생합니다 이럴때 우리는 hash를 사용할 겁니다 hash에 관한 자세한 내용은 배워두면 좋겠지만 당장 코테에서 사용하지는 않기에 그냥 넘어가구요 ..

what is 투포인터?->기존에 이중 반복문을 통해 n^2에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결가능한 것 https://www.acmicpc.net/problem/2230 해당 문제를 풀어보자 문제의 대한 설명부터 하자면 예시 수열 1,2,3,4,5이라 할 때 입력된 값 m(예를들어 3 )이상인 수열 내부의 두 값에 대한 차이의 최솟값을 구하는 것이다 예를들어 4-1=35-2=3 등... 그러면 당장 떠오르는 풀이법은 무엇일까? 그렇다 그냥 반복문 두개 돌려서배열의 모든 값을 돌면서 뺄셈값을 구하면 된다! 하지만 우리는 코딩테스트를 풀 때, 시간 복잡도를 생각하지 않을수가 없어요 https://lee-soo.tistory.com/71 [배열]기초 공부안녕하세요 최근 인턴이 붙어서 ..

이분탐색이란, "정렬된" 배열에서 "특정"데이터를 찾기위해 순차탐색 대신 탐색범위를 절반씩 줄여가며 찾는 탐색 방법입니다. 선형탐색은 O(N)이고 이분탐색은 O(logN) 입니다. 이분탐색이 뭘까요 0 3 6 9 10 이라는 배열이 있을 때저희는 9를 찾고 싶습니다 그렇다면 배열을 절반으로 나누어서 6값을 찾는데6은 특정데이인 9보다 작으므로그 오른쪽을 보고 6과 10사이중 가운데 수를 또 찾는 방식으로 찾아가는 방법입니다 상세히 설명을 드리자면 2 4 6 13 16 19 22 23 30 32라는 배열이 있을 때 저희는 부분배열의 시작값 st와 부분배열의 마지막 값 en을 설정할 겁니다부분배열이란, 저희가 절반씩 나누며 찾아갈 배열이라 생각해주시면 됩니다 그래서, 먼저 가장 큰 배열을 볼 겁니다(전체..

Counting Star밤하늘의 펄 https://lee-soo.tistory.com/91 [배열 정렬]MergeSort정렬에는 여러가지 방법이 있습니다. 처음 정렬을 들었을때 저나 다른 전공자들이 모두 직관적으로 생각하는건 버블소트겠죠? 단순히 배열의 크기의 제곱만큼 모든 경우의수를 보면서 정렬을lee-soo.tistory.com https://lee-soo.tistory.com/92 [배열 정렬]Quick Sort야호https://lee-soo.tistory.com/91 [배열 정렬]MergeSort정렬에는 여러가지 방법이 있습니다. 처음 정렬을 들었을때 저나 다른 전공자들이 모두 직관적으로 생각하는건 버블소트겠죠? 단순히 배열의 크기lee-soo.tistory.com 저희가 두개 정렬을 앞에서 말..

야호https://lee-soo.tistory.com/91 [배열 정렬]MergeSort정렬에는 여러가지 방법이 있습니다. 처음 정렬을 들었을때 저나 다른 전공자들이 모두 직관적으로 생각하는건 버블소트겠죠? 단순히 배열의 크기의 제곱만큼 모든 경우의수를 보면서 정렬을lee-soo.tistory.com앞선 머지소트를 배우고나서퀵소트로 바로 왔습니다. 해당 퀵소트에 대한 설명을 해볼까요 6 -8 1 12 8 3 7 -7이라는 배열이 있을때저희는pivot과 l과 r이라는 인덱스를 둘 겁니다. pivot은 기준이 되는 수 l과 r은 그냥 맨앞과 맨 뒤로 시작합니다. "어떤 기준"으로 나누는지가 가장 중요하겠죠? 바로 pivot idx에 있는 수보다 작은수는 "왼쪽"에 큰수는 "오른쪽"에 두면 됩니다. 그렇다면 ..

정렬에는 여러가지 방법이 있습니다. 처음 정렬을 들었을때 저나 다른 전공자들이 모두 직관적으로 생각하는건 버블소트겠죠? 단순히 배열의 크기의 제곱만큼 모든 경우의수를 보면서 정렬을 하는건데 사실 코딩테스트에선 n^2만 되어도 시간 초과가 되는 문제들이 매우매우 많습니다. 그래서 시간복잡도가 n^2이 아닌 여러 정렬들을 보여드리고싶었으며, 그 첫번째로 머지소트를 보여드리겠습니다. 먼저 두개의 정렬된 n개의 배열을 합쳐서 정렬을 하는 경우부터 시작하겠습니다 만약 이 두개의 배열을 합쳐서, 정렬된 형태로 만들고 싶다면 어떻게 해야 할까요? -9 1 6 8 12와-7 7 13 15 라는 배열이 있을때그냥 단순하게 (n+m)^2 시간복잡도의 for문을 돌려서버블소트로 정렬해도 당연히 되지만 단순히 가장 새로운 ..

https://www.acmicpc.net/problem/12100 다들 한번쯤을 해보셨을 2048 문제입니다. 규칙자체는 다들 알 거라 생각하고 바로 풀어보겠습니다. 앞서 우선 왼쪽으로 기울이는 경우만 생각해보겠습니다 0 4 4 0 8 0 의 경우8 8 0 0 0 이 되는것을 볼 수 있습니다. 여기서 중요한 건 저 8 8 이 합쳐지지 않는 것이겠죠? 어떻게 합쳐지지 않게 할까요 포인터 변수를 따로 사용하면 됩니다. 4가지 방향을 총 5번 행하는 방법은 대충 백트래킹이든 무엇이든 써서 구한다고 했을 때 한 '행'에 대해서, idx를 0부터 시작합니다특정 arr을 우선만들고그리고 그 행을 0인덱스부터 끝까지 볼때, 값이 있는데, idx가 값이 비어있으면 우선 값에 넣어줍니다 예를들어 행이 0 2 0 2 ..

시뮬레이션이란 무엇일까요 진짜 간단히 "모든 상황을 구현?"이라고 보고다른사람들도 그냥 노가다 라고도 말합니다. 즉 구현력에 달려있는 문제들입니다. https://www.acmicpc.net/problem/15683문제부터 아찔하네요 내용자체는 이렇습니다. 방 안에는 최대 5가지 종류의 CCTV가 존재할 수 있으며, 그 갯수는 최대 8개를 넘지 않는다고 합니다. 또한 이런 종류의 cctv들로 되어있는데, 1번의 경우에는 상 하 좌 우 4가지 방향으로 택할 수 있고2번은 상하 / 좌우 2가지 방향..나머지도 똑같습니다. 주어진 입력에서 6이 있다면 cctv는 그 뒤를 보지 못합니다.이렇게 말이죠.여기 문제에서 원하는 답은 사각지대 즉, CCTV가 보지 못하는 구역의 "최대"크기를 구하는 겁니다. 앞선 상..