본문 바로가기

Algorithm283

[004]Jewels and Stones 문제: https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3317/ 'a' ~ 'Z'까지의 알파벳의 상태를 관리하기 위해 아스키코드를 포함한 1바이트를 사용하면 됩니다. 알파벳이 나타날 때 마다 배열의 갯수를 증가시킨 후 쥬얼리 값에 모두 합산해주면 됩니다. class Solution { public: int numJewelsInStones(string J, string S) { int stoneState[128] = {0,}; for (int i = 0; i < S.length(); ++i) { int idx = S[i]; stoneState[idx]++; } int ret = 0;.. 2020. 5. 17.
[BOJ]1194번: 달이 차오른다, 가자. 문제: https://www.acmicpc.net/problem/1194 비트 연산자 + BFS 문제입니다. A~F는 6개의 문자로 {공집합, ... , {a,b,c,d,e,f} } 까지의 부분집합은 2^6 = 64개로 나타낼 수 있습니다. 총 64개의 state가 존재한다고 표현하겠습니다. 그래서 [64][N][M] 만큼의 방문(상태)배열이 존재하게 됩니다. 그러면 각 칸을 순회할 때 가지고 있어야 할 정보는 아래와 같이 네 가지 정보입니다. { 현재 STATE(0~64), Y좌표, X좌표, MOVE_CNT } 열쇠칸을 만났다면 OR 연산자를 통해 현재 STATE에 특정 열쇠를 더해줍니다. int NEW_STATE = NOW_STATE | (1 2020. 5. 17.
[003]First Bad Version 문제: https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3316/ 이분 탐색 문제입니다. mid를 구한 후 Bad Version이 나왔다면, 상한을 en = mid 으로 줄여서 탐색범위를 절반씩 줄여나가면 됩니다. 시간복잡도 O(logN) // The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { long long int st, en,mid, before; st = 0; en = (long long int).. 2020. 5. 16.
[코딩테스트 연습] 지형 이동 문제: https://programmers.co.kr/learn/courses/30/lessons/62050최소 설치비용을 만족하려면 두 가지 조건을 만족해야 합니다. 1. 최소의 사다리 개수2. 사다리를 놓을 수 있는 위치들 중에 최소비용인 위치 1번에 대해 생각해보면 사다리 없이 이동할 수 있는 지점이 N개라고 하면 N-1개의 사다리만 놓으면 N개의 지점은 모두 연결이 됩니다. 여기서 이 문제가 MST 문제임을 알 수 있습니다. 2번에 대해서는 각 컴포넌트 중에서 경계점에 있는 좌표에 대해 엣지를 구합니다.Edge(현재 컴포넌트 번호, 연결되어있는 컴포넌트 번호, 사다리 비용) 이 엣지를 우선순위 큐에 넣고 작은 비용의 사다리부터 뽑도록 크루스칼 알고리즘을 돌리면여기서 뽑혀나온 N-1개의 엣지가 최소.. 2020. 5. 16.

티스토리툴바