Algorithm - 문제

algorithm

컴퓨터가 1초에 할 수 있는 연산은 3-5억 (주먹구구)문제에서 요구하는 시간은 1~5초 정도시간복잡도: 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관 관계빅오 표기법 : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 (시간복잡도를 표현하는 방법)

특징 임의의 위치에 있는 원소를 확인 / 변경 => O(1)원소를 끝에 추가 => O(1)마지막 원소를 제거 => O(1)임의의 위치에 원소를 추가 / 제거 => O(N) (나머지 원소들을 미루고 / 당겨야 하기 때문) 팁 배열을 특정 값으로 초기화 시킬 때 -> f

문제Code: ASCII 코드를 이용하면 편하게 풀 수 있다. A = 65 a = 97

: 역시 ASCII를 이용하여 개수를 분류하는 분류문제 였다.   사용한 배열 초기화를 까먹지 말자;

man / woman 은 같이 잘 일이 없으니 분류학년 별 인원수를 구하고 방 1개 최대 인원수 max와 각각 비교그리고 Count

: char -> int 바꿀 때   char-'0' = int

: 두 문자의 길이가 다를 수 있다는 것을 생각 못함; 바보

: 값과 포인터를 가지고 노드간 서로 연결된 선형 자료구조N 번째 원소를 확인 / 변경 => O(N) 임의의 위치에 원소를 추가 / 제거 => O(1)배열과 같은 '선형 자료구조' (배열과 자주 비교된다)C++ STL에서 list를 사용STL 사용 못하는 코테에서는 구

string 요소 참조 = s인덱스 / s.at(인덱스)공백 포함 입력할 때 = getline(cin, s) cin / getline() 같이 쓸 때에는 반드시 cin.ignore() 사용!(입력 버퍼를 비워줘야 올바르게 입력이 된다)

cursor = L.begin(); -> L.insert(cursor, 3) 하게되면it는 L.end()와 같은 위치에 있다.cursor = L.erase(cursor) 삭제 후 cursor의 값을 바꿔주지 않으면 cursor는 삭제된 값을 가지고 있다! 왜그러냐;li

원형 리스트처럼 구현하기 위해 검사해서 end()면 begin()으로 지정

: 한 쪽 끝에서만 삽입 / 삭제가 가능한 자료구조원소의 추가 / 제거 O(1)제일 상단의 원소 확인 O(1)제일 상단이 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능push / poptop / empty / size : 한 쪽 끝에서 삽입 / 다른 한 쪽

string -> int : stoi(string)int -> string : to_string(int)문제에서 말한 "0"이 int 여도 되는거였음; 어휴

문제 이해가 어려움; (참조 : https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220812563361&proxyReferer=https:%2F%2Fwww.google.com%2F )input

시간초과를 주의해야 하는 문제이다각 입력 뒤에 요소들과는 무관하므로 입력받으면서 처리해야한다input을 받았을 때 S.top()과 비교하여 S.top() > input 이 될 때 까지 S.pop()을 해야함stack을 인덱스와 요소 둘다 저장하기 위해 pair을 사용

풀이를 참고함;스택을 사용cnt가 80,000 까지 내림차순 합이 될 경우 숫자가 매우 커지므로 long long을 사용해야 한다.S.top() > arri 이 되어야 내려다볼 수 있기 때문에 cnt를 증가시킬 수 있다. 이 조건이 될 떄 까지 S.pop()그리고 나서

no인 경우는 두가지 이다.1) 닫힘 괄호가 들어왔을 때 열린 괄호가 없으면 false     (열림 괄호가 있을 때 까지 pop)2) 열리고 닫히지 않으면 false    (소괄호, 대괄호 열림 괄호 개수를 세는 배열 생성)다른 사람들 풀이를 보면 top만 비교해서

'(' 일때는 stack에 push')' 일때 1) 바로 직전이 '(' --> (레이저임) +stack.size()2) 바로 직전이 '('가 아니면 --> +1증가 경우를 잘못 파악해서 돌아서 코딩함; 이런ㅎㅎ;

입력이 올바르지 못한 괄호열은 stack을 사용해서 판별했음1) ')' 일 때 s.top()이 '(' 아니면 false;2) ']' 일 때 s.top()이 '' 아니면 false;3) 닫는 괄호 ')' 또는 ''가 들어왔을 때 stack.empty() 이면 false;

'}' 일 때 stack이 비어있으면 cnt++ 후 '{'로 stack에 삽입!'{{{{{{' 처럼 '{'이 연속으로 있을 경우 하나만 '{'개수의 절반만 바뀌면 올바른 괄호가 된다. --> cnt += s.size()/2;입력에서 '-'가 1개 이상 있다고해서 str

(본 글 참조 : https://www.youtube.com/watch?v=ftOmGdm95XI&t=1s )블러드 필(Blood Fill): 다차원 배열에서 연결된 영역을 찾는 유형BFS(넓이우선) / DFS(깊이우선): 이러한 블러드 필을 해결하는 알고리즘다

BFS 대표문제

방문을 표시하는 vis 대신 거리를 계산하는 dist사용dist를 최초 -1로 초기화 하기 위해 for문 + fill 사용pair<int,int> cur; --> auto cur; 로 사용 가능

정점 여러개에서 같이 BFS 시작하기 위해    \--> boardi가 1일 때 바로 Q.push({i,j});           동시에 disti도 0으로 만들어준다.max 함수 이용해서 크기비교시간초과 나기 쉬운문제라서 유의해야함1년전 코드보다 똑똑해진걸보니 멍청해

풀지못해서 답을 참고함BFS를 여러점에서 시작하는데 한쪽이 다른 한쪽에 영향을 주는 경우(서로 영향을 주는 경우는 이 방법 말고 백트래킹을 써야함;)불의 BFS를 먼저 해서 예상 도착 거리를 dist1에 구함지훈이의 BFS를 할 때 아래 두 조건이 반드시 && 여야 한

아이디어의 핵심은 BFS를 1차원에서도 사용할 수 있다는 생각1차원이든 / 2차원이든 정점사이의 거리를 구할 때 BFS를 사용할 수 있다는 생각!값이 변할 수 있는 범위(-1 / +1 / 2\*cur)은 dx3으로 해결이 문제는 운 좋게 수빈이가 100,000 이하에서

난이도는 쉬움문제에서 배추밭의 가로길이 = M                               세로길이 = N 이라고 해서N\*M배열로 접근했는데 반대였다.(?왜지? 알면 알려줘여)

기존 2차원 토마토에서 높이 -1 / 1 일때 까지 총 6좌표를 검사함6좌표 검사하는 방법1) 배열 1개 사용 2) 배열 3개 사용fill()을 이용해서 dist를 -1로 3차원 초기화 안되서 그냥 dist의 조건을 바꿈

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘귀납적으로 사고하는 방식이 필요(절차지향 사고를 탈피해야함)ex1) 도미노 N개가 있을 때 마지막 도미노가 쓰러지는이유 설명!  1번 도미노가 쓰러지면 -> 2번 도미노가 쓰러진다  2번 도미노가 쓰러지면

[ ASCII-CODE 표 ] > [ string -> int ] > [ char -> int ] > [ int -> char ]

크레인 인형 뽑기 > vector의 형태로 2차원 배열이 주어진다 같은 인형을 연속해서 2개 뽑을 경우 터지는데 터지는 인형의 개수를 구해야 한다. 어피치가 너무 귀여워서 시도해봤는데 풀릴줄몰랐음 (쉬운문제임ㅠ) 코드 >

동명이인을 처리하는 것이 문제의 핵심이라고 생각했다.두 문자열 vector를 정렬한 뒤 사전순으로 비교하면 된다고 생각했다.내풀이가 제일 효율적인 풀이와 같을 때 기분이 좋았다.

문제 난이도는 매우 쉽다.3 학생의 답안을 비교하는 방법을 효율적으로 하고 싶었다.게다가 max값이 여러개가 나올 수 있어서 귀찮은 8개의 조건을 다는 최악을 피하고 싶었다.다행히 가장 효율적인 코드와 같은 로직이여서 만족했다.

vector를 조작하는것에 익숙해지기 위한 문제였다v.begin()은 정확히 첫번째 원소를 가리킨다.programers에서 해당 오류는 어떤 수를 0으로 나누었을 때 발생하는 오류!

윤년이 포함되었기 때문에 2월은 29일까지 있다.월 / 일에 대한 정보를 받고 해당되는 요일을 출력하는 문제

