Baekjoon

sweeping algorithm은 line sweeping 이라고도 불리고, 정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링 하는 방법이다.문제에 있는 예시를 보면 길이 (1,3), (2,5), (3,5), (6,7)인 선분이 4개 있다. 이를 그림으로 그려

현재 100번 채널에 있다. 이동하려고 하는 채널 N이 5457이고 6,7,8 번 버튼이 고장났을 경우에는 5455번으로 이동하고 + +. 총 6번의 버튼을 누르면 된다.즉, 크든 작든 제일 가까운 숫자로 가서 +,- 로 이동해야한다.처음에는 수학적으로 접근해서 일의

브루트 포스 문제를 많이 안 풀어봐서 그런지.. 코드짜기가 귀찮은 건지.. 아직 어렵다.. 근데 그냥 모든 경우의 수를 계산해보면 된다. 이거는 다른 사람의 코드를 참고했다.1행, 2행... 부터 시작해서 같은 행에서 인접한 두 칸을 교환한다.교환했을 때 check()

이 문제는 9명의 난쟁이 중 합이 100이 되는 7명의 난쟁이를 찾아 오름차순으로 출력하는 문제이다.9명 전체 난쟁이의 합에서 두 명을 골라 뺐을 때 합이 100이 되는 경우를 찾으면 된다. 처음 sum - (dwarfi + dwarfj)==100일 때 dwarfi

이 문제는 앞에서 풀었던 RGB문제와 흡사하게 풀 수 있다.먼저 동물원의 크기가 가로2 세로1인 경우를 생각해본다.사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우 + 오른쪽 우리에 배치하는 경우= 총 3가지가 있다.다음 동물원의 크기가 가로2 세로2

먼저 dpN 이렇게 만들어 줄거다. 행에는 n번째 집, 열에는 RGB의 값을 넣어준다.dp0= 1번 집이 R를 색칠했을 경우 비용의 최솟값, dp0= 1번 집이 G를 색칠했을 경우 비용의 최솟값,dp0= 1번 집이 B를 색칠했을 경우 비용의 최솟값... 을 차례로 저장

처음 타일링 문제를 접했을 때는 이게 도대체 뭐지? 하는 생각이 들었다. 동적 프로그래밍을 처음 접한 문제가 타일링 이었기 때문에 더욱 더 낯설고 이상(?)했다.이 문제를 풀기 전에 타일링 문제의 경우 끝을 기준으로 나눠서 생각해야 한다. 3 x k 인 타일의 경우 3

문제만 봐서는 아무런 아이디어도 떠오르지 않아서 표에 채워 넣어가면서 규칙을 찾아보려 했다.여기서 얻었던 몇 개의 단서는dp1=1dpi\*i=1 (어떤 수의 제곱 수는 1)dp3=dp3-1\*1+1dp5=dp5-2\*2+1dp6=dp6-2\*2+1…이런 규칙을 찾을 수

앞에서 푼 연속합의 문제와 다른 점은 수열에서 수를 하나 제거할 수도 있고 안 해도 된다는 것이다.표를 그리면서 여러가지 생각을 했다.(dynamic programming 진짜 안 풀린다..) 먼저 한 생각은 연속된 수가 0보다 크거나 같은 양수일 경우에는 그냥 더하고

이 문제 푸는데 삽질을 엄청 엄청 많이 했다.. 다시 생각해도 눈물난다..첫 번째 아이디어dp를 2차원 vector로 만들어서 dy의 값은 Ay에서 시작해서 Ax에서 끝나는 합을 저장하고 저장 할 때마다 result 에 있는 값과 비교해 큰 값을 갱신해 주는 방법으로

문제에서 주어진 대로 바이토닉 부분 수열은 수열 A가 주어졌을 때 Ai값을 기준으로 A0에서 Ai-1중 증가하는 부분 수열이 존재하고, Ai+1에서 AN중 감소하는 부분 수열이 존재하는 경우를 말한다.'가장 긴 증가하는 부분 수열' 알고리즘과 '가장 긴 감소하는 부분

