알고리즘 문제풀이

간단한 문제고, 정렬을 이용하면 된다.간단하게 푸려면 a는 오름차순, b는 내림차순으로 정렬해서 풀면 되지만 그렇게 되면 문제의 출제의도에 어긋난다고 생각한다.실제로 인터넷을 찾아보니 답이 나온다는 이유로 b 배열도 정렬해서 푸는 경우가 대부분이었다.우선순위 큐 (pr

백준 2309번 : 일곱 난쟁이 먼저 9명중 7명을 뽑는다. (combination 이용) 뽑힌 7명의 키 합이 100인지 확인한다. 맞다면 7명의 키를 오름차순으로 출력한다. 정답 코드 (combination 이용)

시작이 W인 경우의 체스판, 시작이 B인 경우의 체스판을 각각 미리 입력해놓기입력받은 배열을 8X8로 잘라서 1번에서 만들어놓은 두 체스판들과 비교색이 다를때마다 count를 해서 가장 작은 경우 출력정답 코드

0으로 초기화된 배열을 생성 (알파벳 개수 크기만큼)문자열 입력받고한 문자씩 보면서1번의 배열에서 ('문자'-'a')번째 인덱스에 1 더하기정답 코드

백준 10818 : 최소, 최대1번 풀이 : sort한뒤 맨 처음과 맨 마지막 배열 출력정답 코드2번 풀이 : max_element, min_element 이용정답 코드시간은 1번 방법이 약 180ms, 2번 방법이 약 120ms가 소요되었다.

구간 합 이용 (ai = ai-1 + temp)max 함수를 이용해 최대값을 갱신정답 코드

map 이용해 포켓몬 이름 -> 숫자 변환N번째 포켓몬 이름은 따로 포켓몬 이름이 들어있는 배열을 이용해 변환정답 코드atoi 함수는 문자열을 받았을 경우 0을 리턴한다.atoi나 find를 사용할 때에는 (string).c_str() 을 이용해서 문자열을 넘겨준다.

옷의 종류만 사용한다. 옷의 이름은 필요 X해당 옷 종류를 안 입는 경우까지 더해 (종류별 옷 수+1) 개를 조합하는 모든 경우의 수를 계산정답 코드

처음에 단순히 C++에서 제공되는 find 함수를 이용해 손쉽게 풀려고 접근했다.코드 그랬더니 시간초과가 났다..검색해보니 find() 함수가 O(N) 시간이 소요되는 거였다. find 함수를 쓰면 Sequential search를 이용한다고 한다.따라서 이분탐색을 이

왜 틀렸을까?

시간 제한이 2초길래 그냥 이중 for문 써서 모두 검사해서 풀었다.확인할 점조합 이용해서 하면 더 빨라질까?정렬 이용해서 더 빨리 풀 수 있을까?

stack 사용정답 코드

가중치가 같은 탐색이므로 bfs를 사용정답 코드cin, cout과 printf, scanf를 혼용해서 쓰면 안되는 이유

전형적인 dfs 문제왜 틀렸을까?

배열의 최대값을 구하고1에서 구한 최대값만큼 dfs를 돌면서 각각의 안전지대 개수를 구함2의 결과 중 최댓값을 출력정답 코드visited 배열과 cnt 값을 루프마다 초기화 해줘야 하는 것을 잊지 말자

조합으로 풀면 됨!먼저 7명 뽑고합이 100이 되면 통과, 아니면 다시정답 코드

n번째 손님에서 n을 층 수인 h로 나눈 몫이 호수, 나머지가 층수나머지를 먼저 구하고 100을 곱해서 층 수를 만든다.몫을 구해서 호수를 더해준다. (호수가 1부터 시작하므로 +1 해줘야 함)4\. 나눠 떨어지는 경우는 따로 계산해 줘야 한다.1) 층 수는 h와 같음

줄 전체 입력받기공백이면 건너뜀 (세는중) 변수를 false로 업데이트(세는중) 변수가 false이고 공백이 아니면 count를 증가시키고, (세는중) 변수를 true로정답 코드c++에서 단어들 split 하는 방법도 알아놔야 겠다

숫자가 바뀌는 지점에 주목!바뀌는 지점을 2로 나눠주면 정답나눠 떨어지지 않으면 그냥 2번 결과에 1 더해주면 됨정답 코드

직전 문자와 달라지면직전 문자 위치 배열을 1로 업데이트만약에 for문 돌다가 1을 만나면 break브레이크 안걸리면 count 증가정답 코드

우선 전체 길이에서 감소하는 방식으로체크 지점은 -, =, j체크해서 크로아티아 알파벳이면 크로아티아 알파벳만큼 전체 길이 값에서 감소시킴정답 코드

1~k 사이의 숫자에서 조합으로 3개 뽑고3 숫자의 삼각수를 더해서k와 같으면 1, 아니면 0 출력이렇게 했더니 시간 초과가 뜸. 왜 틀렸을까?코드

"666"이 들어갈 자리를 고르는 경우나머지에는 0~9가 들어갈 수 있음 (첫번째 자리에는 0이 못옴)정답 코드

set이 자동으로 정렬되고, find가 O(1)에 수행되는 점을 이용해 set으로 풀이 하였다.이랬더니 시간 초과가 났다.set의 시간복잡도는 O(logN), 따라서 더 작은 시간 복잡도인 O(1)을 가지는 undered_set을 이용했더니 맞았다.정답 코드map :

