potato's devlog

이분탐색과 파라메트릭 서치의 차이점과, 어느 때에 사용하면 좋은지에 대해서 명확하게 알고 넘어갈 필요가 있다고 생각된다. 맨 밑부분에 이 문제가 왜 파라메트릭 서치로 풀리는지에 대해서 생각을 적어놨다. 그것을 항상 기억하자! ⚫️ 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚫️ 나의 풀이 이거 바로 직전에 푼 문제와 매우 비슷햇기 때문에 금방 풀 수 있었다. (바로 이전에 풀었던 문제 아래 백준의 공유기설치) https://didu-..

⚫️ 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ⚫️ 나의 풀이 ◾️ 처음에 생각한 풀이 어떤 것을 기준으로두고 탐색할것인가가 고민스러웠던 문제였다. 처음에 무작정 생각한 풀이 방식은, C개의 공유기를 설치해야하니, N개의 집에서 C개의 집을 고르는 모든 조합을 고려한 뒤 거리를 볼끼? 싶었는데 ㅋㅋㅋㅋ 말도 안됐다. 주어진 조건을 보자 입력 조건은 이렇다. 일단 집은 최대 10억개..

⚫️ 문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net ⚫️ 나의 풀이 보자마자 이코테 책에 있는 '파라메트릭 서치' 문제의 대표유형인듯 싶다. 어려운 문제는 아니지만, 풀이를 하다가 한가지 놓치고 생각한 부분이 있어서 기록하고자 블로그 글을 작성한다. ◾️ 놓치고 생각한 부분 처음에 생각했을 때, start는 주어진 지방예산의 최소값, end 는 주어진 지방예산의 최대값으로 설정하면 되겟구나 싶어서 그렇게 구현했다. 근데, 이렇게 하..

이분탐색을 진행할 때는 존재여부를 확인할때는 괜찮지만, 개수를 세어야할 경우에는 탐색하고자하는 배열 내부에 중복값이 있으면 안된다. 그럴때를 대비해서 upper bounds 방법과 lower bounds 방법을 잘 알아두어야 문제를 맞출 수 있을 것 같다. ⚫️ 문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ⚫️ 나의 풀이 아 그리고 문제 풀고 발견한건데, dictionary를 사용하면 진짜 개 간단하게..

이번에도 막상 구현은 어렵지 않은 DFS 관련 문제였지만, 생각하는데 조금 많은 길을 가야했다. 그래도 DFS, BFS에 대한 감을 조금씩 잡아가고 있는 것 같아서 너무 기쁘다! ⚫️ 문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net ⚫️ 생각의 흐름 1️⃣ 첫번째 생각 일단 연결된 7명의 친구들을 찾아야하는 것이 우선인 것 같았다. 그래서 DFS를 이용해서 7명의 친구들을 탐색하면서, 그 친구들이 S인지 Y인지 판단하고, Y가 4명을 넘어가는..

⚫️ 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=swift 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚫️ 나의 생각의 흐름 일단 몇단계의 흐름을 거쳐야하는지 , 그리고 이 흐름이 최소가 되는 해를 구해야한다. 그렇기 때문에 일단 가장 먼저 BFS를 떠올렸다. 그럼 BFS를 구현하기 전에 이것저것 생각을 해보자. 🔖 시간복잡도 조건을 살펴보고 시간복잡도를 생각해봤다. BFS를 구현하면 총 N번의 노드에 방문하고, queue가 빌때까지 while문이 반복되므로 ..

역시나 이문제도 골드라서 겁먹었는데, 문제를 차근차근 읽어나가면서 아이패드에 생각정리를 해보니 조건처리만 잘 해주면 쉬운 문제였다! 근데 왤케 많이 틀렸냐고? 하하ㅏ하핳,,, 코드 수정하느라 막 print해야하는데 안해주고 print문 지워진지도 모르고 다른거 수정하고 앉아있고 생쑈를 했다. ... 아우 그냥...... 문제는 다 풀었는데 나의 잔 실수때문에 쓸데없이 버린 시간만 너무 많아서 화가 단단히 났던 문제! ⚫️ 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.a..

골드여서 겁먹었는데 조건처리만 잘 해주면 아주 쉬운 문제였당! ⚫️ 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ⚫️ 나의 고민,,, 풀이 문제를 읽자마자 어떻게 풀어야할지 파악했지만,, , 동시에 고민이 들었던 것이 있다. 적록색약인경우와, 적록색약이 아닌 경우를 따로 dfs를 돌려주어야할까? 그렇게 하게 된다면,,, 시간이 너무 오래걸리지 않을까? 싶었다. 그래서 코드를 어떻게 하면 깔끔하게 짤 수 있을까, DFS를 한 번만..

비슷한 유형의 문제가 돌려서 나온다는 말에 공감하는 요즘,,, 더 다양한 유형의 문제를 풀어보기 위해서 노력해야겟다! 그리고 하루에 2문제만 푸는건 너무 적으니, 최소 3문제 이상은 풀어야겟다. 아좌좌 화이팅 ⚫️ 문제 https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net ⚫️ 나의 풀이 아니,,, 이코테 음료수 얼리기, 혹은 방금 전에 풀어본 백준 양문제... 등등 너무너무 비슷한 유형의 문제들이다. 이런 문제 유형은 정말 잘 풀수 잇을것같다는 자신감이 마구 샘솟는다. 이제 DFS 관련해서 다른 유형의 문제를 풀어봐야겠다. 문제를 보자마자, 그냥 D..

친구와 DFS / BFS에 대한 고찰을 한 효과를 톡톡히 보는걸까? 이제 DFS와 BFS를 명확하게 구별할 줄 알고 문제가 쉽고 빠르게 풀린다..! ⚫️ 문제 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net ⚫️ 나의 풀이 앞서 풀었던 DFS 문제 유형과 계속 비슷하기 때문에 수월하게 풀이를 생각해냈다. 그리고 친구와 이야기 나눴던 부분을 잘 생각하면서 푸니까 금방 풀린다.. 올레 올레 영역마다 양과 늑대의 수를 따로 세어줘야하기 ..