알고리즘 + 자료구조

입출력 - 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2

https://www.acmicpc.net/problem/1008소수점 자리 표현하기using namespace std;int main(){}

https://www.acmicpc.net/problem/1095110950번과 비슷해 보이나, 이 문제의 핵심은 몇 개를 입력 받는지 알 수 없다 는 것이다.고로 EOF 를 사용하여 입력의 끝까지 반복해서 a와 b를 입력받고 합을 출력한다.EOF(End Of

https://www.acmicpc.net/problem/10953콤마(,)로 나누는 게 핵심이다. 파이썬처럼 생각하여 내장 함수 split 을 쓰고 싶었으나 다른 방법도 많았다.어떤 형식에 따라 입출력을 받을 때는 인클루딩 후 scanf와 printf를 활

https://www.acmicpc.net/problem/11718getline을 이용하면 쉽게 풀 수 있다.scanf printf 를 이용하여 풀려 했는데 더 쉬운 방법이 있었따 . .다각으로 접근하자 !kih0902님 블로그

https://www.acmicpc.net/problem/11720N 크기의 문자열 생성 & char을 int로 바꿔서 연산하기가 핵심이다.sum에 입력된 각 자리 값을 더할 수 있습니다.숫자가 아스키코드이므로 C++ 에서 char을 int로 변환하는 방법은\

https://www.acmicpc.net/problem/11721전체 문자열 길이만큼 돌면서 10개씩 끊어서 출력 후 줄바꿈한다.scanf 이용하려다 .. 머리가 혼란해져서 종이로 쓰면서 하다가 .. . 결국 찾아봄이렇게 쉬웠는데 . . 어렵게 생각하지

https://www.acmicpc.net/problem/1924총 날짜의 차이를 구하여 7로 나눈 나머지로 요일을 구한다.string인데 printf로 하려다가 안되어서 애를 먹었는데 cout 쓰라네 ..자꾸 printf 를 쓰려는 강박 .. 버려줘 ~그리고

https://www.acmicpc.net/problem/10818배열과 algorithm의 sort를 이용한다.cin >> arrayi 이런식으로 바로 저장이 가능하다. 왜 몰랐니 멍충ㅇsort는 algorithm을 인클루딩 한 후 a가 배열의 포인터라 하면

https://www.acmicpc.net/problem/2438반복문을 활용한다. string은 += 와 .append() 를 이용하여 문자열을 추가할 수 있다.방법 2가 시간적으로도 훨씬 빠르고 기본적인(?) 느낌이다. 다른 분들의 방법이 궁금해서 찾아봤는

https://www.acmicpc.net/problem/10991반복문을 이용, n-i개의 공백과'\* '을 차례로 출력한다.첨엔 막 .. 홀수 짝수별로 나눠보고 .. 가운데 기점으로 +-i 이렇게 해야하나 등등 머리가 터질 것 같아서 찾아봤는데 알고 보면

큰 문제를 작은 문제로 나누어 푸는 문제(Dynamic(동적)이라는 이름의 의미는 딱히 없다고 함)메모리를 적절히 사용하여 수행 시간 효율적을 비약적으로 향상 시킨다.Divide and Conquer(분할 정복)과의 차이?작은 문제의 반복이 일어나지 않는가 -> 분할

https://www.acmicpc.net/problem/1463DP의 bottom-up 방식을 사용한다. N+1 크기의 배열을 만들고 dp\[1] = 0으로 초기화 해준다.N까지 dp 배열을 채워나간다.X가 3으로 나누어 떨어지면 3으로 나눈다.X가 2로 나

https://www.acmicpc.net/problem/11726DP로 bottom-up 방식을 활용한다.N번째 블록의 개수 = N-1개 블록에서 | 모양을 더한 것 + N-2개 블록에서 = 모양을 더한 것"고로 dpN = dpN-1 + dpN-2 이다.반복

https://www.acmicpc.net/problem/10818DP외 2차원 배열을 활용한다.우리가 알아야 할 정보는 숫자 길이(N)과 끝자리 숫자 이다.이를 2차원 배열에 저장해놓는다.끝자리 숫자가 1이라면?? 길이를 1만큼 늘렸을 때 생성될 수 있는 계

https://www.acmicpc.net/problem/10818DP를 이용한다.끝자리가 0이면 이전에 올 수 있는 숫자는 0, 1 모두 가능하다.끝자리가 1이면 이전에 올 수 있는 숫자는 0만 가능하다.이를 통해 식을 세우면 다음과 같다. dp\[N]\[0

https://www.acmicpc.net/problem/9465!\[](https://images.velog.io/images/youhyeoneee/post/2e8b4a57-da55-45ef-b934-93e84299edb1/9465(20.PNG)DP

https://www.acmicpc.net/problem/2156DP를 이용한다.포도주의 양을 저장하는 배열 a, N번째 잔에서의 최댓값을 저장하는 배열 dp가 있다. a\[n]: n번째 포도주의 양dp\[n]: n번째 까지 마신 포도주의 최대 양먼저 초기식을

https://www.acmicpc.net/problem/11053DP를 이용한다.수열 Ai와 가장 긴 증가하는 부분 수열의 길이를 저장한는 배열 dp가 있다. N번째 길이에서 찾을 수 있는 가장 긴 부분 수열은자기 자신보다 작은 수들 각각의 부분 수열 중 제