3진법 변환 > 해당 문제는 3진법으로 변환하면 쉽게 해결되는 문제이다 > > 10진법을 n진법으로 만드는 과정은 다음과 같다. 1) 10진법의 수를 변환하고자 하는 숫자 n으로 나눈 후 (몫 / 나머지를 구한다) 2) 나머지는 순서대로 오른쪽에 위치시키며, 몫은 0

중복된 내용을 없애는 내용이다.나는 iterator를 이용해 앞 원소와 같으면 v.erase()하는 방법을 원했지만 시간초과가 떴다.(아마 for에서 N / erase()에서 N이 되어 O(N^2)이 되어서 그런것 같다)배열로 하면 굉장히 쉽게 풀리지만 unique()

compare()에 변수가 필요할 땐 전역으로 선언 후 사용하게 하면 된다!

문자를 비교할 때 아스키코드 값으로 비교하게 된다.A ~ Z 는 65 ~ 90 / a ~ z 는 97 ~ 122 까지 가진다.해당 문제는 그냥 내림차순으로 문자열을 정렬하면 해결되는 문제이다.

해당 문제는 숫자인지 판별하는 문제이며 <cctype>의 isdigit()을 사용해 판별함공백인지 판별하기 위해서는 역시 <cctype>의 isspace()를 사용한다추가로, 내가 받은 문자열이 숫자인지 / 문자들만 있는지 확인하기 위해 atoi()를 사용하

string.find()은 문자열 내에 특정 문자열을 찾는 것이기 때문에 쓸 수 없다.<algorithm>에 있는 find()를 사용해서 문제를 해결 할 수 있다원하는 문자열을 입력한 뒤 seoul.begin() 을 빼주면 인덱스를 구할 수 있다고 한다 (참조함)

일반적인 방법으로 소수를 찾으면 O(N^2)의 시간복잡도를 가져서 시간초과가 나온다.즉, 에라토스테네스의 채를 사용해서 O(N\*logN)의 시간복잡도를 유지해야만 성공할 수 있다. 에라토스테네스의 채 원리 : 어떤 수의 배수가 되는 수는 소수가 될 수 없기에 미리 f

stoi()가 음수까지 커버 가능한지 궁금해서 처리했으나, 음수까지 전부 알아서 해줌;똑똑한 stoi() atoi()도 마찬가지로 음수까지 커버가 된다.

대소문자별로 값을 다르게 처리해줘야 한다.대/소문자의 아스키코드 값을 알면 편하다

대 / 소문자를 만들기 위해 toupper() / tolower()를 사용해서 처리할 수 있다.

n이 21억이 넘어가기 때문에 int로 불가능 ! --> long long 사용 해야함문자열로 바꾼 뒤 정렬하면 해결됨stoll()은 string to long long 이라는 의미를 가지고 있음조건을 함수로 만들지 않아도 내림차순 / 오름차순은 간단하게 표현 가능

제곱근이 정수인지 판별하기 위한 2가지 방법이 있다.방법 1) 제곱하여 정수값인지 확인하기방법 2) int형으로 강제 변환해서 비교하기sqrt() 와 pow(), powl(), powf()는 <cmath>에 있다.(반환형이 double / long / float이

<algorithm>의 find는 찾으면 해당 요소의 iterator를 반환 /찾지 못하면 v.end()를 가리키게 된다!<algorithm>에 해당 stl에 min/max를 찾는 함수가 있다!1) min_element() : 최소값에 해당하는 요소의 ite

\* a와 b의 최대공약수(gcd) / 최대공배수(lcm) 는 gcd\*lcm=a\*b를 성립한다유클리드 호제법으로 최대공약수를 쉽게 구할 수 있다.

<numeric> 헤더 안에 있는 accumulate()를 이용해 간단히 구할 수 있다

최초 값이 정해지지 않은 vector<vector<int>> answer 에 대해서바로 answeri 이렇게 접근하는 바보같은 행동을 했다.생각해보니 우리가 담을 vector는 크기가 정해져 있지 않아 접근이 불가능 하다!이 때 사용할 수 있는 것이 vect

최초 정답을 풀 때에는 이진화 과정을 거쳐 각각 배열에 표시한 후 || 연산을 통해 정답을 추출함처음에 vector\[i].resize(n)을 한 후 vector\[i].push_back()을 하는 바보같은 행동을 함(이미 0으로 초기화 해서 생성 해놓고 그 뒤에 pu

위 문제를 해결하기 위한 키포인트는 2가지1) 각 state의 실패율 구하기2) sort하기 위한 compare 설계 & pair<int,double> 변수 사용나는 다 순조롭게 해놓고 실패율을 구하는 과정에서 double 자료형으로 나누지 않고int로 나누고 있

입력에 따라서 잘 구분하여 값을 처리해주면 어렵지 않게 풀리는 문제이다받은 문자가 숫자인지 확인하기 위해서는 isdigit()을 사용하면 된다.다른사람들의 해답속에서 stringstream을 알게되었음: 입력받은 문자열에서 공백(' ') 및 개행('\\n')을 제외하고

해당 문제는 하라는 대로만 하면 되는 문제이다나는 거리계산에 있어서 나도 모르게 실제 좌표간 거리계산을 적용해서 답이 틀리게 나왔었다.(sqrt + pow 하지말고 그냥 절대값인 abs를 이용해야 하는듯 --> 실수라서 동등처리가 달라지는것으로 추측!)

해당 문제의 keypoint1) 체육복 여분이 있는 학생이 도난당한 경우 처리iterator / find / vector.erase 를 자유롭게 사용하여 문제를 해결함vector.erase()의 반환값은 삭제된 후 다음 요소를 가리키는 iterator이다\--> 만약

처음에 보고 당황했다. 하지만, keypoint는 결국 3가지로 표현한다는 것을 알아야 한다하다보면 3으로 나누었을 때 나머지가 0인 경우에만 계속 어긋난다는 것을 깨달았다.\--> 나머지가 0인 경우에만 예외처리를 해주어야 한다!

1) 해당 좌표중 그래프보다 같거나 작은 좌표들을 vector<pair<int,int>> p 에 넣는다.2) p에 있는 좌표들을 대상으로 사각형을 만들 수 있는지 검사한다!: 해당 풀이로 답을 구할수는 있다. 하지만 이미 (1번)과정에서 O(N^2)의 시간복

풀이의 원리1) 각 옷 종류들이 몇개씩 있는지 개수를 카운트 해서 vector에 넣는다2) 각 종류마다 선택지는 총 (개수+1)개가 있다 --> 선택하지 않는것도 포함3) 조합(nCr)을 이용해서 개수를 구한 뒤 마지막에 1을 뺀다 (아무것도 선택하지 않는 경우)map

map을 적절하게 사용한 풀이가 핵심이다 map에서 특정 value로 sort하려면 vector에 복사 후 compare함수를 작성해야 했다! (매우중요 -\_-)map은 pair를 사용한 구조로 되어있음을 망각하면 안된다map / vector와 같은 container

string으로 변환한 뒤 정렬 조건으로 실제 정수로 변환한 뒤 값 비교를 해서 처리해서 해결함answer="00" 이렇게 되는 경우 예외처리를 해줘야 하는 것이 키포인트!

H-index 코드 [ 내 풀이 ] > 직관적으로 생각할 수 있는 풀이 (시간복잡도가 좋지는 않아보임) **1) 계차수열을 이용해서 n번 이용된 논문의 개수를 모두 구한다 2) n번 이상 인용된 논문의 개수가 n보다 크거나 같으면 break!** > [ 최적 코드

직관적인 풀이법시간복잡도가 아슬아슬해 보인다O(N^2) 보다 효율적이게 만드려다가 시간이 많이 소모되었다.(이럴 때에는 한번 해보는게 더 좋아보인다ㅠㅠ)스택을 사용한 방법이 더 빠른 해결 방법!값이 아닌 인덱스를 활용한 것이 key point!

key point!1) queue가 가득찼을 때 pop() 과 push()가 하나의 cycle에 존재해야 한다.2) pop() 다음에 push()를 해주는 순서가 중요!3) queue의 size()로 pop여부를 확인하기 때문에 빈 값(0)을 넣어주어야 한다!4) 마

깨달음1) pair<int, int>자료형을 가진 container에서도 max_element를 사용할 수 있다2) queue는 순회도 안될 뿐더러, iterator 자체가 없다!!!      \--> 필요하다면 deque를 queue처럼 쓰는게 더 좋음

