hwooo

https://leetcode.com/problems/count-number-of-bad-pairs/풀이힌트 2를 보고 j - i !=  nums[j] - nums[i] 식은 nums[j] - j!= nums[i] - i와 같다는 걸 깨달았다.해서 모든 원소에서 num[i] - i을 계산 후 해당 값을 map에 저장했다. 저장된 값을 순회하며 goodPairs의 개수를 구해 전체 개수에서 빼줬다.C/C++ 코드class Solution {public: long long countBadPairs(vector& nums) { map m; long long len = nums.size(); for (int i = 0; i second; goodPa..

https://leetcode.com/problems/battleships-in-a-board/풀이공간복잡도가 O(1)이고 한 번만 순회하여 답을 구해야 했다.주어진 battleship은 수직 혹은 수평으로만 주어지기에 위에서부터 순회하며 현재 셀에 battleship이 있고, 해당 셀의 위쪽 혹은 왼쪽이 X가 아니라면 즉, 이미 카운팅된 battleship이 아니라면 카운트 해 답을 구했다.C/C++ 코드class Solution {public: int countBattleships(vector>& board) { int row = board.size(); int col = board[0].size(); int cnt = 0; for (int i ..

https://leetcode.com/problems/decode-ways/description/ 풀이재귀로 풀릴 것 같아 도전했으나 답이 나오지 않아 답지를 봤다. 먼저 현재 값이 0이 아니라면 경우의 수 1개를 더한다.만약 현재 값이 1이거나 바로 뒤의 숫자 하나까지 더해 'z'의 값인 26 이하(두 자릿수가 가능한 경우)라면 해당 경의 수를 하나 더 더해주었다.이런 방식으로 뒤에서부터 탐색하며 처음 위치에까지 경우의 수를 구해 총 가짓수를 구했다.C/C++ 코드class Solution {public: int numDecodings(string s) { int len = s.size(); int dp[101] = {0, }; dp[len] = 1; ..

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이누적합을 이용하여 풀어야겠다는 생각을 했지만, 2차원 배열에서의 누적합은 어떻게 해야 할지 몰라 다른 분들의 풀이를 참고했다. 위의 그림과 같이 행과 열을 기준으로 누적합을 총 2번 계산한다. 이를 위해서 누적합 배열을 선언할 때 네 모서리에 각각 값을 넣어주어야 한다.N의 데미지를 입는다 가정했을 때,먼저 행을 기준으로 일차원 배열에서와 동일하게 데미지를 입는 시작 부분에 -N, 데미지를 입는 부분 + 1 열에 +N을 더해준다.다음으로는 열..

https://www.acmicpc.net/problem/14719풀이dp 등의 방법으로 풀 수 있을 거라 생각했지만 떠오르지 않아 답을 봤다.현재 위치에서 양옆으로 가장 큰 블럭을 찾고, 현재 위치가 양 옆의 블럭보다 작다면 (양 옆 블럭 중 작은 값 - 현재 블럭)을 고인 빗물 값에 저장하여 출력한다.C/C++ 코드#include #include using namespace std;int main() { int H, W, sum = 0; int blocks[500]; scanf("%d %d", &H, &W); for (int i = 0; i  Java 코드import java.io.BufferedReader;import java.io.IOException;import java.i..

https://leetcode.com/problems/keys-and-rooms/description/풀이0번 방부터 dfs로 탐색하며 방문 가능한 방을 모두 탐색한다. 이 때 방문 여부를 저장해, 미리 방문한 방은 다시 탐색하지 않는다.모든 방을 탐색한 후 탐색하지 않은 방이 있다면 false, 모든 방을 탐색했다면 true를 반환한다.C/C++ 코드class Solution {public: bool visited[1001] = {false, }; void dfs(vector>& rooms, int now) { if (visited[now]) return; visited[now] = true; for (int next : rooms[now]) ..

https://school.programmers.co.kr/learn/courses/30/lessons/70130 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이모든 경우의 수를 확인했을 때 최악의 경우 50만 * 50만이라 이중 반복문을 사용하는 방법은 아닐 거라 생각해서 인덱스 쌍을 짝수, 홀수로 나누어 스타 수열이 될 수 있는 쌍의 개수를 구해 최대인 값을 반환했다. 하지만 이는 숫자 쌍이 아닌, 단순히 양 옆의 숫자가 다를 때 추가하는 로직으로, 해당 문제와는 맞지 않았다.안 풀려 답을 봤고 각 숫자가 나온 횟수를 저장한 후, 최댓값이 현재 탐색값보다 작을 때만 주어진 배열 전체를 탐색하여 최..

https://www.acmicpc.net/problem/197풀이이전에는 프림 알고리즘을 사용했고, 이번에도 해당 알고리즘을 떠올렸으나 분리-집합으로 풀었다.주어진 경로로 가는 도중에 다른 노드에 들렀다 갈 수 있어 실질적으로는 모든 노드가 같은 집합 내에 위치해 있는지를 확인하면 된다.이 때 주어진 연결 정보가 1-2, 2-1로 양방향으로 주어지기에, 각 노드들이 같은 노드에 속해있지 않은 경우에만 합쳐줘야 한다.   BOJ (C/C++) 1976번: 여행 가자https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일hwoo..