먼저 Ai에 값을 입력 받으면서 Bi에도 값을 똑같이 넣어준다.A의 부분수열이 증가수열이면서 현재 비교대상값(Bi) 보다 이전까지의 합+ 현재값 (Bj+Aj)이 더 큰 경우 이 값을 현재 비교대상값(Bi)에 넣어준다.코드 짜면서도 자꾸 헷갈려서 표에 값을 채워가며 생각

바로 앞에서 풀었던 문제가 부분 수열의 길이만 출력하는 거라면, 이번에는 가장 긴 증가하는 부분수열도 출력해야 한다. dp의 값이 가장 큰 A의 값부터 시작해서 하나씩 작아지게 역순으로 B에 push_back 한다. (처음에 dp의 값이 가장 작은 A값부터 B에 pus

종만북 P.232 최대 증가 부분 수열 문제를 해결하는 완전 탐색 알고리즘을 공부하다가 도저히 이해가 안 돼서 일단 다른 사람들이 풀어 놓은 코드를 참고해서 코드를 작성했다.중첩 for문을 사용하여 Ai의 값과 Ai 이전의 값 Aj, 예를 들면 A5일 경우 A0부터 A

문제에서 보면 '먼저 푸는 것이 좋은 문제'가 있다는 말은 문제에 '순서'가 있다는 말이다. 이것은 DFS로 풀 수 있는 가장 유명한 문제중 하나인 위상정렬 (topological Sort)로 푸는 문제이다.각 정점간의 순서를 저장하며 진입차수 증가예를 들어 위와같은

#6603 로또 > 1. 생성 먼저 49가지 수 중 k개의 수를 골라 담을 벡터 를 만들고 k개중 6개를 뽑아서 넣을 를 만듦 > 2. dfs 함수를 반복하는데 인자를 둔다. 는 의 index, 는 의 index다. 즉 는 이때까지 뽑힌 로또의 개수

\[합이 s가 되는 부분 수열 합의 개수를 구하는 문제는 dfs를 이용하여 간단하게 풀 수 있다.예를 들어 {-7, -3, -2, 5, 8}의 수열이 주어졌을 때, 처음 합 sum=0에서 ⓐ-7을 더하는 것과 ⓑ더하지 않는 부분으로 나누고 ⓐ-7을 더한 곳에서 ⓒ-3을

\[문제는 1,2,3 을 이용하여 정수 n을 만드는 방법을 나타내는 개수를 구하는 것이다.주의할 점은 4를 만들 때, 2+1+1, 1+2+1, 1+1+2 는 모두 같은 것으로 취급한다. 여기서 한가지 생각해야 할 점은 이 순서를 오름차순이나 내림차순으만 나타낸다.여기에

\[100번칸에 도착하기 위해 최소 굴려야 하는 주사위 횟수를 구하는 문제다. 여기서 '최단 거리'를 구하면 되므로 BFS로 풀어야 한다.뱀과 사다리를 따로 구분해서 배열을 만들 필요가 없으니 그냥 같이 int ladderOrSnake\[MAX] 로 선언해서 뱀과 사다

(r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구하는 문제이므로 BFS를 이용해 풀어야 한다는 것을 알 수 있다.(대개 BFS는 그래프에서의 최단 경로 문제를 푸는데 용도로 사용된다)BFS 복습queue <pair<int, int>> qqu

\[각 정점에서 최대로 가져올 수 있는 사탕의 개수를 구해서 (n,m)까지 이르렀을 때 저장된 최댓값을 return 하면 된다. 사탕의 개수는 (1,1)부터 (n,m)까지 저장되어 있기 때문에 위에서 부터 top-down 방식으로 memoization 기법을 사용한다.

dp에서 이런 비슷한 유형의 문제를 풀어본 기억이 있어서 dp로 풀어야 겠다고 생각했다. 일단 int dp\[]에서 dp\[i]가 의미하는 것은 jump\[i]에서 가장 오른쪽 끝으로 갈 수 있을 때까지 해야하는 최소 jump의 개수다. 그렇다면 마지막에 구해야 할 값

\[참고1, 참고2n Queen Problem 은 대표적인 Backtracking의 예제라고 한다.처음에는 단순하게 NxN 체스판 위의 모든 좌표에 대해 한 좌표를 기준으로 x축, y축, 대각선을 모두 구하는 방법으로 해야 하나 했다..그래서 여러 블로그를 보고 공부한

정규 표현식은 문자열에서 패턴을 찾는데 사용주어진 문자열이 주어진 규칙에 맞는지 확인할 때주어진 문자열에서 원하는 패턴의 문자열을 검색할 때주어진 문자열에서 원하는 패턴의 문자열로 치환할 때주어진 엔진 소리 (100~1~|01)~은 정규식 (100+1+|01)+로 나타

\[Palindrome회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.(참고: 위키피디아)이

\[처음 문제를 봤을 땐 쉬운 문제라고 생각했는데 생각보다 까다로운 문제같다. bool visited\[]\[]우선 세 돌의 개수는 계속 변하므로 돌 세개를 처리하는 벡터를 만드려고 하니 너무 크기가 커졌다. 그런데 어차피 돌 무게 2개가 지정되면 나머지는 자동으로 정

\[참고dp\[x]\[y] =file\[x]에서 file\[y]까지 합치는데 드는 최소비용마지막에 구해야 하는 것은 dp\[1]\[K]가 된다sum\[x]은 file\[1]부터 file\[x] 까지의 부분합이다.sum\[x]=sum\[x-1]+file\[x] 이다.예를

\[가끔 코딩 테스트에서 이렇게 기본 구현하는 문제들이 나와서 조금씩 풀어봐야겠다.진법 변환은 원래 10진법의 숫자를 진법 변환을 하려고하는 수로 나누기를 반복해서 하면 되는데 쉽게 예를 들면,나중에 숫자를 출력할 때 위에서 부터 pop()하며 출력하기 위해stack을

\[풀이 1먼저 보고 바로 dp로 풀어야겠다고 생각했고dp\[i]\[j]=a\[i] 부터 a\[j] 까지의 합으로 설정했다.(자꾸 dp, bfs, dfs문제 들을 풀다보니 이런 문제도 그런 알고리즘으로 풀어야겠다고 생각한다 ㅠㅠ)e.g. n=10 m=5 a={1,2,3

\[풀이1 - Hashunordered_map<int, bool> map;을 만들어주고 이렇게 숫자를 하나씩 받을 때마다 해당 숫자에 true를 저장해준다두 번째로 숫자를 받아올 때 이 값이 hash map에 저장된 값이 맞다면 1, 아니라면 0을 print한다.

\[\[풀이1벽은 부수거나, 1개만 부수거나이므로 처음에는 벽을 부수지 않았을 때 주어진 map 그대로 해서 distance를 구한다다음 map의 모든 정점을 순회하면서 WALL==1일 경우 해당 부분을 PATH=0으로 바꾸어주고 bfs 탐색 후 다시 WALL=1로 바

\[빈 칸을 채울 때 3x3 정사각형 내에서 숫자를 겹치지 않게 하는 부분과 시간 초과때문에 힘든 문제같다vector<pair<int, int>>vp;먼저 스도쿠 판에 숫자를 입력 받을 때 빈 공간 즉, 0으로 입력 받는 부분의 좌표를 vp에 저장하고 받을

\[Velog Posting \[벽 부수고 이동하기 첫 번째 문제와 다른 점은 첫 번째는 최대 1개까지 벽을 부술 수 있었지만 이번엔 K개까지 부술 수 있었다. 그래서 bool discovered\[MAX]\[MAX]\[2]에서 bool discovered\[MAX]\

\[참고1이때까지 많이 풀어보았던 BFS 문제들 처럼 똑같이 BFS 함수를 구현하고 현재 위치가 WALL=1 이면 BFS탐색을 통해 갈 수 있는 PATH=0의 개수를 count하고 리턴하여 그 수를 원래 WALL=1이 있던 자리에 넣어주고 이 과정을 WALL이 나올 때

\[\[마지막 계단/포도주를 골라야 한다는 조건 빼고는 본질적으로 동일한 문제다이 문제를 정확하게 이해하는데 이틀이 걸렸다..계단 오르기를 예시로 들면dp\[i]=i번째 계단을 밟았을 때 얻을 수 있는 최대 점수로 두고 점화식을 도출해본다(각 계단에 적혀있는 점수는 s

\[참고n가지 종류의 동전을 사용하여 k원을 만드는 경우의 수를 구하는 문제 (순서만 다른 경우는 같은 경우이다)dp\[a]=b일 때, a원을 만드는 방법은 b개이다 라고 정했을 때우선 dp\[0]=1이다. 0원을 만드는 방법은 하나도 선택하지 않는 경우로, 이 경우를

K원을 만드는데 필요한 동전 개수의 최솟값을 만들기 위해서는 동전의 가치가 큰 동전부터 사용해야 한다동전의 가치가 큰 동전부터 사용하다가 K원에서 현재 동전을 뺐을 때, 0보다 작아진다면 다음으로 가치가 큰 동전을 사용한다using namespace std;int N,

\[처음 칸에서 상하좌우 이웃한 곳을 탐색해서 제일 아래 칸으로 내려간다는 점에서 dfs를 이용해 풀어야 한다는 것을 알 수 있다처음에 dfs만을 이용해 풀었다가 시간 초과가 났다. map의 크기가 최대 500\*500이므로 완전탐색 dfs 방법으로 풀면 최악의 경우

문제는 (0,0)에서 시작해 (N-1, N-1)까지 갈 때 최소 비용을 구하는 것처음에는 dp를 풀 때 외발뛰기, 삼각형 위의 최대 경로 같은 문제들을 생각하며 dp로 풀어야 하나 생각했지만 링크는 동서남북으로 움직일 수 있으며 그때마다 이미 구했던 최적의 해는 바뀔

\[은진이가 마지막으로 남은 마피아일 때 종료 조건은 1. 참가자가 1명이 남고 그 사람이 시민일 경우, 2. 참가자가 1명이 남고 그 사람이 은진이일 경우 이다게임이 종료될 수 있을 때까지 모든 경우의 수를 따져보아야하는 Brute Force 문제각 사람들의 유죄지수

문제문자열 S안에서 단어W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산문자열 W의 길이가 g라고 했을 때, 문자열 S에서 g만큼 떼서 보았을 때 그 문자열을 구성하는 각 글자들이 W를 구성하는 각 글자들과 동일한지 살펴본다문자열 S의 처음부터 g길이

\[BOJ 참고로 이 문제도 예전에 C++로 풀었는데 그땐 Heap으로 풀었었다. 하지만 문제에서 의도한 알고리즘은 아닌 것 같아서 JAVA 문법 익힐 겸 다른 풀이를 참고하며 풀었다. (JAVA로 알고리즘 푸는 거 고역이다..) 문제 제목에서도 주어진대로 가장 가까운

#11659 구간 합 구하기4 #11660 구간 합 구하기5 #11659 구간합4 Idea 구간 합 구하기 문제의 핵심은 누적합을 Memoization 기법을 사용하여 해결하는 것이다 N과 M이 최대 100,000이기 때문에 그냥 for문을 돌려서 찾을 경우 최악의

\[문제는 단순히 단어를 몇 개 선택하여 문장을 만들었을 때, 이 문장 안에 a~z까지 모든 알파벳을 포함하고 있는지 확인하고 이런 문장이 몇 개 있는지를 출력하는 문제이다현재까지 나온 알파벳의 개수를 저장하는 배열 int\[26] checked 을 만들고, 한 단어

\[단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산우선 순위 큐에 지금까지 찾아낸 해당 정점까지의 최단 거리, 정점의 번호를쌍으로 넣음 priority_queue <pair<int, int>> pq; 정점까지의

\[문제의 핵심은 3\*3 2차원 배열에 존재하는 숫자들을 좌상단부터 우하단까지 이어지는 숫자 (1차원 배열, 엄밀히 말하면 String 형)로 표현하는 것이다 위에서 변형한 String형태를 HashMap에 넣어 관리한다. HashMap <String, Inte

\[답으로 구해야하는 것이 무엇인지 생각해볼 필요가 있는 문제였다 → "한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값"을 구하는 문제이다 일반 그래프 문제에서 요구하는 최소 이동거리, cost의 최소 등과는 다르다 → A에서 출발해서 B로 가는 지점 중 다리