소수와 관련된 문제시 사용할 수 있는 것들1) 숫자 n이 소수인지 판별 (isPrime)2) 1~n까지 소수 판별 (에라토스테네스의 채)로직1) 수의 최대 범위 구하기      : numbers를 내림차순 정렬한 뒤 stoi()로 바꾸어 최대 숫자 크기를 구함2) 최대

keypoint!1) 가로 / 세로를 사용하여 주어진 brown / yellow와 관련된 식을 찾기2) 해당되는 조합을 찾기: yellow=(가로-2)\*(세로-2) 를 만족시키는 가로, 세로 조합을 찾는 것

key point!1) 조이스틱을 위/아래로 움직이는 것의 선택은 min을 이용해 해결2) 조이스틱을 왼쪽/오른쪽 으로 움직이는 것의 선택은 먼저 'A'가 아닌 요소가 발견할 때 까지 찾기 \--> 바꾼 name의 값을 'A'로 치환해주는 작업이 필요!

아직 Greedy 유형에 대한 느낌이 오지 않음풀이는 이해가 되는데 왜 그렇게 풀었는지 근본적인 접근을 모르겠음

같이 탈 수 있는 사람과 탔을 때, 가장 여유공간이 적게 남는 경우가 효율적!해당 경우를 찾기 위해 이중 for문을 썼더니 효율성 검사에서 실패함같은 결과를 내지만 정렬 후 head / tail로 접근을 하면 훨~씬 빠르다! (..이런게 알고리즘의 힘인가)주의해야 할

풀이법1) 주어진 스킬트리 (BSCDA) 에서 해당 스킬 (CBD)들의 인덱스를 벡터에 저장2) 벡터에 저장된 인덱스들이 조건에 만족하면 count!1) 해당 skill_trees에서 우리가 원하는 skill들과 비교하며 발견 시 순서대로 벡터에 삽입2) 벡터에 존재하

문자열이 n일때에 1 ~ n/2개 의 단위로 자를 때 까지 개수를 구한 뒤 최소를 구해야 함3중 for문으로 구조가 구성됨1) slice for문 : 1 ~ n/2개 단위로 자르는 큰 틀2) 비교 할 기준이 되는 문자 for문3) 비교 할 대상이 되는 문자 for문예

1) 각 수들을 묶음별로 2차원 배열 형태의 vector에 저장함2) 각 층마다 head / tail 이라는 변수를 두고 증 / 감 해가면서 특징을 찾아서 해결함key point !1) 3개의 패턴을 state라는 변수로 관리2) 각 패턴 내부에서 일어나는 연산 수에

중복 제거를 할 때 sort -> erase + unique 를 써야한다.(정렬되어있지 않은 상태라면 제거를 안함 -\_-;)

어려워 보였지만 생각보다 쉬웠음!10진법이 넘어갈 경우 알파벳으로 치환해야하는데 number 배열을 이용하는 좋은 방법을 배움!

이중 for문으로 차례차례 더하는 방법을 통해 테스트 코드는 돌아가지만, 효율성 검사에서 탈락하게된다ㅠㅠ연속된 숫자들을 더하다가 크거나 같아질 때 값을 빼면서 균형을 맞춰주는게 key point!

최댓값과 최솟값 > 코드 >

깨달음1) <algorithm>의 find()를 사용할 때 전체 범위가 아닌 경우에서 찾을때 못찾으면        \-> v.end()가 아니라 해당 범위의 바로 다음을 의미함ex) find(v.begin(), v.begin()+2, str);        :우리

sstream을 통해 숫자만 꺼내오려고 했으나 실패함 \--> 테스트 해보니 문자열에 숫자 외에 다른 값들이 있으면 구분하지 못함ex1) str = "{{12,13}}" / str = "{{ 12 }}" / str = "12,13"(이거는 12만 가져옴)결국 sstre

캐시(cache) 공간을 vector<pair<string,int>> 자료형으로 만들었음\--> string은 지역 이름, int는 LRU 수행하기 위한 최근 들어간 idx값LRU 수행 로직 (LRUpair은 다음에 빠져야 할 pair!)1) cache에 해

모든 수를 대상으로 최소 공배수를 구하려면 각 약수들의 최대 차수들의 곱이 필요하다고 생각했음그래서 모든 수의 약수를 구했고, 최대 값들만 map에 저장하여 계산했음밑에 풀이가 더 간단하고 똑똑한 풀이!key point!: 앞에 2개씩 차례차례 최소 공배수를 구하면 결

아무리 생각해도 안되는게 이상해서 찾아봤더니 c++ STL의 sort는 불안정 정렬이라고 한다!!!!!<algorithm>'s sort()는 퀵정렬로 이루어져 있기 때문에 불안정함! (이유 : 퀵정렬은 같은 데이터를 비교할때 서로 바꿔주기 때문입니다. 문제는 같은

합이 어떤 경우의수로 나오느냐에 따라 개수를 count해야한다. 해당 코드는 오답이다 --> map을 사용해 중복으로 나오는 합은 1개로 생각했기 때문문제에서 이것과 관련된 근거가 없어서 조금 헷갈려했다.sum이 같은 value가 나오더라도 조합의 경우가 다르면 갯수를

피보나치 수열을 만들기 위해 재귀보다 DP방식이 빠르다는 것을 알아야 한다모듈러 연산 성질 을 통해 합을 줄이는 방법을 알고 있어야 한다.피보나치의 경우에 재귀는 비효율적이기 때문에 DP방식으로 점화식을 구해서 속도 향상!또한 어떤 수로 나누라는 문제는 모듈러 연산 성

정석적인 BFS 풀이

stringstream을 유용하게 쓸 수 있는 케이스!

DFS는 stack으로 구현할 수도 있지만, 재귀로도 구현될 수 있음을 기억하자DFS의 원리는 깊게 하나의 경우의 수를 처리하는 것으로 생각할 수 있음

deque을 사용해서 모든 테스트코드는 성공했지만 효율성 검사에서 실패했다\--> 정렬을 할때 시간 초과가 난다고 추측됨 priority_queue를 사용해서 원소 삽입과 동시에 정렬이 되게 하여 시간을 단축했다.주의할 점1) 일반 queue에는 q.front()로 앞

로직1) 각 문자열에서 2개씩 나누어 map에 저장2) 교집합 구하기 : 공통으로 있는 원소 중 min개수인 것3) 합집합 구하기 : 원소 개수의 max 개수isalpha(ch)를 사용하면 알파벳인지 검사해준다!map을 안쓰고 배열 or 벡터를 쓴다면?: 26\*26크

단순히 string에서 삭제하는 방식으로 하면 --> O(N^2)효율성과 관련한 문제에 부딛히면 '자료구조'를 바꾸는 것을 생각해보기!이전 값과 현재 값의 상관관계가 있는 경우 stack을 고려해보자!

정해진 로직에 따라 차근차근 구현하면 풀리는 문제

모든 경우의수를 처리하는 방법을 못찾아서 힌트를 참조함key point!1) 모든 cloumn의 경우의수를 구해서 정해놓아야 한다    : 1 << Col의 수 로 모든 경우의 수의 개수가 나온다      ex) column이 4개일 때 1<<4

key point!: 연산자의 종류 개수에 따라 가능한 조합을 구하는 것이 관건<algorithm> 에 next_permutation()을 이용하면 현재 조합에서 다음 순열을 구할 수 있음!tmp배열에 0, 1, 2, 3, 4 가 있을 때0,1,2,3,4 ~ 4,

key point!1) 빙하의 위치에서 4방을 검사하여 주변이 바다(0)인 것 만큼 감소!2) 감소하는 과정에서 실시간으로 값이 board에 반영되면 안된다 \--> 같은 해에 같이 녹는 빙하인데 만약 실시간 변경이 되버리면 옆 빙하가 녹고 난 후 다음 빙하를 계산할

모든 좌표에 대해 bfs를 하는 것 보다는 거리를 구하는 것이 더 빠르다 (내 풀이)나의 풀이 로직1) 각 섬의 개수 별로 섬의 모든 좌표를 저장한 queue를 구한다2) 모든 섬에 대해 각 섬의 모든 좌표들 간 거리를 구해서 최소값을 갱신한다많은 사람들의 풀이 로직1

dx\[] / dy\[] / dz\[] 3개의 범위를 잘 지정해야한다 (6개에 방문 가능)fill을 이용한 3차원 배열 초기화

