💜개발과 일상 (≧∇≦)ﾉ

📌 문제 https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 접근하고 어떤 자료구조를 사용하는지는 너무 명확해서 구현까지는 금방 했다. 자료구조도 한 원소의 값의 범위가 크기 때문에 long long 으로 선언하는 것만 조심하면 된다. 하지만 문제는... 도대체 첫번째 테스트1가 왜 통과되지 않는것일까.... 계속 고민을 해보았다... 구글링 해보고 다른 분들 코드를 리뷰해 본 결과 이유는 반복문이 작업을 계속하는 기준을 큐의 크기 * 2..

https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 각 노드들이 연결되어있는지를 파악하고 한 묶음을 네트워크라 칭한다. 여기서 네트워크가 총 몇개인지? 출력하는 문제. BFS로도 가능하다. 필자는 DFS로 풀었고, 각 노드 별로 탐색을 하되, 한번 탐색을 했던 기록을 visited에 저장해서 더 이상 탐색하지 않도록 했다. 왜냐면 단 하나라도 연결이 되면 그 노드는 네트워크에 속하기 때문이다. 모든 노드와도 연결되지 않은 노드의 경우는 노드 하나만..

자료구조를 활용한 완전 탐색 문제다. 단, 우선순위를 고려해야하는 문제가 있어서 처음에는 우선순위 큐 자료구조를 활용해야하나? 싶었는데, 막상 원하는 location의 값이 언제 나오는지를 확인하기 위해서는 원래 위치를 기반으로 탐색을 할 수 밖에 없었다. 그래서 location에서 지정해둔 index를 따라가면서 순서를 찾는 방식으로 개발했다. 다른 방법으로도 풀 수 있을 것 같지만 가장 직관적이게 다가온 방법은 이 방법이었다. #include #include #include #include #include using namespace std; int solution(vector priorities, int location) { int answer = 0; queue q; // queue 자료구조 fo..

전형적인 구현 탐색 DFS 였습니다. // 욕심쟁이 판다 - 구현 #include #include using namespace std; int N, result; int board[501][501]; long long score[501][501]; // 상, 하, 좌, 우 중 한 곳으로 이동 int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int DFS(int x, int y){ if(score[x][y] == 0){ score[x][y] =1; int cnt = 0; for(int i = 0; i = 0 && nx = 0 && ny < N){ ..

📌 문제 https://www.acmicpc.net/problem/1030 1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 결론부터 말하자면 시간초과가 났다... 필자는 보드를 관점으로 문제를 풀었다. 보드의 모든 프렉탈 평면 구조를 다 탐색하면서 R1, R2, C1, C2 내에 해당되면 출력할 수 있도록 출력 이차원 배열을 선언했지만 이 방법이 아닌 듯 하다. 다른 블로그 글을 참조해보니 해당 R1, R2, C1, C2를 탐색하면서 해당 칸들이 색칠되는 칸인지를 확인했다... ㅠㅠ 처음부터 접근을 잘 못한 것이었다. 문제 풀면서 부분만 출력하라는 조건을 보면 그렇게 생각했어야했는데..... 다른 분들 코드를 보고 통과를..

📌 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 처음에 이 문제를 DFS로 풀었다. 풀린다... 하지만 시간초과... 왜일까 고민해봤다 #include using namespace std; int MIN = 999000; int N; int Red[1001];..

📌 문제 숫자 L과 R이 있을 때, 숫자 두 개 사이에 8을 가장 최소로 가지는 숫자의 8의 개수를 출력하는 문제다. 먼저 생각나는 방법은 L부터 R까지의 숫자들의 자리수를 하나씩 구해서 최소 값을 구한다고 생각할 수도 있다. 하지만 명심할 점은 굳이 우리가 하나씩 확인할 필요가 없이 생각 하나로 바꿀 수 있다는 점이다. 첫번째, L과 R의 자리수에서 분명히 공통된 부분이 있을 것이다. 공통된 자리수에 있는 8의 개수는 L과 R의 사이에 있는 숫자들도 무조건 가지기 때문에 앞으로 셀 필요가 없다는 것. 두번재, 우리는 8이라는 숫자를 쓰는 것을 피하는 것이다. 그러므로 L과 R사이의 숫자 사이에 8 이에외의 자리수를 가지는 숫자가 분명히 존재한다면 굳이 8을 쓸 필요가 없다는 것이다. 이런 점을 고려했을..

📌 문제 항상 문제에서 애매하게 설명하기 때문에 예시를 보면 좀 더 명확하게 문제를 이해하는 듯 하다. 많은 단어를 읽을 수 있도록하되, 알파벳 K개의 글자를 가르쳐 이때 읽을 수 있는 단어의 최대 개수를 출력하는 문제였다. 문자열 다루기 + 백트래킹 + brute force였다. 조건 1) 알파벳 몇 개를 가르칠 것인가? 먼저 "anta" ~ "tica"는 무조건 읽을 수 있어야 모든 단어를 읽을 수 있는 기회(?)가 주어지기 때문에, "atinc"는 무조건 읽어야한다. 그러므로, 알파벳을 선택하는 배열에 "atinc"는 디폴트로 선택할 수 있도록 한다. 이렇게 되면, 처음 시작할 때부터 5개의 알파벳을 선택하고 시작해야한다. 그말은, 알파벳 배우는 개수인 K개가 5개보다 적으면 애초에 아무런 단어를 ..