potato's devlog

💬 시작하며 정렬 알고리즘을 공부하면서 sort()에 대해서 궁금해졌다. 그리고 코딩테스트에서 정렬알고리즘도 어떻게 사용되는지 궁금해졌다. 코테에서는 대부분 정렬을 원할 때 Sort() 메서드를 사용해서 정렬시키기 때문이다. 단순히 알고 넘어가야만 하는 개념인건지, 아니면 구현까지 모두 완벽하게 할 줄 알아야하는건지? ⚫️ Swift의 sort() 내부 알고리즘 변화 ▪️ 2018년 이전 Swift는 2018년 sort의 내부 알고리즘이 교체가 됐다. 원래는, introsort를 사용했었다. introSort introsort란 평균적으로 빠른 성능을 내면서 최악의 상황에서도 점진적으로 최적화된 성능을 제공하는 하이브리드 정렬 알고리즘이다. C++ STL에서도 기본적으로 제공되는 정렬 함수이다. intr..

이번에도 막상 구현은 어렵지 않은 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 문제를 풀고 있다. 비교적 최근에 풀었던 문제중..

⚫️ 잘못된 방향 요즘 BFS와 DFS 문제를 풀고 있다. 비교적 최근에 풀었던 문제중 '프로그래머스 타겟넘버'를 풀면서 풀이를 작성하고, 내가 고민해온 과정을 블로그에 남겼는데 이 글을 본 친구에게 연락이 왔다. 친구가 본인이 이 문제와 BFS.DFS에 대한 문제풀이 방식을 정리해준 Notion 페이지도 보내줬다. 운동하느라 카톡을 조금 늦게 확인했는데 친구가 이건 혼자 생각할게 아니라며 통화를 하며 알려준다고 했다. 일단,,, 나름 문제를 풀고 '잘풀었다!'하고 끝냈던 상황이었는데, 어떤 방향으로 잘못흘러가고있는지 궁금해서 얼른 씻고 친구에게 연락을햇다. ⚫️ 문제의 포스팅 https://didu-story.tistory.com/420 [프로그래머스] (Swift) 타겟넘버 (lv.2) (BFS, 시..

아아아 짜증나 잘 안풀려ㅠㅠ 예전에 내가 풀었던 코드를 잠깐 참고하고 풀었씀... 흡.. 🤥 ⚫️ 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ⚫️ 나의 풀이 일단 보자마자 DFS임을 파악하긴 했는데... 잘 안풀렸다. 시작지점이 ICN으로 지정되어있었는데, dfs에 ICN을 전달하면, 티켓의 첫번쨰원소가 ICN인걸 찾아야하는건가? 싶어서 고민했고, 그 이후에 모든 경우를 다 판단하고 answer에 쌓아야하는데 어떻게 하지.. 그냥 고..