key point!: 현재 값의 2배로 이동하는 cost가 0이기 때문에 가중치가 제일 높아야한다. --> 가장 먼저 이동하게 dx\[] 조정!(관련 반례 : 0,2 --> 1이 나와야 함!)

BFS로 해당 depth를 구한 뒤 DFS로 그 경로 출력해서 해결경로를 일일히 vector에 추가하다보니 시간초과가 난 것 같다key point!: 자신의 parent를 저장하는 parent\[]를 사용한 후 거슬러 올라가 출력!

key point!: 연속된 3개의 계단을 밟을 수 없다      \--> 2차원 배열로 경우의 수를 나눠야 함N == 1일때 예외처리

타일 하나의 입장에서 생각을 해봐야 함!나누기 문제는 보통 모듈러 연산의 성질을 사용하면 해결됨

Prefix sum 개념이 사용prefix sum 이란?: 원하는 연속된 구간의 합을 구할 때 prefix sum의 차로 구할 수 있는 원리 --> O(1)의 시간복잡도

DP에서 값을 추적하기 위한 방법: pre\[] 배열을 사용해서 순회!

문제 이해 (백준설명이 별로임; 프로그래머스는 괜찮음): 맨 위에서 가장 아래층까지 내려오는 경로 중 최대 값을 구해라 풀이삼각형의 요소를 2차원 배열에 담아서 해결해야 한다 삼각형의 맨 앞 / 중간 / 맨뒤 이렇게 3가지 요소의 종류가 있다고 볼 수 있음\--> 3

int -> 21억 --> 1억대 까지 커버 가능 (10^8)long long -> 10^18까지 커버 가능unsigned long long 이 제일 큼

해당 문제는 결과적으로 피보나치 점화식으로 풀리긴 한다.하지만, 이것은 해당 문제의 본질을 파악한 것은 아님key point! (본질을 파악한 풀이)1) 해당 자리수에서 끝이 0으로 끝나는 요소는 0과 1이 붙을 수 있다ex) 100 -> 101 / 1002) 해당 자

로직1) 입력 그대로 vector에 저장2) 시작시간을 우선으로 정렬 (같으면 종료시간이 짧은 순서대로)3) 2중 for문으로 순회하면서 최대 경우 구함결과: O(N^2) 코드로 시간초과!(1초에 대략 1억개의 연산을 하니까 2초라서 2\*10^8정도까지 되는데 지금은

로직1) 로프의 길이를 오름차순 정렬2) for문을 순회하며 v\[i]\*뒤에남은 개수의 최대값을 구하며 MAX갱신(적어도 내 값으로 내 뒤에 남은 개수만큼은 들 수 있기 때문)

원리: 어차피 각 A의 최소값xB의 최대값을 해주면 곱이 최소가 되니 둘다 정렬해서 곱하자로직1) A,B배열 모두 정렬2) A\[i] \* B\[(N-1)-i]로 최대와 최소를 곱한다

원리: 최대한 많은 수를 빼는 것이 핵심로직1) -가 나오면 다음 -가 나올 때 까지 수를 save에 쌓는다2) 다음 -가 나오면 쌓인 save를 빼고 다시 save를 지금 읽은 수로 치환

원리: 뒤에 최상위 레벨부터 내려오면서 최소한 차이가 나도록 감소주의할 점: 처음에 하위 레벨부터 맞추다보니 내가 맞춘 앞 레벨보다 다음 수가 더 작아지는 경우가 생김ex) 10 5 4 9 일 때1) 앞에서부터 맞추면 4 3 4 9 가 된다.- 오답2) 뒤에서부터 하

깨달음1) 컨테이너 선언 후에 값을 추가하지 않고 v.size()하면 오류난다 ㅠㅠㅠ2) 곱셈 / 음수 이 두가지가 있을 때에는 반드시 0과 1처리에 대해 고민하자 로직1) 수를 음수/양수로 분리해서 받는다(0은 음수로넣어야함 --> 음수와 곱해서 없어질 수 있기 때

싸피 Computational 문제에서 나왔던 문제..!최초 시도1) 1과 0의 개수를 모두 구하면서, 연속된 1과 0의 카운트를 센다2) 더 적은 개수의 연속된 카운트를 반환\--> 생각해보니 어차피 연속된 것은 하나로 칠 수 있으므로 1과 0의 개수를 세는것은 의미

이해: 해당 문제는 OPT라는 스케줄링 알고리즘 기법을 구현하면 해결되는 문제!(OPT란 ?페이징 대체 기법중 하나로 현재 유지하는 요소중 가장 마지막에 사용되는 요소를 대체해야 최적의 경우가 나오는 것!)원리(opt 스케줄링 알고리즘)1) 각 전자기기의 번호별로 사용

맞다고 생각했던 로직1) 강의가 끝나는 시간에 따라 정렬한 후 비교하며 해결\--> 강의가 끝나는 시간으로 정렬할 경우 시작 시간이 누락하는 경우 발생2) 강의가 시작하는 시간에 따라 정렬한 후 단순 차례 비교만 한 경우(위 코드)key point!1) 입력을 시작 순

key point!: DP로 생각하는 사고방식을 떠올려야 함ㅠ원리: 큰 정사각형을 이루는 조건은 작은 정사각형을 이루는 조건으로 표현될 수 있다. D\[i]\[j] = min(D\[i-1]\[\[j-1], min(D\[i]\[j-1],D\[i-1]\[j])) + 1;

로직: board판을 만들어서 에라토스테네스의 채 처럼 수를 적어나가는 방식문제1) 시간초과ㅠㅠ2) 메모리 영역 초과(스택 영역): 지역변수의 메모리는 스택 영역에 포함되어 스택 크기에 따라 제한이 걸리게 된다.그러나, 전역 변수로 사용하면 힙 영역에 포함되어 보다 큰

