potato's devlog

⚫️ 문제 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 문제 유형과 계속 비슷하기 때문에 수월하게 풀이를 생각해냈다. 그리고 친구와 이야기 나눴던 부분을 잘 생각하면서 푸니까 금방 풀린다.. 올레 올레 영역마다 양과 늑대의 수를 따로 세어줘야하기 ..

💬 잡담부터 start 어제 친구와 깊은 dfs 와 bfs에 대해서 고찰해본 뒤, 첫 문제풀이다. dfs/bfs관련 문제를 그래도 ... 50개정도... 는 풀었나..? 그 이상인가.. 어쨌든 그정도 푸니까 문제 유형은 대애애충 파악했고.. 이제 이게 정말 BFS인지 DFS인지 머리를 굴리기 시작했다. (원래였으면 대충 그냐 완탐=bfs지! 라는 바보같은 소리를 적어내려가고 있겠지. 땡큐,,,마이프랜드) 아래는 내가 문제를 풀면서 잘못 짚고 넘어갔던 BFS와 DFS에 대한 개념을 살펴볼 수 있다. https://didu-story.tistory.com/422 [알고리즘] 2023.02.25 DFS와 BFS에 대한 고찰 ⚫️ 잘못된 방향 요즘 BFS와 DFS 문제를 풀고 있다. 비교적 최근에 풀었던 문제중..

⚫️ 문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net ⚫️ 나의 풀이 아니 이것은,,, 내가 이 문제를 풀기 전에 바로 정리했던 '음료수 얼려먹기' 예제와 같은 문제다. https://github.com/HotCodeBreakers/CodingTest/discussions/25 [개념정리] DFS+BFS (혹시,,, 문제풀이 전에 이코테 책을 보시나요!?) · Discussion #25 · HotCodeBreakers/Codi 안녕하..