https://www.acmicpc.net/problem/11054DP를 이용한다.왼쪽에서 부터 가장 긴 증가하는 수열을 구한다. -> 배열 a에 저장오른쪽에서부터 가장 긴 증가하는 수열을 구한다. -> 배열 b에 저장왼쪽 + 오른쪽 합친 것 중 가장 큰 수

https://www.acmicpc.net/problem/1912DP 를 이용한다.수열이 담긴 배열 a 와 최대합을 저장하는 배열 dp 가 있다.N번째 수를 선택한다는 가정 하에연속일 때 -> dpN-1 + ai연속이 아닐 때 -> ai 이 둘을 비교하여 더

https://www.acmicpc.net/problem/2579DP를 이용한다.계단 점수를 저장하는 배열 stair과 얻을 수 있는 총 점수의 최댓값을 저장하는 배열 dp가 존재한다.먼저 문제를 읽어보면, 아래와 같은 조건이 있다.계단은 한 번에 한 계단씩

https://www.acmicpc.net/problem/2133DP를 이용한다.3xN의 크기의 벽을 2x1, 1x2로 채우기 위해서는 N이 짝수이어야 한다.때문에 N이 홀수일 경우 dpN = 0 이다.N이 2씩 늘어날 때마다 생각을 해보겠다.N=2 일 경우

https://www.acmicpc.net/problem/2011DP를 이용한다.나올 수 있는 해석의 가짓수를 1000000으로 나눈 나머지 배열 dp가 있다.N자리 수 일때 왼쪽부터 한 숫자(i=1~N)씩 본다.0\. 제일 중요한 예외 ! 코드 맨 앞자리가