key point!1) \`\`\`2) sort에서 사용하는 compare()정의 할 때 return false이면 교환하지 X\*\*

로직: 전체 sum에서 특정 난쟁이 2명의 키 합을 뺐을 때 100이 되는 경우에 바로 break!

로직: 1부터 N까지 문제에서 시키는대로 분해합을 구했을 때 N이되는거 찾

로직 1) 오른쪽 칸 / 아래 칸 2개에 대해 현재 좌표와 board\[]\[] 교환2) 바뀐 board\[]\[] 에 대해 가장 긴 사탕 길이를 찾는다3) 1~2를 모든점에 대해 수행하며 MAX값 갱신

key point!: board\[51]은 최대입력인 1000보다 크니까 전체범위를 51로 해도 충분함! (시간이 엄청 단축된다)

정답을 참조한 문제 --> 핵심 로직을 파악하지 못함로직1) arr\[123] ~ arr\[999]까지 모두 true로 초기화2) arr\[123] ~ arr\[999]중 최초 조건에 맞지 않는 숫자는 false처리(조건 : 1. 각 자리 중 하나라도 0인 것     

로직1) 전체 체스판을 origin\[]\[]에 저장2) 전체 for문 틀로 a=N-8 ~ b=M-8까지 돌며, board\[]\[]에 정해진 범위까지를 복사!3) 8x8 체스판인 board\[]\[]에서 맨 왼쪽 위가 'W' 경우 / 'B'경우 가정해서 최소 변경회수

key point!: a^n \* a^n = a^2n 이라는 곱셈의 특징을 재귀로 구현하는 것!재귀재귀를 종료하는 base condition을 잘 정해야 한다함수의 return을 잘 정해야 한다

핵심 :하노이의 탑 풀이에 필요한 과정을 찾기1) 가장 큰 원반 n을 제외한 n-1개의 원판을 나머지 기둥(2기둥)으로 이동2) 원판 n을 3기둥으로 이동3) 원판 n-1개를 2기둥에서 3기둥으로 이동key point!: 원판을 옮기는 과정을 재귀로 풀어낼 때 움직이는

각 범위를 depth로 두고 타고 들어가서 차례대로 수행하게 하였음모든 범위에 대해 수행하므로 0.5초 시간동안 수행할 수 없음시간 초과 해결: 모든 사분면에 대해 find하지 않고, 검사해서 안에 없으면 해당 size\*size만큼 더하기로직1) 현재 좌표에 대해 s

앞 재귀문제와 유사한 문제key point!: 입력이 2^n이기 때문에 맞춰서 size를 조정하며 탐색!

원리1) 일정 구역에서 항상 중간에 해당되는 부분은 ' '값을 가지도록 저장(y와 x의 범위가y+size/3 ~ y+size/3+size/3x+size/3 ~ x+size/3+size/3 일 때 항상 ' '값을 가짐)2) 가운데 부분을 제외하고 나머지 8부분에 대해 재

로직1) board\[]\[]를 모두 ' '으로 초기화2) x좌표 N을 중심으로 증가해가며 별모양으로 init!3) 현재 중앙 삼각형 부분을 공백처리한 후 재귀로 순환!주의할 점1) 배열의 높이는 최대 N / 넓이는 최대 2N 이다!2) x좌표가 0인 부분은 출력하지

이제 별은 그만..

깨달음char\[]\[] 배열로 문자열을 입력받을 때에는반드시 +1만큼 더 크게 해야한다\--> 마지막에 null문자가 삽입되기 때문에!!! 안그러면 참조가 벗어나서 BOJ에서 메모리 초과라고 뜬다!주의할 점 !: 기존에 입력을 이렇게 받았더니 에디터에서는 잘돌아가는데

백트래킹 문제 유형: 특정 조건을 만족하는 모든 경우의 수를 수행하는 방법(경우의 수를 진행하다가 막히면 가장 마지막으로 성공한 부분으로 돌아가 다른 경우로 진행하는 것 -> 백트래킹)

백트래킹의 대표적인 문제\--> 해당문제를 완전탐색으로 하는 것보다 훨씬 효율적임        (백트래킹은 조건을 만족하는 모든 경우를 돌기 때문)문제 이해: 퀸은 같은 행/열/대각선 으로 이동할 수 있다. 즉, 가능한 모든 경우는 한 행에 하나의 퀸이 있을 것이기 때

주의할 점1) 일단 모든 요소는 순회해야 한다      \--> 그렇지 않으면 S가 0일때 경우 세지도 않고 바로 종료함2) isused\[]는 일정 개수의 조합으로 개수가 정해져 있었기 때문에 이를 파악하기 위해 사용했던 것임. 여기서는 쓸 필요가 없음

다음 시작될 순서인 start변수를 넘겨서 큰 순서로 만듬!

중복 포함이니 그냥 재귀로 돌리면 된다

수가 정해져 있기 때문에 save 변수를 쓰는데, 사전순 증가로 출력해야 하기 때문에 정렬하려고 vector<int> save로 선언next_permutation()을 2중으로 써야함1) 전체 N개에서 M개를 뽑은 숫자들 구하는 do~while2) 뽑은 M개 숫자

key point!: 시작이 같은 수열에서 같은 값을 출력하지 않게 조건을 만들어야 한다(sort하고 func실행하기 때문에 바로 이전값을 저장하는 변수를 써야함 prev)로직1) 2중 do~while()로 N개중 M개를 뽑는 모든 조합을 구한다2) ans를 정렬한뒤,

최소 모음 1개, 자음 2개인 조건을 조심해서 구현

핵심: N-Queen문제를 풀때 사용했던 대각선 2개에 대해 isused\[]를 선언해 해결문제: 시간초과 발생문제 해결: 기존 코드 로직 + 흰색과 검은색 체스판은 서로 영향을 주지 않아서 서로 나눠서 해결해야 한다는 아이디어가 필요이러한 체스판에서 비숍이 대각선으로

분석 이유: 백트래킹이 내가 생각한 경우의수를 만족시키지 않아서 분석할 가치가 있다고 생각로직1) 모든 점들에 대해 4방향으로 백트래킹 실시2) depth == 7 이고 'S'가 4개 이상이면 ans++실패 이유1) 해당 코드는 하나의 막대처럼 검사해서, 중간에 뻗어나

어려웠던 점문제 이해를 잘못함문제에 처리해야 할 예외가 나와있는 것은 좋은것문제가 많다고 대충읽지 말고, 꼼꼼하게 읽고 이해하고 처리하기key point!1) 전형적인 백트래킹 로직의 원리를 지켜줘야 한다     \--> 내가 한 행위를 원상복귀 하는 과정이 항상 필요

로직1) 배양액을 뿌릴 수 있는 땅의 수에서 R과 G의 개수만큼 뽑는 모든 조합을 구한다 (next_permutation())2) green과 red에 대해 BFS를 실행해서 꽃이 피는 수만큼 count!어려웠던 점green에서 큐를 돌릴 때 꽃이 폈는지 검사하는 걸

문제: N이 너무 커서 시간초과key point!: DP의 핵심인 메모제이션(memoization)을 사용해야 한다

key point!: map<string,int>와 string.substr()을 사용로직1) map 자료형인 dic에 알파벳 A~Z까지 등록2) w와 c를 string.substr()로 구하고 사전에 있으면 cnt증가해서 길이를 늘림3) 사전에 없으면 w를 an

로직1) tmp로 움직인 후 범위 벗어나면 continue2) 범위가 벗어나지 않으면 x,y좌표로 2방향 문자열을 만들어 map으로 처리

key point1) board판에서 사라지는 블록을 sort로 해결하기 위해서 vector<vector<pair<char,int>>> v;에 저장함2) sort() 대신 stable_sort()사용깨달은 점1) sort()는 퀵정렬로 구현되어 있어서

key point: (sm+1)/2 == (lr+1)/2 일 때 현재 같은 대진에 있다는 조건

key point!: DFS로 하나의 점에 연결된 모든 점을 방문 체크하면서 네트워크 개수를 세야 한다!

단어 변환 > 코드 >

깨달은 것: vector<vector<string>>> ansList 자체를 오름차순으로 꺼내려면sort(ansList.begin(), ansList.end()); 로하면 된다(기본 sort에서 vector<string>에 대해 알아서 정렬 해줌)

key point!작업의 요청부터 종료까지 걸린 최소시간 \--> 해당 시간까지 들어온 요청중 작업시간이 짧은 것부터 실행했을 때!깨달은 것: priority_queue<pair<int,int>> 특정compare함수 만드는 법: struct로 구조체 만든

처음: 우선순위 큐 2개(내림차순, 오름차순)으로 유지했을 때 순서가 바뀌면서 최대, 최소값도 달라져서 쓰지 못할것이라고 생각함결과: 각 큐의 전체적인 순서는 보장이 안되지만, 최대,최소는 각각 관리하기 때문에 최대,최소 만큼은 2개의 큐의 연산에서 보장이 된다!!주의

강의실 배정 문제와 비슷하다고 판단느낀 점과거에 풀었던 그리디 문제 강의실 배정 문제와 비슷하다고 판단함(일정 시간 동안 최대로 겹치는 개수를 구해야 하기 때문)sstream을 매우 유용하게 사용했음(공백으로 분리된 값 가져올때는 진짜 최고)핵심1) 요청 처리시간이 빠

시간초과: 문자열 s의 길이가 2500까지라서 엄\~~청 크다 --> 터무니없이 실패ㅎㅎ(재귀를 이용해 푸는 문제들은 대상인 N이 10만 되도 최대O(2^n) 정도로 급격히 커짐)접근 정답이 짝수일때와 홀수일 때 다르게 검사 해야한다는 것을 느껴서 나눔\--> 이렇게

경주로 건설 > 코드 > [ DFS풀이 - 실패 ] 결과 에 계속 실패가 떴음 하는 의 순서를 바꾸니 성공하긴함 --> 안정적인 풀이는 아닌 것 같다 (실제 구글링으로 찾은 dfs풀이들도 방향을 바꾸니 오답처리

핵심: DFS / BFS 모두 풀리는 문제지만 그래프의 양방향성을 생각하는 것이 중요반례일 경우에 단방향으로만 검사하면 3은 감염되지 않았다고 체크된다

촌수계산 > 코드 >

silver인데 많이 해매서 정답을 참고함 아직 그래프에 대한 문제의 이해가 부족하고 사용에 미숙함핵심각 정점끼리 이동할 수 있는 조건은 맥주 20개로 즉, 1000미터 안에 있는 점이라는 것조건에 따라 연결된 간선을 양방향으로 넣어두고 출발지 ~ 도착지까지 연결되어

느낀 점각 cctv별로 방향을 정해주는 과정이 복잡함 --> 뒤 풀이에서 단순하게 처리재귀를 쓰다보니 board\[]\[]를 값만 복사하기 위해 새로 만든 뒤 일일이 복사함핵심cctv별로 가진 방향의 수가 다르다 (각자 4,2,4,4,1 가지)이 때 각 cctv가 4가

깨달은 것자꾸 시간초과가 왜나는지 봤더니 무심코 for(1~N)안에서 done\[]를 초기화 시켜준 것 때문이었음: fill()함수는 결국 O(N)의 시간이 거리는걸 간과하고 있었다.무심코 쓰는 STL 함수의 시간복잡도를 잊지 말자;핵심arr\[]에 숫자를 입력받고 확

로직'1'이 들어간 모든 좌표에 대해 하나씩 값을 바꿔보며 BFS를 수행해 최소값을 찾기실패 이유: 시간초과핵심board\[N]\[M]의 입장에서 각 칸은 벽을 부수고 온 경우 / 벽을 부수지 않고 온 경우로 2가지가 존재\--> cost\[2]\[N]\[M] 으로 각

벽부수고 이동하기 와 매우 유사한 문제핵심이 문제 역시 cost\[K]\[H]\[W]로 각 칸에서 말처럼 가는 능력을 K번 쓰고 온 경우를 모두 계산주의할 점 : cost\[K]\[H]\[W] 비교할 때 같으면 큐에 무한히 쌓여서 메모리 초과가 된다 !!!

로직BFS로 현재 L --> L 가능한지 검사BFS로 물에 인접한 빙하 녹이기결과: 시간초과! (해당 문제는 O(N^2)까지 허용)시간 복잡도 check() --> O(N^2)melt() --> O(N^2)최악의 경우에 가장 대각선에 백조(L)가 있고 나머지 다 빙하일

로직: 다익스트라를 활용해서 1번 노드에서 모든 노드까지 거리를 구한 후 최대 개수 구함결과 시간초과 해당 문제의 시간 복잡도는 O(NlogN)이다이 문제는 굳이 다익스트라를 쓰지 않아도 BFS를 하면 O(N)이 가능함로직: BFS를 써서 연결된 모든 정점까지 최단거리

나의 시도들각 사람의 이긴 횟수를 구해서 반드시 승리하는 경우를 찾으려고 시도함 --> 실패모든 사람간의 승/패에 대한 표를 구했으나 확실히 순위를 정해진 사람의 조건을 찾지 못함 --> 실패해답: 플로이드 워셜 알고리즘을 이용해 각 선수의 총 경기 횟수를 구하면 됨정

모든 풀이는 얍문님을 참조(https://yabmoons.tistory.com/606)핵심(방을 만드는 조건)이미 방문한 정점을 다시 방문하는 경우(vis) 간선이 처음 만들어 지는 경우(make)예외 처리(교차)교차시 정점으로 체크할 수 없는 2개의 방이 만

로직: N명의 사람들을 절반으로 나누는 모든 조합을 next_permutaion()으로 구하고 합의 최소를 찾는다

로직총 치킨집의 개수 중 M개를 뽑는 조합으로 치킨집을 고름치킨집과 집간의 치킨거리를 구해서 최소값을 찾음

key point가장 먼저 나오는 수가 제일 작은수이기 때문에 바로 exit(0)으로 종료해주는 것느낀점조건을 걸었기 때문에 O(3^N)까지는 아니더라도 시간이 많이 나올것같아서 백트래킹을 못하지 않을까 했으나 exit(0) 덕분에 해결exit(0)으로 프로그램을 바로

key point해당 좌표에서 가능한 숫자가 없으면 바로 return; 으로 종료시켜줘야함(그렇지 않으면 그대로 0인 값을 가지고 다음 depth를 실행하기 때문;)

key point각 나무들 간의 간격의 크기들을 모두 구해서 모두에 대한 GCD(최대 공약수)를 구해야 함ans = 심을 수 있는 나무의 수 - 미리 심은 나무의 수심을 수 있는 나무의 수 = (마지막 나무 위치 - 처음 나무 위치)/gcd + 1(마지막 +1은 처음

느낀 점2개의 변수로 이동해가면서 합을 구하는 것은 알았으나, 두 포인터의 예외상황 처리가 난감했음\--> 이것을 깔끔하게 정리한게 투포인터 알고리즘 이라는 것이 있었음로직2개의 포인터를 움직여가며 부분합을 구하는 것사실 기존 풀이와 같으나, 두개의 포인터 예외처리를

정리소수중 2를 제외한 모든 수는 홀수모든 4이상의 짝수인 정수는 두 소수의 합으로 나타낼 수 있다(적당히 큰 수에서 증명 완료)풀이 방법 2가지O(logN)로 소수판별 가능한 밀러-라빈 소수판별법 이용하는 방법골드바흐의 추측 + 에라토스테네스의 채 이용 (우리가 사용

key point이번에 0좌표를 따라 도달할 수 있는 1의 좌표 = 이번에 녹을 치즈 & 다음에 돌아야 할 air

느낀 것: 재귀를 통한 완전탐색풀이밖에 떠오르지 않아서 결국 힌트를 참조풀이: DP를 이용한 풀이를 해야한다 (DP\[i] = i개의 카드를 뽑는데 필요한 최대 비용)

로직: 조건에 맞게 백트래킹을 수행하면 된다(입력이 10보다 작기때문에 충분히 가능)

로직나무의 최대 길이를 구한다이분탐색으로 최적의 나무 높이를 구한다주의합을 구하는 tot변수는 반드시 long long 혹은 그 이상이어야 한다

로직: 최적의 랜선 길이를 찾는 탐색을 이분탐색으로 하여 찾는다주의: 이분탐색을 할 때 항상 나누는 수인 mid가 0이되는 경우를 찾아 예외처리를 해주어야 한다(본 문제: N=1, M=1, input=1일 때 mid가 0이되므로 최초left를 1로 초기화)

key point: 정상에서 미끄러지지 않으므로 결국 가야 할 거리는 V-B인것을 캐치하는 것

예산 > 코드 >

이분탐색 문제에 적응중이분탐색 구현시 주의답을 기억하는 =(등호)가 붙는 방향은 앞으로 답이 될 수 있는 가능성이 있는 쪽에 붙여주어야 한다left의 초기값을 0으로 하면 나누는 값인 mid가 0이될 수 있으니 1로 초기화하자

로직2개의 우선순위 큐(최대힙-maxPQ, 최소힙-minPQ)을 생성maxPQ 부터 시작해서 번갈아가면서 값을 넣는다만약 maxPQ.top() <= minPQ.top() 을 만족하지 않으면 값을 swap한다: 최대힙 큐의 top은 항상 최소힙 큐의 top보다 작아

핵심가방에 넣을 수 있어야 가격이 비싸든 말든 의미가 있다\--> 즉, 가방에 넣을 수 있는 모든 보석을 고른 후 가장 비싼 보석을 선택하면 됨그리디 + 우선순위 큐 사용

로직모든 사람에 대해서 이분매칭 DFS 수행: 내가 선택한 책이 이미 선택되어 있다면    그 책을 선택한 사람에게 다른 책을 선택하도록 권유!핵심: 이분매칭 알고리즘의 이해로직책의 범위를 (st, en) 라고 했을 때en이 작은 순서대로 정렬, en이 같다면 st이

로직'R' / 'B' / 'O' 각각 좌표에 저장4방향에 대해서 DFS 수행Red 이동Blue 이동두개의 좌표가 겹친다면 최초 좌표와 방향을 고려해서 조정! (매우 중요!)Red만 hole에 들어갔는지 검사4방향에 대해서 DFS 다시 수행ans 오름차순 정렬정답 추출느

로직원본 배열인 origin에 값을 저장하고 유지한다DFS()를 통해 배열을 넘길 때에는 반드시 복사본을 생성한 후 넘겨줘야 한다 DFS 로직진행방향이 상 or 좌 인 경우 로직을 앞(idx = 0) 순서부터 실행진행방향이 하 or 우 인 경우 로직을 뒤(idx = N

로직board\[]\[]판에 사과의 위치를 'A'로 표시 / 나머지는 '.'time변수를 늘려가면서 진행하며, DIR변수를 사용해서 방향을 컨트롤(상 우 하 좌 순서로 배치한 뒤 오른쪽 회전 ==>dir증가 / 왼쪽 회전 ==> dir감소)뱀이 DIR 방향으로 이동한

느낀 점음수일 수 있기 때문에 unsigned long long이 아닌, long long 자료형을 써야함음수값을 나눌 수 있기 때문에 값을 뺀 후 양수임을 검증하고 나누기를 진행해야 한다

로직N\*M개의 점들 중 인접한 4개의 점 을 골라서 합을 구하는 방식으로 최대값을 구함(next_permutation을 이용한 조합으로 경우의 수를 구하기)결과: 시간초과next_permutation() --> O(N\*M)next_permutation() 내부 에

핵심DFS의 매개변수로 left를 전달해서 left가 0보다 작을 때 일을 하도록 설계N이 15정도로 작기 때문에 충분히 완전탐색 으로 가능한 것을 캐치해야 함로직DP\[i] = i일 전까지 일했을 때 얻는 최대 금액DP\[i]는 1일 ~ i-1일에 주어진 일을 할 때

로직next_permutation()으로 모든 '0' 좌표중 3개를 선택해서 '1'로 바꾸고 BFS를 실행'0' 카운드하여 최대값 카운트next_permutation() 이 없으면?: 3-depth인 재귀를 통해 3개의 '0'좌표를 '1'로 바꾼 뒤 BFS 수행!

로직현재 방향(북, 동, 남, 서)에 맞춰 dx\[] / dy\[] 설정현재 방향을 기준으로 왼쪽 방향을 임시 방향 tD로 두고 검사할 좌표를 표시 (ny, nx)벽이라면 dir을 감소시켜서 왼쪽으로 전환 / 동시에 후진을 위한 reverseCnt++reverseCnt

핵심: 백트래킹을 이용해 연산자에 따라 모든 경우의 수를 수행

핵심 로직이전 블록의 값인 prev와 다음 블록의 값을 비교해서 큰 경우와 작은 경우로 나누어서 처리(값의 차가 1 이상이면 경사로를 놓을 수 없으니 바로 종료)작은 경우작은쪽에 경사로를 놓아야 하기 때문에 다음 블록을 포함해 앞으로 최소 L개의 같은 값이 있어야 함(

핵심: 회전하기 전 상태에서 톱니의 left, right를 저장해서 갱신해줘야 함(코드에서는 순차적으로 처리하지만, 실제로는 동시에 일어나는 일이기 때문)

로직최대 3-depth 백트래킹을 통해 사다리를 놓는 경우를 찾는다starGame() --> 사다리게임을 하여 하나라도 자신이 아니면 바로 return false 오래걸린 이유해당 문제는 총 300개중 3개를 골라서 사다리를 놓는 경우의 수 (300C3)라서 450만개

드래곤 커브의 세대 증가 로직드래곤 커브의 가장 마지막 점 인덱스를 pre에 저장마지막 점을 제외한 나머지 점에 대해서 방향정보(dir)를 가져온다(방향 정보 : 내 다음 점이 나를 보는 방향)가져온 방향 정보를 90도 회전시킨 후 pre를 통해 새로운 ny, nx를

로직모든 점에 대해서 BFS 수행BFS를 돌면서 인접한 점과 인구수 차이가 L 이상 R이하이면 큐에넣고 계속 수행인구 이동이 없으면 종료

최초 실패 원인: 최초 deque를 쓰지 않고, vector를 사용하면서 양분을 주기 전에 sort()를 했더니 시간초과 발생\--> deque를 쓰면 앞,뒤에서 삭제가 O(1)밖에 안걸리며, 어차피 한번 양분을 못주면 알아서 나머지 뒤는 죽으니까 신경쓰지 않아도 된다

로직shark의 좌표를 시작으로 BFS를 수행해서 가장 가까운 좌표를 찾는다ans를 증가시키고 shark를 update!느낀 것 : 문제의 조건을 정확하게 파악하지 못해서 시간이 오래걸렸기 때문에 정신을 차려야 한다

로직미세먼지 확산tmp\[]\[] 에 변경된 값을 저장하고, spread값은 board\[]\[]로 판단미세먼지 확산 로직 수행공기청정기 가동반시계방향 수행시계방향 수행변경된 board\[]\[]를 tmp\[]\[]에 복사앞 과정 반복 & 마지막에 Count!

핵심: 시간복잡도 줄이기1) 이동해야하는 상어를 queue를 통해서 관리하였고, size를 통해 이번 차례 상어까지만 수행함2) speed에 따라 상어가 움직이는 과정에서 speed가 최대 1,000이라는 숫자를 가져서 시간초과가 날 확률이 크다\--> speed를 방

핵심: map을 활용해서 count한 뒤 pair<등장횟수,숫자> 로 vector에 넣은 뒤 정렬하는 것주의: 시간복잡도 계산을 해보니 최대 O(N^3) = 10^6승 연산 정도라서 충분히 가능!

핵심: next_permutation을 이용해서 전체 virus개수 중 M개를 선택하는 조합을 모두에 대해 전부 바이러스를 퍼뜨리는 경우 중 최소값을 기록시간복잡도 최대 10개의 바이러스 중 5개를 선택하는 수이기 때문에 252가지 경우를 가진다252가지 경우에 대해

로직x / y / d1 / d2 가능한 모든 경우의 수에 대해 주어진 조건을 만족하는 경우를 실행1) sector 5에 해당하는 경계선을 모두 그리기2) sector 1 ~ 4에 해당하는 좌표를 탐색하며 sector별 인구수 count! (경계선을 만나면 다음 row로

핵심 다음 이동하는 칸이 blue인 경우 새로운 방향에 대한 새로운 좌표(nny, nnx)에 대해 다시 한 번 다음 칸을 검사하고 white / red이면 다시 해당 말에 대해 검사하게 i--를 수행해야 한다각 반복문이 시작하고 끝날 때 horse.size() >=4

핵심원판을 회전할 때 dir(방향)과 횟수(cnt)를 받아서 무조건 시계방향으로 변환하면 반시계방향 구현하지 않아도 됨\--> reverseDir에서 주의할 것은 M-cnt로 해야한다! (1 Cycle이 M에따라 바뀌기 때문에)인접한 수가 같은것이 있는지 검사하는 과정

핵심이미 말이 있는 곳에는 말을 둘 수 없다윷놀이의 모든 경로를 5가지로 분리하여 이미 말이 있는 곳에 두지 않게 해야 한다\--> 경로를 분리할 때 만약 겹치는 부분이 존재하면 무조건 오답1) 2 ~ 382) 13 ~ 19 3) 22 ~ 244) 28 ~ 265) 2

문제 풀이 접근상어가 어떤 물고기를 먹는지에 따라 결과가 계속 달라짐\--> DFS를 이용한 완전탐색 필요고려해야할 것순서가 진행될 때 마다 board / shark / fish 변수가 달라진다\--> 매번 매개변수로 새로운 배열을 넘기거나 다시 배열을 복구해주는 방법

핵심동시에 일어나는 일이기 때문에 비어있는 임시배열을 이용하는 것: board\[]\[]와 pheromone\[]\[]으로 비교 t_board\[]\[]와 t_pheromone\[]\[]에 저장상어의 정보를 응집하기 위해 shark 구조체 사용이상한 점: 해당 문제에서

주의board\[]\[]와 cost\[]\[]를 인덱스 1~N까지 사용하는데 초기화를 0부터 함\--> 아래처럼 해야 1부터 N까지 초기화가 된다for(int i=1;i<=N;i++) fill(cost\[i]+1, cost\[i]+N+1, -1);예외처리고객을 태

컨베이어 벨트 위의 로봇 > 코드 >

유의파이어볼이 분할될 때 제자리에서 여러 방향을 가진 파이어볼로 분할되는 것임\--> 여러 방향으로 뻗어나가서 그 자리에 파이어볼이 저장되는 것이 아님(문제 설명이 너무 모호해서 많은 사람들이 헷갈려하는 듯 보임)

핵심토네이도 방향에 따라 board\[]\[]에 접근하는 것토네이도 방향에 따라 각자의 spread와 rate를 지정하는 것깨달은 것토네이도 방향이 4가지이니까 dir\[4]\[10]으로 모두 지정했다면 코드가 더 짧을 것이고 지금처럼 시간이 오래걸리지 않을 것 같다토

핵심각 크기마다 접근해서 90도 회전하는 것이 핵심: 각 좌표에 대해 st_r / st_c를 지정해서 st_r+\_size / st_c+size 까지 수행해서 임시 배열 t_board에 저장

핵심주사위를 굴릴 때 마다 up / back / right / left / front / bottom에 있는 주사위 면을 갱신해줘한다

문제 풀이최초 시도: 모든 연산자 개수 중 우선순위 조합을 만들어서 실행하려 했으나 실행 코드를 짜지 못해 실패(괄호가 겹치는 경우의 우선순위를 찾는것도 확실하지 않았음)결과: 정답 풀이를 참조(핵심) 현재 연산자를 기준으로 2가지 경우를 수행현재 연산자를 기준으로 괄

DP 로직D\[i] = i-1일까지 일 했을 때 얻는 최대 금액최대 Ti가 50이라서 최대 D\[i-50]을 검사하면 될 줄 알았음\--> 실제로 D\[i-53]부터 정답처리가 되었다 --> 이유는 모르겠음(어차피 시간도 넉넉하니 이럴때는 안전하게 -100정도 해도 괜

아쉬운 점문제를 보고 틀을 바로 잡아서 30분 정도면 풀 수 있을 것이라고 생각했는데 BFS에서 시간을 많이 보냄아쉽지만 그래도 문제유형이 조금씩 익숙해져가니까 희망이 보인다오래걸린 이유현재 궁수의 위치에서 가장 가까운 적을 찾는 과정을 BFS로 구현했는데 이상하게 안

핵심: 모든 1에 대해서 모든 종류의 색종이 크기에 대해 가능하다면 백트래킹을 수행해서 최소값을 찾는다느낀 점: 하나의 DFS는 하나의 1에 대해서만 수행하고 종료되어야 한다(그렇지 않으면 색종이를 덮지 않은채로 다음이 진행될 수 있음 + 시간복잡도 상승)

로직예외 처리K가 5보다 작으면 종료 --> 필수 알파벳 5개 ('a' / 'c' / 'n' / 'i' / 't')는 있어야 하기 때문필수 알파벳 5개가 없으면 종료 --> 모든 단어에 들어가기 때문에 없으면 무조건 0필수 알파벳을 제외한 알파벳 수 <= K-5

주의행의 방향이 8과 1이 보통 풀던 방향과 다르다는 것을 인지해야한다느낀 점문제를 꼼꼼하게 읽고 확인하자

로직백트래킹을 이용해서 밤에 마피아가 시민을 죽이는 모든 경우를 수행해당 과정에서 최적의 경우 (마피아가 마지막까지 살아남으면 더 이상의 최적 경우는 X)에 exit(0)느낀 점최초 next_permutation()을 이용해서 모든 경우의 수에 대해 최대 night를

필요 기법백트래킹 + DP를 모두 사용해야 무한 경로 검사 + 중복 경우 제거(시간 단축)이 가능함!핵심Cycle 검사 : map을 활용해서 해당 좌표의 해당 방향으로 이미 온 기록이 있으면 Cycle로 간주 (백트래킹 이용)\--> 무한대로 도는 경우를 검사해서 -1

로직물의 양을 9 --> 1로 줄여가며 각 영역마다 담을 수 있는 최대 물을 저장문제와 다르게 물과 땅의 높이차가 있어야 흐르지 않는 것으로 이해하고 문제를 풀었다(영역의 개수를 cnt로 구한 뒤 마지막에 더해주면 동일한 높이에서 흐르지 않는것과 같은 계산이 가능!)해

풀이 & 한계열쇠('a' ~ 'f')를 만나면 해당 좌표부터 새로운 BFS를 수행 + map을 통해 현재 보유한 key관리(key는 백트래킹으로 나왔을 때에는 다시 false처리를 했음)N과 M이 50이라는 큰 숫자에서 DFS를 했고, 최적 조건시 exit(0)할수도

핵심 : 마지막 좌표에서 처음으로 오는 것도 검사해야 하니까 sv\[0] 더한 뒤 검사해야 함

핵심min_r / max_r / min_c / max_c 를 통해서 범위 관리board판을 넉넉하게 잡은 뒤 50부터 인덱스 시작

원리갈 수 있는 모든 경로를 재귀 DFS라면 백트래킹을 통해서 쉽게 해결했을 것이다하지만 N과 M이 커서 재귀가 힘들다고 생각해서 stack을 이용한 DFS를 수행: 중요한 것은 어차피 낮은 곳으로만 이동하기 때문에 왔던 경로로는 절대 갈 수 없음\--> BFS든 DF

핵심board\[dir]\[r]\[c]를 사용해서 보드판의 입장에서 어떤 방향을 가지고 있는지에 따라 최소 값 갱신cost를 비교할 때 같은 cost를 가지면 반드시 continue로 넘겨줘야 한다\--> 그렇지 않으면 무조건 무한루프에 빠진다출발지점과 도착지점이 같은

문제 접근DFS를 통해 완전탐색으로 경로 찾기 --> N이 100이라서 너무커서 시간초과가 확실방향이 증가밖에 없으니 vis없이 BFS를 수행하면 모든 경로의 수를 찾을 수 있음\--> 수행은 되지만 시간초과 발생\`\`\`해답:DFS + DP\`\`\`를 사용해서 풀

핵심통나무의 중심점을 통해서 BFS를 수행각 board에서 status에 따라 다른 경로를 가질 수 있으니 3차원 배열을 이용\--> board\[status]\[r]\[c]

주의할 점반드시 Knight보다 Queen이 먼저 수행되어야 한다 (더 많이 갈 수 있기 때문)같은 Queen끼리 방문한 점은 Queen이 다시 방문할 수 있어야 한다!\--> 만약 방문하지 못하면 퀸의 실행 순서에 따라 방문하지 못하는 점이 발생!\--> vis\[r

문제 해결본인은 BFS를 통해 원하는 depth(5)까지만 실행해서 map을 통해 개수를 Count!DFS로 원하는 depth까지만 수행 후 체크해도 해결 가능한 문제

핵심비트마스킹을 이용해서 벽이 없다면 갈 수 있도록 설정 --> 1,2번 BFS벽이 있어도 status가 0이면 (벽을 부수지 않았으면) status++하고 진행 --> 3번 BFS영역간 방 개수의 합을 구하기 위해 각 영역별로 숫자를 부여하고 영역별 룸 개수를 기록(

느낀 점DFS로 모든 물병간 옮기는 경우의 수를 수행해서 구해야겠다고 생각최초 3차원 vis를 vis\[water]\[content]\[from]\[to]로 생각해서 오답이 나옴(from에서 to로 water을 줘서 content가 되었다 : 지금생각해보니 매우 복잡하

핵심모든 육지의 좌표에서 연결된 육지간 최장 거리를 구해서 최대길이를 찾아야 한다

핵심 원리3차원 cost를 사용 + queue에 info라는 구조체를 통해 정보 관리 : cost\[찾은K개수]\[R]\[C] / info = { r / c / find / max_height / min_height / m }     \--> m이라는 map을 통해서

핵심자물쇠의 총 구멍 개수(tot_cnt)를 구해서 열쇠로 매운 개수(cnt)와 비교해서 같은 경우에만 true!\--> 현재 key로 일부분은 채워질 수 있지만, 반드시 정답은 모든 자물쇠 구멍을 채워야 하기 때문이동하는 좌표를 구할 때 행,열 간 차이를 나타내는 d

핵심map을 이용해서 parent와 인덱스를 관리해서 문제 해결

핵심 아이디어경로가 일찍 끝나는 것 부터 cctv를 설치하는데 동시에 포함되는 경로는 같은 cctv로 처리할 수 있음\--> 경로가 끝나는 것을 기준으로 오름차순 정렬 + 경로의 시작이 빠른 것 순서대로 정렬 + idx 증가map을 이용해서 이미 처리된 경로는 cont

핵심 아이디어두개의 마을로 나눌 때 어차피 하나의 간선을 끊어야 한다즉, 가장 cost가 큰 간선을 끊으면 최소값을 구할 수 있다

핵심MST(최소 신장 트리)를 찾는 문제니까 Kruskal, Prim을 사용

핵심 아이디어Kruskal 알고리즘 사용전체 cost를 더한 tot에서 MST에 포함하는 cost인 ans를 빼면 된다

메모리 초과 원인모든 planet 간의 간선과 비용을 모두 구해서 edges에 넣었기 때문!핵심 planet간 cost는 min(a.x - b.x, a.y - b.y, a.z - b.z)이다. 즉, x축 / y축 / z축으로 각각 정렬해서 서로 인접한 planet간의

핵심 다익스트라(Dijkstra) 알고리즘 사용 : 한 정점에서 모든 정점까지 최단거리 구하기 (O(NlogN))

사실 BFS풀이와 큰 차이가 없고, 어차피 중간에 끊지 않으니 걸리는 시간도 동일하다BFS와 비교했을 때 priority_queue를 사용한다는 것 정도가 다름