스택을 이용( 면 스택에 push, ) 면 스택에서 poppop할게 없거나, 마지막에 스택에 뭔가 남아있으면 결과값이 NO마지막에 스택이 비어있으면 YES정답 코드

큐의 first-in, first-out 성질을 이용해서정답 코드

한장도 없는 상태에서 과정을 거꾸로 수행한다.앞뒤로 넣고 빼야 하므로 덱(deque) 사용정답 코드

우선순위 큐를 이용정답 코드

구현이 빡센 문제정답 코드

구현해야 할 기능1\. 입력받기2\. 정답 코드

백준 3190 : 뱀 입력받기 뱀이 이동할 거리와 방향을 큐에다 저장 큐 값들을 하나씩 빼내면서 뱀의 이동을 구현 뱀의 길이가 늘어나는 부분을 어떻게 해야 할까? sol) 뱀의 위치를 덱을 이용해 처리한다. 뱀 몸통 각각의 위치를 덱을 이용해 저장한다. 사과를 먹

백준 15686 : 치킨 배달 폐업한 치킨집을 1, 2, ..., M개 고르는 경우 모두 고려해 보고 그 중 도시의 치킨 거리가 최소가 되는 경우를 구한다. cf) MC1 + MC2 + ... + MCM = 2^M (이항계수) 구현할 함수 입력받기 집과 치킨집 위

그래프를 이용해 풀이하면 된다.연결 관계를 인접행렬로 만들고, 만약에 DFS로 풀이한다면 아래와 같은 경우에1번이 상근이라고 가정하면, 2번 3번을 방문한다.그 후 3번을 통해 4번을 가야 하는데 3번은 바로 위에서 이미 방문했으므로 건너뛰게 된다 -> 4번이 탐색이

조합으로 풀면 된다s개 중 k개를 선택해서 출력정답 코드\* 로컬에서 할 때는 빠른 입출력 (sync with stdio)를 제거해야 정상적으로 출력된다! 제출할때는 상관없음

백준 1351 : 무한 수열DP라고 문제에 써있다.단지 숫자가 커서 캐시를 배열로 쓰긴 힘들다따라서 map을 이용해서 memoization을 해야 한다.정답 코드

백준 2607 : 비슷한 단어 기준 문자열의 알파벳을 앞에서부터 차례대로 입력받은 문자열에서 찾아서 하나씩 지워간다. 입력받은 문자열에 남은 알파벳이 1개면 비슷한 단어! 정답 코드

백준 1654 : 랜선 자르기

백준 2606 : 바이러스 dfs를 이용하면 간단하게 풀리는 문제이다. 정답 코드

N이 최대 8이니까 숫자 배열하는 모든 경우를 다 생각해도 8!이다.그냥 다 배열해보고 그 때의 결과값을 계산해서 최소값을 구하면 될듯정답 코드

백준 4811 : 알약 dp문제이다. 온전한 알약을 a개, 반쪽짜리 알약을 b개 가지고 있다고 하자. top-down 방식 bottom-up 방식 재귀를 이용해 생각해봤다. 만약에 온전한 알약을 먹었다면 다음날은 온전한 알약은 a-1개, 반쪽짜리 알약은 b+1개

듣도못한 사람들을 set에 저장m동안 입력받으면서2-1. set에서 찾으면 입력받은걸 정답 set에 저장출력은 정답 set의 크기와 set의 내용물들정답 코드

입력을 하나씩 받음, map<string, int>기존 map에서 찾으면 int 증가, 못찾으면 map에 insert다 했으면 마지막에 map의 int값들 중 최대값의 string값 출력정답 코드

deque 이용, deque<pair<index, value>> dq;터뜨리고숫자를 확인3-1. 숫자가 양수라면, (숫자-1) 만큼 앞에서 pop, 뒤에서 push3-2. 숫자가 음수라면, (숫자의 절대값) 만큼 뒤에서 pop, 앞에서 push맨 앞의 수가

전형적인 dfs 문제코드왜 틀렸지????\-> visited배열과 bat 배열 둘 다 초기화를 해줘야 한다!!!!!!!!정답 코드

커스텀 정렬 연습하는 문제입력 값들을 {문자, 문자의 길이}로 map에 저장커스텀 정렬하는 방법3-1. map의 값들을 벡터에 저장3-2. 커스텀 정렬 조건 구현 \- 문자열 길이가 작은 순으로 \- 문자열 길이가 같다면 사전 순으로정답 코드

백준 1107 : 리모컨 100에서 시작해 +,- 로 해당 채널까지 가는 경우 채널 숫자를 입력하고 그 후 +,- 로 해당 채널까지 가는 경우 정답 코드

bfs문제현재 위치가 N일때, 자식 노드는 N-1, N+1, 2\*N임을 이용해서 BFS를 돈다.큐에 push 하는 조건을 잘 생각해 봐야 함정답 코드

dfs의 진행 과정을 어느정도 파악하고 있어야 하는 문제였다.dfs를 진행하며, 방문할때마다 영역의 넓이를 1씩 더하며 진행하면 된다.정답 코드

문자열 길이가 30밖에 안되니 브루트 포스로 다 검사해보는게 나을듯정답 코드

방 개수만큼 감독 인원 초기화 (총감독은 한명씩)루프 돌면서 남은인원/부감독감시인원 을 올림한 값을 더함사이즈가 100만이라 중간에 int 범위를 넘어갈 수 있어서 long long형으로 선언해주는게 핵심!정답 코드