n개의 숫자가 입력으로 주어졌을 때, 이를 기준에 맞게 정렬하여 출력하는 알고리즘정렬 알고리즘에는 다양한 종류가 있고, 이에 따라 수행 시간도 다양하다.순차적으로 기준에 따라 현재 위치에 들어갈 값을 찾아 정렬오름차순이면 Min-Selection Sort(최소 선택 정

https://www.acmicpc.net/problem/10818STL sort 쓰려고 했는데 메모리 초과가 나왔다..이렇게 풀면 안되는 문제..그리고 수의 개수 N은 최대 10,000,000개라서 입력값을 전부 저장하면 당연히 메모리 초과가 난다.이 수는

개념 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 형식의 자료 구조 > 가장 최근에 스택에 추가한 항목(top)이 가장 먼저 제거될 항목이다. 이는 알고리즘 구현시 임시 목록에 객체를 추가한 다음 나중에 목록에서 객체를 꺼내려고 할 때 필요하다. 연산 : item 을 top에 추가한다. : top을 제거한다. : top을 반환한다. : 스택이 비어 있...

https://www.acmicpc.net/problem/10799 문제 알고리즘 접근 방법 > : 잘려진 쇠막대기 조각의 총 개수 : 현재 있는 쇠막대기의 개수 : 입력받은 문자열 왼쪽부터 한 글자씩 for문을 이용하여 체크한다. > ### 쇠막대 쇠막대가

개념 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 형식의 자료 구조 >LIFO(Last In First Out) 가장 최근에 스택에 추가한 항목(top)이 가장 먼저 제거될 항목이다. 이는 알고리즘 구현시 임시 목록에 객체를

양방향 큐(Double-Ended Queue)의 줄임말 큐의 전단(Front)과 후단(Rear) 모두에서 데이터의 입출력이 발생하는 자료구조이다. 스택과 큐의 특성을 모두 갖는, 둘을 조합한 형태의 자료구조로 이해되고 있다.매우 유연한 자료구조로써 양 끝단에서 발생하는

위 표와 같이 ASCII 코드값에는 십진수(Dec.)기준으로 숫자(0~9) : 48번~57번에 할당알파벳 대문자(A~Z) : 65번~90번소문자(a~z) : 97번에서 122번에 할당되어 있다. ASCII 코드 테이블 상에서 알파벳 대문자는 65~90번, 소문자는 97

https://www.acmicpc.net/problem/10820각각 비교를 통해 문자를 구분한다. N이 입력되지 않음으로, eof를 이용하여 종료조건을 잘 받아야 한다.이런 식으로 처음에 했는데 안되었다. 이유는 마지막 줄을 읽고나면 마지막 줄 뒤에 달려있

'일정한 순서'의 나열 로,어떤 정의에 의해서 결정된 '논리적인 순서'의 나열이다. 리스트의 순서는 데이터가 저장되는 물리적 위치와 상관없이 사람들의 머릿속에 인식되는 논리적인 순서, 혹은리스트에 나타나는 원소들간의 의미적인 순서를 의미한다.인덱스로 표현되는 '순서'가

나무 가지처럼 연결된 노드로 이루어진 자료 구조비선형으로, 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있다.노드(node) : A, B, C, D, E, F, G, H, I , J 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포

주어진 쿼리에 대해 빠르게 응답하기 위해만들어진 자료구조이다.1 2 3 4 5 6 이라는 배열 arr 이 있다.arr\[2] + arr\[3] + arr\[4] 를 구하라는 쿼리가 주어진다.쿼리 란?주어진 요구사항에 대해 맞는 결과물을 제시하라는 뜻지금 당장은 3+4+

https://www.acmicpc.net/problem/1406\[2004 Olympiad Croatian Highschool Competitions in Informatics National Competition 왜 .. 오답인지 모르겠지만 아마 시간 문제

https://www.acmicpc.net/problem/1158원형 링크드리스트로 풀다가 오류나서 머리 터질뻔했다..큐를 이용하면 쉽게 풀 수 있다..!K번째 사람이 올 때 까지push & pop 을 반복하면서 동그라미 형태로 뒤로 계속 보내고차례가 되어 제

https://www.acmicpc.net/problem/2609최대공약수 GCD(Greatest Common Divisor)최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.ex) 72 와 30의 최대공약수는 6이다.최소공배수 LCM(Least

https://www.acmicpc.net/problem/18503과 4의 최대공약수가 1이면 답은 1,3과 6의 최대공약수가 3이면 답은 111이다.그래서 먼저 입력받은 두수의 최대공약수를 구하고그 수만큼 1을 출력한다.입력되는 값이 2^63이므로 long

https://www.acmicpc.net/problem/1100510진수를 2진수로 변환하는 방법을 예로 들겠습니다.변환하려는 값을 2로 나누어 몫과 나머지로 위와 같이 구하는 작업을 반복해서 몫이 0이 됐을 때 나머지를 역순으로 표시하면 끝입니다.(만약,

https://www.acmicpc.net/problem/2089음수 진수는 구하는 과정에서 부호와 함께 고려해야하는 것이 있다.: 10진수 → -2진수 로 바꾸는 과정에서3가지 경우 중 1가지를 선택하며 0이 될 때 까지 반복한다.2로 나눠지는 경우2-1.

https://www.acmicpc.net/problem/19291의 경우를 조심하자 대표적인 소수 판별 알고리즘이다.대량의 소수를 한꺼번에 판별하고자 할 때 사용한다.소수를 판별할 범위만큼 배열을 할당해 그 인덱스에 해당하는 값을 넣어준다.2부터 시작해서 자

https://www.acmicpc.net/problem/1676N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제이다.뒤에서부터 0의 개수를 센 뒤 +1 해서 출력그러나 N의 최대값이 500이기 때문에 N!을 직접 구하는 건 무리

https://www.acmicpc.net/problem/11576 문제 알고리즘 접근 방법 > ### 소수 판별 > 1. 에라토스테네스의 체 를 이용하여 소수 판별 한 번만 해놓고 계속 쓴다!!! > 2. 이 때 까지 돌려도 됨 > ### 테스트 케이스 n을 입

https://www.acmicpc.net/problem/15649조합의 개수를 구하는 문제이므로, dfs를 활용하여 풀이가 가능하다.각 숫자는 순열에서 딱 한번만 사용되므로, 각 숫자를 인덱스로 가지는 bool형 배열인 visited를 선언하고,해당 숫자를

https://www.acmicpc.net/problem/15650dfs를 활용한 조합문제이다.조합문제를 풀기 위해서는 간단하다. 재귀 호출에서, 현재 뽑은 원소의 이전값들은 고려하지 않게끔, for문의 i값을 함께 넘겨주면 된다.예를 들어, 1 2 3 4 5

https://programmers.co.kr/learn/courses/30/lessons/12982정렬을 이용한다. 단순하게 부서별로 필요로 하는 금액을 정렬한 뒤 가장 적은 부서 순으로 빼가며 문제를 해결 이 때 주어진 예산이 음수가 되면 더하지 않음에

https://programmers.co.kr/learn/courses/30/lessons/77885짝수일 때, 홀수일 때로 나누어서 접근2 == 00104 == 01006 == 01108 == 1000항상 최하위 비트가 0임을 알 수 있다.따라서 1만 더해주

https://programmers.co.kr/learn/courses/30/lessons/1835friends = "ACFJMNRT" 를 정렬하는 모든 경우의 수를 구하기해당하는 경우에 data조건을 만족하는지 확인한다. 만족하면 answer+1를 해주는

https://codeup.kr/problem.php?id=1018괜히 어렵게 생각했뇌 .. split하구 난리칠뻔문제 1018 >> c++로 어떻게 푸나요

https://codeup.kr/problem.php?id=1022getline을 이용한다.아맞다 getline!\[C++] 공백(띄어쓰기)포함 문자열 입력받기

https://codeup.kr/problem.php?id=1085h,b,c,s를 곱한 후 bit 단위를 MB 단위로 바꿔준다.int -> long long int float -> double 로 바꿨더니 맞았다..ET님 블로그

비선형(non-linear) 자료구조이며 노드(node)와 엣지(edge)로 구성노드는 꼭짓점(vertex)으로 표현됩니다엣지는 두 노드를 연결하는 선(line)으로 표현됩니다.위 그래프를 으로 표현할 수 있다.그래프의 표현그래프를 인접 행렬(Adjacency Matr

트리, 그래프, 탐색 알고리즘에 자주 쓰인다. 이둘을 바이너리 트리에서 구분해보고, 로직을 그래프까지 확장시켜보자Breadth First Search로 너비를 우선적으로 탐색한다.root가 11인 트리는 연결된 자식 노드인 6과 16을 먼저 탐색한다. (11->6-16

개념 현재 상황에서 지금 당장 좋은 것만 고고르는 방법 >탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 일반

https://www.acmicpc.net/problem/2839거꾸로세기N에서 3부터 빼면서 5로 나누어 떨어지면 정답using namespace std;int main(){ int N, cnt = -1;}

https://www.acmicpc.net/problem/14659이중반복문을 이용한다.첫번째 for문에서는 비교하려는 배열의 값을 저장하고 이를 기준으로 잡는다. (now_hanzo)또한 cnt를 0으로 초기화한다.두번째 for문에서는 기준값보다 작으면 cn

https://www.acmicpc.net/problem/2810커플석이 하나 있을 때마다 컵홀더를 못 쓰는 사람이 한 명씩 늘어나다.컵홀더의 개수는 = N+1 개이므로 이로 초기화하고,커플석이 하나 있을 때 마다 -1 해준다.(단, 커플석이 하나도 없는 경우

https://www.acmicpc.net/problem/2865한 장르에 여러 사람은 가능하므로 사람별로 제일 높은 점수를 뽑은 후 이를 내림차순으로 정렬하여 K개만 뽑아 더한다.compare함수 자료형 실수 때문에 두번 틀렸다ap3334님 블로그

https://www.acmicpc.net/problem/2012오름차순으로 정렬 후, 각각 인덱스에 대한 절댓값을 뺀다예가 더 있었으면 .. 좋겠다 자꾸 꼬아서 생각함 ㅠㅠ퉁이리님 블로그

https://www.acmicpc.net/problem/1455axb 만큼 뒤집으면 왼쪽, 위에만 영향을 끼치므로 오른쪽 밑부터 역순으로 오면서 뒤집는다굿원당컴님 블로그

https://www.acmicpc.net/problem/11501잘못된 접근: 주가가 떨어지는 시점에 기존 구입했던 주식 판매 (Greedy)올바른 접근: 주가가 떨어지는 시점이 아니라, 현재 주가를 현재일 이후에 가장 비싸게 팔 수 있는 날에 판매뒤에서부터

https://www.acmicpc.net/problem/2577string으로 바꿔서 string을 돌면서 해당 인덱스에 +1 해준다.나의 풀이더 간단한 풀이아스키코드 조심조심st-lab님 블로그

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정대표적 그래프 탐색 알고리즘 = DFS/BFS먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)입구가 출구가 동일한 형태실행 결과1 3 2 5먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조입구와 출ㄹ구가

https://www.acmicpc.net/problem/2003단순 반복문 = O(N^2) 방식 i=1~N 까지 돌면서 반복문으로 i+1 ~ N까지 더해보면서 M이 되면 break2-pointer = O(N) 방식 start, end를 각각 정해서start

https://www.acmicpc.net/problem/2805절단기에 설정한 높이가 정해지면 나무의 양을 계산하는 데에 소비되는 시간 복잡도 = O(N)절단기에 설정할 높이를 탐색하는 시간복잡도1 ~ 십억을 탐색절단기에 설정할 높이가 낮으면 낮을수록 잘려질

https://www.acmicpc.net/problem/2749피사노 주기(Pisano Period)행렬 이용피사노 주기(Pisano Period)int fibop = {0,1};int main() { long long n; cin >> n;

https://www.acmicpc.net/problem/7453정수로 이루어진 크기가 같은 배열 A, B, C< DAa+Bb+Cc+Dd의 합이 0인 (a, b, c, d) 쌍의 개수각 배열의 최대 크기 = 4000Brute force 로 풀면(막 풀면)

https://www.acmicpc.net/problem/1927최소힙을 구현한다.잘 이해해보자 ...

완전 탐색입력될 때마다 입력된 수를 탐색해서 중간값 구하기시간복잡도 : 1+2+...+N = N(N-1)/2 = O(N^2)\-> N이 100,000일 경우 시간초과중간값 : 중간값을 기준으로 중간값보다 작은 수의 집합 A, 큰 수의 집합B⭐️ 유지해야 하는 상태 :

정답은 -2^63 보다 크거나 같고, 2^63-1 보다 작거나 같은 정수이다. = long long 확정 가능인덱스 트리는 루트에 들어갈 자료형에 주의하면서 구현해야 한다.tree 의 배열 크기 정하기 = tmpNtree 값 내 초기화 2-1. 입력 leafnode2-

실력을 위치 정보로 하여 배열에 저장을 하면 입력되었을 때 입력된 실력보다 앞에 표시된 정보들의 합으로 답을 구할 수 있음. ex. 2 8 10 7 1 9 4 15 > 이렇게 정보를 바꾸면 실력이 입력될 때 값이 바뀌고, 등수를 계산할 때 인덱스보다 앞에 있는 구간의

https://www.acmicpc.net/problem/3955확장된 유클리드 호제법을 이용한다.예외처리K=1C=1C=1, K = 1000000000우와..(푸니까) 재밌다\[캔디 분배] 어떤 부분이 틀렸는지 모르겠습니다...

https://www.acmicpc.net/problem/132511번색에서 K개 뽑기 + 2번색에서 K개 뽑기 + .. + M번색에서 K개 뽑기를N개에서 K개 뽑기 로 나누면 된다.M = 3 이고5 6 7K = 2 라고 예를 들면(5C2 + 6C2 + 7C2

https://www.acmicpc.net/problem/15663백트래킹을 이용한다.can_use 로 각 숫자의 개수를 체크한다.백트래킹 연습을 많이 해봐야겟당.

https://www.acmicpc.net/problem/55570~20 까지의 2차원 배열을 만들어서결과값을 해당 인덱스에 더하며이전 깊이에 배열에서 더하고 빼나가며 반복한다.아놔\~~ 왤캐 안풀려

https://www.acmicpc.net/problem/1256(1) 첫 문자열이 'a' 혹은 'z'인 문자열의 수길기아 N+M이고 'a'의 개수가 N개, 'z'의 개수가 M개인 문자열은 첫 문자가 'a'인 경우와 'z'인 경우밖에 없다.첫 문자가 'a'인

https://www.acmicpc.net/problem/2252위상정렬을 이용한다.다시 풀어보자!!

https://www.acmicpc.net/problem/11266주어진 그래프에 대해서 방문하지 않은 정점을 시작으로dfs 탐색을 수행하여 order를 저장한다.dfs함수는 하나의 정점에 연결된 다른 정점들을 탐색하면서 low를 리턴한다.자신과 연결된 정점에

1949\. \[모의 SW 역량테스트] 등산로 조성dfs를 이용한다.1\. 가장 높은 봉우리에서 시작2\. 4방향으로 탐색하면서 갈 수 있으면 재귀 탐색갈 수 없는 높이이면 공사했다 가정하고 재귀 탐색최대한 긴 등산로를 만들기 위해 공사할 때 (이전 높이 - 1) 로

2105\. \[모의 SW 역량테스트] 디저트 카페완전 탐색1\. 사각형의 두 변을 a, b라고 했을 때2\. 각 꼭짓점은 (i, j) (i+a, j+a) (i+a+b, j+a-b) (i+b, j-b)이다.3\. a,b 를 1부터 N-1까지 반복문을 돌리면서4\. 사각

5644\. \[모의 SW 역량테스트] 무선 충전완전 탐색1\. A, B를 이동시킨다.2\. 각 범위 내에 있는 BC를 본다.3\. 모든 조합을 보면서 최댓값을 도출한다.

SWEA 1952 \[모의 SW 역량테스트] 수영장 C++님 블로그

DFSwithSG님 블로그

\[모의 SW 역량테스트 해설] 미생물 격리

\[C++] SWEA 2383 - 점심 식사시간

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUqBFS를 이용한다.현재 위치가 갈 수 있는 방향에 있는 터널이 현재 터널과 이어지는지 체크함에

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVHDFS + 백트래킹을 통해 모든 경우를 탐색하는 완전탐색 \+ - \* / 의 경우를 모두 대

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWuDFS 를 이용한다.먼저 한 일꾼의 벌꿀 채취 범위를 정한다가로 상의 m개의 벌통을 선택했다면

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo중복순열을 이용하여, 구슬을 N번 쏠 위치를 미리 구한다.후 벽돌을 제거하고알맞게 이동시켜주면

재귀함수 정의 단계에서 자신을 재참조하는 함수 전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수 큰 문제를 작은 부분 문제로 나눠서 풀 때 사용 주의사항 반드시 기저사례를 써야함 (종료조건) 사이클이 있으면 쓰면 안됨 ex. f(a)가 f(b) 호출한 뒤

순서와 상관 O 뽑는다면 -> 순열순서와 상관 X 뽑는다면 -> 조합문제에서 아래와 같은 경우 순열 오름차순 기반으로 순열 만들기정렬이 되지 않은 경우 모든 순열을 다 반환하지 않음 -> sort 필수ex. {2, 1, 3}2,1,32,3,13,1,23,2,14가지 경

순서와 상관 X 뽑는nCr = n! / r!(n-r)!TIP3개 뽑는거 까진 중첩 for문4개 이상부터 재귀 good2개 뽑는 경우는 2중첩만 하면 됨.

C++에서는 split()을 지원하지 않음시간복잡도 : O(n)input에서 delimiter을 찾는다. 못 찾을 때까지 반복됩니다.찾았다면 해당 pos까지 해당 부분 문자열을 추출합니다. ex. abcd 에서 d를 찾았다면 ? pos는 3을 반환하고 abc를 추출함.

고유한 주소를 가진 1바이트짜리로 이루어져있음변수를 선언을 했따?메모리에 사용할 공간을 예약을 한다주소 : 사용하는 메모리 셀의 첫번째 주소값을 할당해당 메모리에 값이 쌓임

메모리의 주소를 담는 타입메모리 동적 할당, 데이터를 복사하지 않고 함수 매개 변수로 사용, 클래스 및 구조체를 연결할 때 사용\* = 에스터리스크(asterisk operator)OS가 32bit라면 4바이트, 64bit라면 8바이트로 고정어떠한 타입이든(string

이항 연산자로 사용하면 곱셈 연산으로, 포인터 타입의 선언, 역참조(dereference)로 메모리를 기반으로 변수의 값에 접근할 때도 사용

배열이 포인터로 부식됨 decay = 부식배열의 이름을 T\* 라는 포인터에 할당하면서 T\[N]이란 배열의 크기 정보 N이 없어지고 첫번째 요소의 주소가 바인딩되는 현상vector는 안되고 array만 가능

범위 안에 있는 요소 중 앞에서부터 서로를 비교해가며 중복되는 요소를 제거하고 나머지 요소들은 삭제하지 않고 그대로 두는 함수시간복잡도 : O(n)앞의 경우처럼 앞에서부터 서로를 비교해가며 중복된 요소를 제거하기 때문에sort(), erase(unique())를 함께

입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요 로직의 반복 횟수를 중점으로 측정됨주어진 입력크기를 기반으로 어떠한 로직이 몇번 반복되었는가 복잡도에 가장 많이 영향을 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법n! >

입력 크기에 대해 어떤 알고리즘이 실행되는데 필요한 메모리 공간의 양정적변수 뿐만 아니라 동적으로 재귀함수로 인해 공간을 계속 필요로 할 때도 포함이고 배열이든 맵이든 셋이든 공간이면 다 !!ex. 입력이 N, 자료형이 int \-> 4N => O(N)문제를 푸는데는

누적합 누적된 합의의미로 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것 앞에서부터 더함 : prefix sum 뒤에서부터 더함 : suffix sum >보통 코테에는 prefix sum만 나오고 suffix

주석을 달면서 풀기코드를 바로 작성하지 말기문제 지문에서 최대 최소 범위 파악무식하게 풀 수 있으면 무식하게 풀어라 (브루트 포스)아니면 다른 알고리즘 생각하기논리적으로 로직을 손코딩 for i = 0 -> n 어떤 자료구조 쓸지 생각반례가 있는지 생각하기

정점 약자 : u (from) or v (to) outdegree : 정점으로 나가는 간선 indegree : 들어오는 간선

자식 노드와 부모 노드로 이루어진 계층적인 구조 무방향 그래프의 일종이자 사이클이 없는 자료구조부모, 자식 계층 구조Vertex - 1 = Edge임의의 두 노드 사이 경로는 유일무이하며 반드시 존재💡TIP문제, 면접에서 트리가 주어지면 루트 노드부터 탐색하는 것이

이진 트리(BT) 각각의 노드에 자식 노드 수가 2개 이하로 구성된 트리 종류 정이진트리 : 자식노드가 0개 or 2개 완전 이진 트리 : 왼쪽에서부터 채워진 트리 변질 이진 트리 : 자식노드가 1개 포화 이진 트리 : 모든 노드가 꽉 차있는 트리 ⭐️ 균형 이진

그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬0 : 두 정점 사이 경로가 없음1 : 두 정점 사이 경로가 있음a\[from]\[to] = 0 or 1a\[3]\[5] = 1;a\[3]\[5] = 1;a\[5]\[3] = 1;bool a\[20]

각 정점마다 연결된 정점들 배열로 만들기마지막 요소에 삽입, 삭제 : O(1)특정 요소 탐색 : O(n)n번째 인덱스에 삽입, 삭제 : O(1)n번째 요소 참조 : O(n)n번째 인덱스에 삽입, 삭제 : O(n)n번째 요소 참조 : O(1)인접리스트를 구현할 때 많이

인접행렬 : O(V^2)bool adj\[V]\[\[V];인접리스트 : O(V+E)vector<int> adj\[V];인접행렬 : O(1) (a\[i]\[j])인접리스트 : O(V) (최악의 경우 = 모든 정점이 연결되어 있을 때)인접행렬 : O(V^2)인접리스트

문제 Q. {0,0} 좌표에서 dy, dx를 만들어 4방향(위, 오른쪽 ,아래, 왼쪽)을 탐색하며 좌표를 출력 Q. {0,0} 좌표에서 dy, dx를 만들어 8방향(위, 오른쪽 ,아래, 왼쪽, 대각선)을 탐색하며 좌표를 출력 Q. 3*3 맵을 입력받아야 함. 1과 0으로 이루어져 있고 {0,0} = 1, {0,0} 좌표에서 4방향을 기준으로 한 칸씩...

각 노드에 인접한 노드를 재귀적으로 방문방문한 노드는 다시 방문하지 않음

왼 -> 오 -> 루트자식 이후! 루트 -> 왼 -> 오자식 이전!DFS왼 -> 루트 -> 오자식 중간!BFS

절차 문제 해결 풀이 분석 어떤 알고리즘이 나을까? 성능이 좋은 순 O(1) 상수 실행 시간 (constant running time) 상수 실행 시간 입력의 개수와 무관 O(log n) 로그 알고리즘 (logarithmic algorit

수도 코드찐 코드균형 이진 검색 트리에서 룩업 : O(log(n))삭제 및 삽입 : O(log(n))왼쪽 자식만 따라가면 가장 작은 값, 오른쪽 자식만 따라가면 가장 큰 값모든 노드를 정렬된 순서로 출력 : O(n)어떤 노드 다음으로 높은 노드 찾기 : O(log(n)

모든 경우의 수를 따져봄순열, 조합, 경우의 수, 1억 미만까지 ㄱㅊ가능하면 반복문 사용조합 or 순열 + DFS, BFS 등의 알고리즘경우의 수마다 생각해야하는 로직 💡 TIP 💡 초기화 주의최댓값을 구하라 -> 답이 될 수 없는 최솟값으로 초기화해놓기원상 복구

https://jungol.co.kr/백준 문제를 프로그래머스처럼 채점 가능!

https://www.acmicpc.net/problem/2615 문제 알고리즘 접근 방법 >10950번과 비슷해 보이나, 이 문제의 핵심은 몇 개를 입력 받는지 알 수 없다 는 것이다. 고로 EOF 를 사용하여 입력의 끝까지 반복해서 a와 b를 입력받고 합을 출

모든 정점 ~ 모든 정점으로 최단 경로 구하기 거쳐가는 정점

https://school.programmers.co.kr/learn/courses/30/lessons/72413플로이드 와샬 알고리즘1\. 모든 i,j 정점으로 최단 경로가 저장된 테이블을 완성한 후2\. s부터 i까지 최단 경로 (합승) + i부터 a까지

https://school.programmers.co.kr/learn/courses/30/lessons/12946재귀 -> 여기까진 생각해냈다.. ㅎ근데 어떻게?1->2 : n-1개의 원판을 옮긴다. 1에는 가장 큰 n번째 원판만 남게 된다.1->3 : 가장

이분탐색을 이용해최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것다음과 같이 나이순으로 정렬된 사람들이 있습니다. 그리고 25살 이상이라면 소주를 좋아한다는 것이 증명되어 있다고 합니다. 그럼 이 중에서 소주

https://school.programmers.co.kr/learn/courses/30/lessons/86053이분 탐색 과 파라매트릭 서치 를 활용한다.1\. 구해야 하는 값인 시간을 start , end 로 정한다.2\. 범위를 기반으로 이분 탐색을 진

https://school.programmers.co.kr/learn/courses/30/lessons/178870누적합 이용// 수열의 개수가 1인 경우// prefix1 - prefix0 = 1 - 0 = 1// prefix2 - prefix1 = 1+2

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1882 접근 방법 > DP 로 시도 ! > ex. ["ba","na","n","a"] "banana" 3 DP 배열은 최대 숫자(INF) 로 초기화한다.

https://school.programmers.co.kr/learn/courses/30/lessons/12929n값의 범위가 작아서 가능했던 것 같다.괄호의 개수로 만들 수 있는 모든 문자열을 순열을 이용해 구한 후스택을 이용해 올바른 괄호인지 판단한다.찾아

문제 https://www.acmicpc.net/problem/16637

동생보다 왼쪽에 있으면 +1, \*2동생보다 오른쪽에 있으면 -1재귀함수를 돌려서 완전 탐색으로 시도해보았으나, 시간복잡도가 초과되었고, 로직도 잘못되었음 5 -> 4 -> 8 -> 16 -> 17 로 갈 수도 있는데뺄샘을 동생보다 오른쪽에 있을 때만 해서 fail 방

https://www.acmicpc.net/problem/13913기존 숨바꼭질2 문제 + 추적처음에는 인접리스트를 이용해서 풀 수 있겠다고 생각하였으나 생각해보니 BFS를 이용해서 1번만 방문하기 때문에 인접리스트까지 이용하는 것은 비효율적이다. 이전 위치를

https://www.acmicpc.net/problem/1931그리디끝 기준으로 오름차순 정렬되는 회의를 최대한 많이 끼워 넣는다.태도를 우디르급으로 전환하기.. 끝 기준 정렬

그리디로 문제를 풀려면? 최적 부분 구조 (optiomal substructure) 이 state에서 최선을 다해 선택하는 해가 결국 전역적인 최적해로 이어지기 탐욕적 속성이 증명이 되어야 한다. 보통 귀류법으로 증명한다. \>>> 코테에선 사실상 불

https://www.acmicpc.net/problem/1202그리디가방을 무게 오름차순으로 정렬보석을 무게 오름차순으로 정렬가방을 반복문으로 돌면서 담을 수 있는 보석의 가격을 우선순위 큐에 다 넣고, 제일 가격이 높은 거 1개만 빼기 N이 클 때(천만~

https://school.programmers.co.kr/learn/courses/30/lessons/181188최근 배운 그리디, 정렬을 이용했다.1\. 끝 점을 기준으로 내림차순 정렬을 했다.2\. 처음부터 시작한다. (시작점 저장)3\. 현재 끝점보다

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=cpp숫자 앞의 부호를 +인 경우, -인 경우를 재귀를 통해 호출하여완전탐색 하였다.처음 시도한 방법이 맞았으나 가독성을 위해 매

https://www.acmicpc.net/problem/7568구현키, 몸무게 pair 벡터를 입력 받은 후2중 for문을 돌려서 자신보다 덩치가 큰 덩치가 나올 때마다 등수를 올리고 출력한다.처음에 문제를 보고 우선순위큐까지 생각했다가.. 너무 복잡하게 생

https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=cpp가로 세로 중 큰 것을 x, 작은 것을 y 로 고정한다.최댓값을 계속 갱신한다.복잡하게 생각했다 22

https://school.programmers.co.kr/learn/courses/30/lessons/43163DFS로 재귀 + 백트래킹매개변수 : 현재 단어, 카운트종료 조건 : 현재 단어와 타겟 단어가 같을 때 방문하지 않고, 두 문자열이 1문자만 다를

https://school.programmers.co.kr/learn/courses/30/lessons/49189BFS와 인접리스트를 이용하였다.1부터 시작하므로 queue에 1을 먼저 넣고인접한 요소를 차례로 방문해나가며 거리를 갱신했다.최단거리 = BFS!

https://school.programmers.co.kr/learn/courses/30/lessons/42898DP를 이용한다. dpi 는 i, j로 갈 수 있는 길의 개수dpi == 물웅덩이 -> -1로 초기화 하고 dpi += 왼쪽에서 올 경우(물웅덩이가

https://softeer.ai/practice/info.do?idx=1&eid=2050&sw_prbl_sbms_sn=266553주어진 m개 위치를 순서대로 방문하는 개수를 구하는 문제이다.완전탐색 + 백트래킹으로 다음 목적지 idx, 현재 위치 y, x를

https://softeer.ai/practice/info.do?idx=1&eid=1717&sw_prbl_sbms_sn=266595m보다 작은 개수 \* m보다 큰 개수를 반환하는 문제lower_bound를 이용하였다.처음에 벡터에 주어진 q가 없을 때를 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42626priority_queue를 이용했다.std::greater<int>를 이용해 오름차순 정렬을 하여, 가장 안 매운 순서대로 정렬되게 하였다.

https://www.acmicpc.net/problem/1655우선순위 큐로 일정 횟수만큼 pop 한 뒤 top을 출력 -> 시간 초과100,000 \* 50,000번 = 5,000,000,000 무조건 시간 초과 최대힙과 최소힙 2개를 이용한다.최대힙의 크

https://www.hackerrank.com/challenges/one-week-preparation-kit-time-conversion/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=prepa

https://www.hackerrank.com/challenges/one-week-preparation-kit-lonely-integer/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=prepar

https://www.hackerrank.com/challenges/one-week-preparation-kit-caesar-cipher-1/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=prepa

https://www.hackerrank.com/challenges/one-week-preparation-kit-tower-breakers-1/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=prep

https://www.hackerrank.com/challenges/one-week-preparation-kit-grid-challenge/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=prepar

https://www.hackerrank.com/challenges/one-week-preparation-kit-recursive-digit-sum/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=p

https://www.hackerrank.com/challenges/one-week-preparation-kit-new-year-chaos/submissions?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=pr

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&problemLevel=3&problemLevel=4&contestProbId=AV5LrsUaDxcDFAXc&catego

문제 https://school.programmers.co.kr/learn/courses/30/lessons/181187 접근 방법 > 원의 방정식 (x^2 + y^2 = r^2) 을 이용한다. x가 1일때부터 ~

https://school.programmers.co.kr/learn/courses/30/lessons/176962구현 문제 1\. 00:00 ~ 23:59분으로 주어져 있는 문자열을 모두 계산하기 편하게 분으로 바꾼다.2\. 수행할 과제 idx와 현재 시간

https://www.acmicpc.net/problem/2504먼저 stack을 이용해 올바른 괄호열인지 판단한다.짝이 맞으면 pop 아니면 pushempty 면 올바른 괄호이다.top 을 체크할 때 empty를 함께 체크하여서 런타임 에러가 나지 않도록 주

문제 https://www.acmicpc.net/problem/1068 접근 방법 반례 지운 노드의 부모가 리프노드가 될 경우 >2 -1 0 1 정답 : 1 >9 -1 0 0 5 2 4 4 6 6 4 정답 : 2 > 2 1 -1 0 풀이 정리 참고 h

https://www.acmicpc.net/problem/1967리프 노드들의 리스트를 구한다리프노드 ~ 리프노드 사이 거리 중 가장 긴 거리를 구한다.이 때 lca(최소공통조상) 을 이용한다.트리에서 임의의 정점 x(나는 root로 했음)를 잡는다.정점 x에

https://www.acmicpc.net/problem/9184예제 식을 풀어서 쓰다 보니 메모이제이션을 사용하면 될 것 같았다.dpac 는 w(a, b, c) 값을 저장해 놓고필요한 값이 저장되어 있다면 그 때 dp배열에서 값을 꺼내고아니라면 값을 계산해서

문제 https://www.acmicpc.net/problem/21921 소요 시간 문제 이해 : 15분 풀이 : 20분 접근 방법 > 1) 완전탐색 배열을 돌면서 X기간별 다 더해보고 max 값을 갱신하며 개수를 센다. > 2) 슬라이딩 윈도우 2중 반복문을 없애기 위해, 0~X까지 초기합을 구한다음 앞으로 한 칸씩 이동하였다. 풀이 1차 ...

https://school.programmers.co.kr/learn/courses/30/lessons/67256넘버가 1,4,7이면 왼쪽 / 3,6,9면 오른쪽아니면 왼쪽 현재 위치와 오른쪽 현재 위치 각각에서 거리를 구해서 작은 곳으로 가도록 한다.왼쪽 현

https://school.programmers.co.kr/learn/courses/30/lessons/778851차 시도다른 부분을 찾기 위해 XOR 연산을 사용하였다.각 num 부터 1씩 더하며 XOR 연산 한 값에서 1의 개수를 세어 1이나 2면 답이다.

https://school.programmers.co.kr/learn/courses/30/lessons/120826letter가 1글자라서 문자열을 돌면서 일치하지 않으면 새 문자열에 넣었다. <string> 의 erase와 remove를 잘 활용할 수