본문 바로가기

전체 글60

99클럽 코테스터디 21일차 TIL 정수 삼각형 정수삼각형프로그래머스 level 3 DP문제링크문제설명문제풀이DP를 푸는 것이 익숙하지 않아서, BruteForce 방식으로 우선적으로 풀이하고, DP로 바꾸는 작업을 거쳐 풀이했다.int brute (int cur, int prev, int lim, vector>& tri) { if (cur == lim) { return 0; } if (memo[cur][prev] != -1) { return memo[cur][prev]; } int tmp1 = brute(cur+1, prev, lim, tri); int tmp2 = brute(cur+1, prev+1, lim, tri); memo[cur][prev] = tri[cur][prev] + ma.. 2024. 8. 11.
99클럽 코테스터디 19일차 TIL 조이스틱 조이스틱프로그래머스 Level 2 Greedy문제링크문제 설명문제 풀이처음에는 직관적으로 풀이하려고 해서 인덱스 0 번의 문자에서 오른쪽으로 가며 해당 바꿔야 하는 문자가 있다면 그 곳으로 가, 그 문자를 바꾸고 가장 가깝게 이동할 수 있는 거리를 측정해 답에 더해주는 방식으로 풀이했다.하지만 이 풀이의 문제는, 오른쪽으로 이동하며 확인했을때, 최초로 마주하는 문자보다 0번에서 바로 왼쪽, 즉, 가장 끝 번으로 갈때가 효율적인 경우에는 제대로 답이 나오지 않는 다는 문제가 있었다.혼자힘으로는 디버깅을 할 수 없었고, 결국 질문하기 탭에 있는 어떤 분의 설명을 보고 풀었다.참고한 질문게시판의 글전체 코드#include #include #include using namespace std;int solutio.. 2024. 8. 9.
99클럽 코테스터디 18일차 TIL 일루미네이션 일루미네이션BOJ Gold IV BFS / DFS문제 설명문제 풀이처음에는 한줄 고립된 부분을 찾고 그 부분을 방문하지 않으면서 건물이 있는 부분에서 건물이 없는 부분을 찾는 방식으로 구현해 나갔다.하지만, 곧 그 방법이 틀린 걸 알았고, 이 문제가 그래프 순회 문제라는 것을 보고 다른 풀이를 떠올려야 했다.오늘 진행된 스터디에서 아이디어를 얻었고 문제를 풀 수 있었다.예전에 문제 풀 때 사용했던 아이디어지만 잊고있던 둘레에 한줄씩 더 추가해주고, 그 부분에서 보이는? 인접해 있는 건물의 부분만 카운트 해주면 되는 방식으로 풀이하면 되는 문제였다.풀이#include #include #define MAXW 105using namespace std;int fld[MAXW][MAXW] = {0, };int W.. 2024. 8. 8.
99클럽 코테스터디 17일차 TIL 사자와 토끼 사자와 토끼BOJ Gold 1 이분탐색문제링크문제 설명문제 풀이처음에 BFS 로 시뮬레이션 느낌으로 구현했는데 시간초과가 났다.문제를 푸는 과정에서 잠깐 생각했던 이분그래프 로직으로 다시 짜봤는데, 성공적으로 통과했다.노드를 색칠한다고 생각하고, 하나의 노드를 빨간색으로 칠했다면, 그 노드와 연결되어 있는 모든 노드는 파란색으로 칠하는 로직이다.구현#include #include #define MAXN 50005using namespace std;// 수풀의 수, 오솔길의 수int N, M, res=0;vector> fld(MAXN);int visited[MAXN];void dfs (int cur) { if (visited[cur] == 0) { visited[cur] = 1; .. 2024. 8. 7.
99클럽 코테스터디 16일차 TIL N-Queen N-Queen프로그래머스 level 2 완전탐색문제설명가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.제한사항퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.n은 12이하의 자연수 입니다.문제풀이예전에 고생해서 풀었던 문제라서 오랫만에 보니까 좀 반가웠다. 그때 거의 2주 가까이 풀이했던 기억이 있다. 파이썬으로 이미 풀이가 되어있어서 C++ 로 다시 한번 풀어봤다. 별다른 처리 없이 체스의 Queen의 특성을 조건으로 만들어주고, 정직하게 .. 2024. 8. 6.
99클럽 코테스터디 15일차 TIL 소수찾기 문제 소수찾기프로그래머스 level 2 완전탐색문제링크문제설명한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.제한사항numbers는 길이 1 이상 7 이하인 문자열입니다.numbers는 0~9까지 숫자만으로 이루어져 있습니다."013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.문제풀이문제 설명이나 구현해야할 것은 명확했지만 그만큼 시간복잡도가 높을 것 같아서 설계하는 단계에서 고민을 많이 한 문제였다.예상했던 시간복잡도는에라토스테네스의 체 .. 2024. 8. 5.

티스토리툴바