알고리즘

2021-12-4(토)https://www.acmicpc.net/problem/10448https://www.acmicpc.net/problem/14501풀이는 알겠는데 구현하기 조금 힘들었다 DFS로 풀었다.https://www.acmicp

https://www.acmicpc.net/problem/1063하라는대로 조건만 맞추면 답이 나오는 문제이다.8가지 이동할수 있는 방법을 어덯게 중복코드 없이 작성하는가 이것이 중요한문제이다.이렇게 배열에 담고, 반복문으로 8가지 경우 중 한가지를 찾으면중복

BOJ 7573번 바로가기

처음에 N\*N을 구현하고 처음부터 완탐을 했었는데, 시간초과가 났다.N<=10^4이라 당연한 결과였다.효율적으로 가장 많은 물고기를 잡는 그물들을 특정해서 구현을 해야한다.즉 그물의 길이 또는 물고기의 개수로 한정지을만한 조건을 구해야된다.그물을 치는것에 영향을

완전탐색을 생각안하고 복잡하게 돌아서 생각하다가 solv를 찾아봤다.간단하게 풀릴수 있는지부터 확인해보는게 필요하다N에 대해 가장가까운 수를 바로 만드는것이 아니라0부터 올려가면서 조건에 맞는 답을 찾으면된다.

상자가 3개로 고정되어있으므로 완전탐색을 쓰기로 했다.바뀌는 경우의 수는1\. 옆으로 회전시2\. 상자위치 변경3\. 상자 구조 변경이렇게 옆으로 회전하는 경우를 계산했다.반복문을 3개쓰고 if문으로 안되는 경우를 걸렀다. 이렇게 q w e로 3가지의 상자를 표현했다.

처음에는 완전탐색으로 풀려고 해봤다.N개에 개미에 대해 최대 L번 돌려야하니 시간초과가 날 수 밖에없다.구현보다는 아이디어가 어려운 문제였다.충돌을 해도 결국 떨어지는 시간은 또같다.그냥 몸이 바뀐것과 마친가지로 쭉 가게된다.충돌시 -방향과 +방향의 각각의 총합은 일정

조합 kC6를 나열하라는 문제이다.완전탐색시 12C6의 경우의 수를 가지므로 (2^12) / 2 = 2^11 = 2048가지이렇게 for문을 중복하면 q w e r t y 로 원하는 조합을 만들 수 있다.if문으로 조건을 걸어서 원하는 조합만 꺼내 쓸수 있다.

모든 경우의 수를 조사하는것이 아닌 답이 될 수 없는 경우 즉, 유망하지 않은경우를 제외하면서 완전탐색을 하는것이다.문제의 경우의 수를 단순히 계산해보면 N^N이다.(x,y) = (1,1)에 퀸이있고, (2,2)에도 퀸이 있을경우 그 뒤의 경우는 더 이상 조사할 필요가

참고 https://itguava.tistory.com/67

1, 2, 3을 활용해서 11이하의 자연수 N을 순서있이 만들어 내는 방법의 수를 구하면된다.4 = 1+1+2 와 4= 1+2+1은 다른 경우로 계산한다1와2와3의 개수만 파악한다면, 확률과 통계에서 배운 서로다른 3개의 색상의 의자를 배열하는것과 같이 (i+j+k)!

문제해석 p1=1, p2=5, p3=6, p4=7일경우 N=4개를 가지기 위한 금액은 p1으로 4개를 살경우 4원, p2 1개, p1 2개를 사면 7원, 최대금액은 p2를 2번구매하는 10원의경우이다. 이 경우를 찾으면된다. DP

https://www.acmicpc.net/problem/117262xn 크기 직사각형을 2x1과 1x2로 채우는 경우의 수를 구하자.n=1 : 1가지n=2 : 2가지n=3 : 3가지n=4 : 5가지...n=n : (n=n-1)가지 + (n=n-2)가지

문제링크 : https://www.acmicpc.net/problem/14728다이나믹프로그래밍의 가장 기본이 되는 원리이다. 한문제에 대한 해가 최적이면 그 문제를 이루는 부분문제들의 해도 최적이다.a -> b -> d로가는 최적의 길이 Jab+Jbd 이면

간단히 N=1일때와 N=2 일때를 계산해보자.앞에 수가 어덯게 쓰이는가에 따라서 뒤에 수가 결정된다.이 아이디어에서 점화식을 끌어낼수 있다.주어진 점화식을 바탕으로 답을 구한다.dpn = b // n:숫자길이, a: 마지막으로 끝난 수, b: 숫자길이가 n이고, 마지막

n=1,n=2일때를 대입해서 구해본다.바로 옆과 위에는 사자가 올 수 없으니, 한줄에 사자를 놓는방법은 3가지이다.OX 또는XO 또는XX 또는O : 사자, X : 빈자리n번과 n-1번 사이에 관계식을 구한다.반복문을 통해 답을 구한다.n=1, 답:3 n=2, 답:7 이

11048번 이동하기 문제풀이 > 전형적인 DP의 최적의 원리가 보이는 문제이다. 최적의 원리 :

여러가지를 선택하는 것들중 최적의 방법으로 선택을 하는 문제는 대부분 DP로 풀리는거같다.이 문제도 보자마자 DP가 떠올랐다.dpN = S // N잔의 포도잔중 가장 많이 마시는 량이 문제의 조건은 연속해서 3잔을 마시지 못하는경우이기때문에N번째잔을 마시는경우와 마시지

한글로 번역하면 최장 공통 부분수열이다. 비슷한 개념으로는 최장 공통 문자열(Longest Common Substring)이 있다.후자는 말그대로, 두 문자열중 공통되는 문자열이 연속으로 이어지는 문자열을 말한다.ACAYKP와 CAPCAK의 최장 공통 부분수열은 ACA

제곱수의 합 잘못된 풀이 N보다 작거나 같은 제곱수 중에서 가장큰 값을 빼가면서 값을 구했다. 즉 반례 12 12 = 2^2 +2^2 +2^2 으로 3이나오지만, 잘못된 풀이는 12가 나오게된다. > 가장 큰 제곱수로 빼는것은 가장작은 답을 추출해 내지 못한다.

가장 간단한 풀이이다.i번째부터 j번째까지 더하는것이 답일것이다.시간복잡도는 N^2, N=100,000이므로 10^10으로 시간초과가 난다.정답은 어느시점부터 i번째 까지 더한수가 정답일 것이다.즉, i번째 숫자를 더했을때 연속합을 dpi, ret라는 변수를 두고 최대

가장 긴 감소하는 부분 수열 DP풀이 이전에 풀었던 연속합과 같은 느낌으로 dp[i]를 i번째 항을 포함하는 가장 긴 감소하는 부분수열로 정했다. > i부터 j까지 어느 시작점과 끝지점이 있는 선택문제는 i번째항을 포함하는 dp로 정하면된다. dp[i]를 어떻게

n-1개의 건물에서 1개가 추가 되면 n개 건물이 된다.dpn과 dpn-1사이의 관계식을 어떻게하면 도출해 낼수 있을까?1개의 건물이 추가될때, L과 R이 바뀌는 경우가 있고 바뀌지 않는 경우가 있다.바뀌는경우는 크게 두가지, dpir = dpi-1r + dpi-1r-

조건이 상당히 복잡해보인다. M개 줄, N개의 요소 라고 용어를 정리하고 들어가자.k번째 줄을 선택하면 위아래 줄은 그대로 없어진다. 즉 M개줄 중에서 가장 많이 선택해도 M/2개를 넘을수 없다.N개의 요소중 가장 많이 선택하는 방법은 N이 짝수일때 N/2개, 홀수일때

자료구조의 한 종류, 컴퓨터 파일의 구조처럼 들어갔을때 거기서 또 나눠지고, 들어가는것을 트리라한다.트리 내부 요소들을 순회하는 방법으로는 대표적으로전위순회, 중위순회, 후위순회가 있다.위에그림에서 A부터 전위순회ABDHIEJCFG, 부모노드 -> 왼쪽자식 -> 오른쪽

자료구조의 한 종류, 정점(vertex)와 간선(edge)로 이루어진 자료구조.즉. 점과 선으로 이루어진 자료구조. 트리는 부모노드와 자식노드가 간선으로 연결되어 있으므로, 그래프의 한 예시이다.대표적으로 DFS와 BFS가 있다.정점에서 한 간선을 통해 다른정점으로 이

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.그래프의 간선들이 주어지므로, 루트노드가 1번인것을 이용하여 트리를 구성한다.DFS와 BFS를 이용하여 트리를 구성해나간다. 여기서는 DFS로 풀이를

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.BFS와 DFS의 탐색방법을 통해 그래프를 탐색한다탐색되지않은 정점이 있다면 그 정점을 시작으로 다시 탐색하고, 횟수 카운트모든 정점이 탐색됫다면

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.트리는 사이클이 없는 연결 요소이다.

트리 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를

트리의 지름은 가장 끝에 있는 두 노드 사이의 가중치의 합이다.어느 한 노드에서 가장 멀리있는점은 지름에 해당하는 노드중 한 노드이다.그 점에서 가장 멀리있는 노드 사이의 가중치 합을 구하면된다.즉, dfs를 두번쓰면 된다.벡터배열+pair가 들어가서 문제를 풀때 햇갈

inOrder와 postOrder로 preOrder를 구하는 문제이다.이 문제를 풀면서 2가지 막히는 부분이 있었다.첫째 : 알고리즘 자체를 모른다. inorder와 postorder를 어덯게해야 preorder가 나오는지 모르겠다.둘쨰 : 알고리즘을 코드로 옮길수 없

graph에서 간선을 알려주고, i에서j로 갈수 있는지 인접행렬로 표현하는것이다.여기서는 bfs로 풀었다. 예를들어1\. i번째 줄에서, boardi==1를 찾아 그 요소를 q.push(j)한다.2\. q의 원소를 한개씩 꺼내서, boardi !=1이라면, q.push

유기농 배추 문제 왼쪽 오른쪽 위 아래를 인접으로 보고 지렁이가 최소 몇개가 필요한지를 구하는 문제이다. 풀이 먼저 지렁이가 필요한 위치에 놓고, 그 인접한 부분을 dfs나 bfs로 계속해서 탐색해 나가면 된다. 코드 작성 간단한 풀이지만, 코드를 간결하고 이쁘게

음식물 피하기 문제 유기농 배추와 99% 동일한 문제이다. 풀이

섬의 개수 문제 및 풀이 실제 코드

1번 정점에 연결된 정점들을 dfs나 bfs를 이용하여 탐색하면된다.탐색을 하면서 카운트를 한개씩 올린다.

나눠진 영역의 어느 한점 부터 인접한 점으로 탐색을 이어나간다.탐색이 끝나면 영역갯수를 1개 늘리고, 탐색한 넓이를 기억해둔다.백준의 예시그림에서는 (0, 0) 왼쪽 아래에 위치해 있지만, 우리가 디버깅을 하면서보는 배열은 왼쪽 위가 (0,0)이다. 차후에 디버깅을 위

dfs를 이용해서 탐색을하고 cnt를 하나씩 올리면 된다.코드 작성중 reset()를 작성할때 graph배열의 인덱스를 1부터 n까지쓰므로초기화할때도 1부터 n까지 다 초기화를 해줘야한다.나는 실수로 0~n까지 초기화를 시켰다.

전형적인 dfs탐색 문제이다.컴퓨터를 1번부터 dfs탐색시켜서 탐색수가 최대인 노드들을 답으로 쓰면된다.탐색을 할때마다 reset()으로 방문한 노드를 체크한 visited배열을 초기화 시켜줬다.

촌수를 계산하기위해 사람을 정점, 부모 자식관계를 간선으로 생각했다.그래프 탐색은 가장 짧은 동선을 찾기 편한 BFS로 탐색을 진행했다.노드를 한단계식 더 탐색해 나갈때마다 cnt를 한개씩 올렸고, 목적하는 노드가 나오면그 cnt를 ans에 저장했다.

모든 토마토가 있는 지점에서 상하좌우로 퍼져나가므로, BFS로 풀면 된다.queue를 만들어, 반복문으로 토마토가 있는지점을 모두 넣어준다.queue가 빌때까지 요소를 하나씩 front, pop해가면서 농장을 채워 넣는다.며칠이 지났는지 체크를 해야하므로, 날짜가 지나

토마토

비의 높이를 0부터 100까지 올려가면서 반복을 한다.각각의 물에 높이일때, 각각에 물에 안젖는 지점 && 방문되지 않은지점에 대해 DFS를 실행시키면서 cnt를 1개씩 올린다.비의높이가 바뀔때 방문지점 reset()시켜준다.

가장 거리가 먼지점을 가장 가깝게 연결한 길이를 구하는 문제이다.각각의 지점에 대해 BFS를 쓰면서 최대값을 최신화 해주면 된다.BFS를 한번한 이후 초기화 시켜주는것도 잊지 말자.dfs는 한번에 깊게 멀리 들어가는 알고리즘 특성상, 가장 효율적으로 길이를 가지 않는다

dp가 잠깐 생각 나긴했지만, dpi를 적고 풀어보려했다. dpi와 dpi-1과 dpi+1 dpi/2의 연관성을 찾아 관계식을 도출해 내서 반복문을 통해 dpi를 채워나가면 문제가 풀릴거 같았다. 하지만 앞으로 뒤로 갈수있는 양방향 문제에서 어떻게 짜야할지 얘매했고,

처음 생각해낸 방법이지만, 오류가 있는 풀이이다.1\. dfs를 2번까지만 반복한다는 생각으로 시작했다.2\. 1번(주인공)에 대해서 첫번째 친구에 대해서 탐색을 하고, 그친구의 친구를 탐색한다.3\. 두번째 친구를 탐색하고, 그 친구의 친구까지 탐색을 한다.4\. 탐

비효율적이지 않은 동선으로 가장 먼지점을 구하면 모두다 구할수 있다.따라서 BFS를 사용했다 (DFS는 가장 효율적인 동선을 선택하지 않는다.)BFS를 쓰는 가장 전형적인 유형이다.

트리의 지름은 예전에 풀어봤던 트리의 지름과 또같은 문제이다.어느 한지점에서 가장 먼지점은 지름에 해당하는 점중 하나이다.이 생각을 가지고, bfs를 써서 지름에 해당하는 한 지점을 구하고,구한 지점에서 bfs로 가장 먼지점과의 거리를 구해서 출력해주면 된다.bfs를

https://www.acmicpc.net/problem/117262\*n 길이의 타일을 만드는 경우의 수를 구하는 문제이다.n길이의 타일은 이전 n-1 또는 n-2 길이의 타일에 타일을 하나 추가해서 만드는 것과 같은 것을 직관으로 알 수 있다.따라서 이전

조건을 만족하는 숫자의 개수를 구하는 문제이다.자리수가 하나씩 증가하기 때문에 i자리 숫자의 개수와 i+1자리 숫자의 개수가 연관이 있을 수 밖에없다. 여기서 dp라는 포인트를 잡아야 한다.연관이 있는거같긴한데 계단수를 직접 써봐도 dp 변수와의 연관성을 찾기 쉽지 않

업로드중..두 문제 모두 DP로 푸는 문제이다. 인덱스 i로 이전 dp에 접근하여 조건문으로 해결가능하다. 주의해야할점은 포도주문제의 경우 무조건 마셔야되는 범위가 없지만 계단오르기문제의 경우 세 계단을 가면 무조건 한 계단은 올라야 한다. 이러한 차이점 때문에dpi=

파이썬에서 기본적으로 사용하게되는 list 자료형 3, 2, 1 은 nlogn 시간복잡도를 가진 정렬함수 sort를 제공한다. 따라서 나도 단순히 input , print로 입력을 받고 출력하는 코드를 작성했지만 fail이 떴다.문제는 input 과 print함수는 느

해당 조건을 만족하는 정렬을 구현하는 문제이다.파이썬은 sort함수를 기본적으로 제공하기 때문에 이걸 잘 활용하는 것이 중요하다.sort함수는 key옵션으로 기준을 정하여 정렬이 가능하다.lambda함수를 같이 사용하여 쉽게 조건을 만족하는 정렬을 구현할 수 있다.la

N의 범위가 10까지 밖에 안되기때문에 N!가지의 경우의 수로 모든 경우를 계산할 경우에도 360만 경우의수이다. 따라서 완전탐색으로 문제를 해결하였다.permutation먼저 생각난 아이디어는 순열로 경로를 미리 저장하고 그 저장된 경로를 계산하는 방식이다.경로의 값

해당 문제는 특정 목적지까지 특정조건(사탕을 최대한 많이 가지도록)을 만족하면서 가는 길을 찾는 문제이다.문제를 보는 순간, 최적화된 경로를 찾는 문제의 한 종류이므로, BFS 나 DFS를 사용할 것이라 생각했다.그리고 현재의 최선의 선택이 최종적으로 최선의 선택이 된

최종적으로 답은 S(1) ~ S(n) 까지의 합이다.S(m) 은 민균이가 추가로 갚아야하는 돈이고, 해당 금액을 계산하는 방법은A 배열에서 m개의 원소를 추출해서 m\*(그 원소들중 최댓값) - 원소의 합이다.즉 최댓값에서 각원소를 뺀 값들을 모두 더한것이다.가장 쉽게

한지점 -> 특정 지점 까지의 최단거리이므로 BFS로 풀면 될거라 생각했다.기본적인 BFS라 생각했으나 테스트케이스에서 계속 틀려서 고민을 많이 했다.평소 백준문제를 풀때는 board가 input으로 주어져서 x와 y를 boardx로 편하게 지정할 수 있었지만, 여기서

그리디를 통해 풀 수 있는지 먼저 고민해봤다.특정 회의를 선택하면 그 뒤에도 계속해서 최적의 해가 되지 않을까0시간 부터 탐색한다고 가정했을때, 가장 빨리 끝나는 회의부터 선택을 한다면 최적의 해가 된다.각 회의는 시작시간, 끝시간을 가지고 있으므로 정렬이 필요한데,

코테에서 자주 나오는 유형의 이분탐색이다.이분탐색은 정렬된 배열에서 특정 값을 찾는 일이고 후보를 한번 탐색할때마다 1/2로 줄여가는 알고리즘이다.유튜브 영상해당 영상을 보고 쉽게 이해할 수 있다.1654 문제는 이분탐색을 사용하여 특정값이 아닌 범위중 최댓값, 최솟

https://school.programmers.co.kr/learn/courses/30/lessons/64062해당 문제를 보고 이분탐색이라고 생각하지 못했고"mid 번째 친구가 징검다리를 건널 수 있는지" 라는 문장을 힌트로 듣고 이분탐색이구나 라는 걸 알

투 포인터인지 문제를 보자마자 알진 못했다. 이것도 실전에서는 여러 알고리즘을 하나씩 가능한지 확인해보고 사용하게 될 것 같다.left right를 0으로 초기화한다left가 범위를 넘어가지 않을때 까지 반복조건을 충족하면 left ++조건을 충족하지 못하면 right

DFS가 사용되는 상황은 크게 3가지이다. 한 정점과 연결된 모든 정점을 찾는 문제 경로를 찾아야 하는 문제 사이클 존재 유무를 찾아야 하는 문제 9466번 텀 프로젝트는 3번 유형에 해당한다.

시작점, 끝점이 주어질때 끝점으로 이동하면서 주어진 조건에 따라 최소값 또는 최댓값을 구하는 전형적인 BFS 문제이다.시작점 : 0,0끝점 : 500,500문제의 조건 : 영역에 따라 0 또는 1을 더 하고 갈수 없는 지역이 존재다음 영역에 대한 비용 Cost를 계산할

N개중 중복없이 M개를 추출하는 조합문제이다.순열조합 정도는 묶어서 DFS 풀이해야된다고 기억하는 것도 괜찮고, 다시 생각해보면 1부터 N까지 가면서 M개를 선택하는 "경로 를 선택"히는 문제이므로 DFS라고 생각할 수 있다.그 다음 생각할만한건 M개를 선택해야하니까

특정 행동에 대해 선행되어야 하는 행동이 있으면 위상정렬문제이다.2가지 변수를 기억하자. b를 풀기 위해 먼저 풀어야하는 문제의 수를 저장하는 int\[] degree 변수선행문제를 풀었을때는 후행문제의 degree를 낮춰줘야하므로 후행문제를 저정하는 int adj 변

시간을 알면 인원수를 쉽게 구할 수 있고, 숫자의 범위가 매우 크므로 이분탐색을 생각할 수 있다."정렬", 정렬을 놓쳤다... 풀어놓고 왜틀렸지.. 시간낭비했다. 코테에서는 절대 절대 주의하자.right를 쉽게쉽게 설정할 수 있는 문제만 만나봤는데 이 문제는 꽤 섬세하

문제 링크범위가 작았더라면 배열을 선언해서 boolean으로 체크해볼 수 있겠지만, 범위가 최대 20억이기 때문에 시간초과가 난다.그보다 효율적으로 접근해야 한다. N 는 100만이기 때문에 N을 하나씩 처리해나가려 한다.N를 정렬해주고 가장 앞의 선 부터 처리하도록

문제 링크서로 두 다른 원소가 같은 집합에 포함되어 있는지 확인할 수 있는 알고리즘이다.유니온(합집합), 파인드(찾기) 함수로 이루어져 있다.유니온 파인드를 개념적으로 이해하긴 쉽지만 중간에 놓치면 안될 중요한 포인트가있다.바로 find 함수에서 경로압축에 따라 시간복

문제링크(https://school.programmers.co.kr/learn/courses/30/lessons/42895문제를 보고 어떻게 푸는지 감이 안왔다. DP문제라는 것을 알고 봐서 DP목표숫자 = 최소 숫자 로 구성되진 않을까 하고 끼워맞춰 보려했지

기존의 계산식을 재사용하여 더 큰 문제를 풀 수 있으므로 DP로 풀었다.dpn = value 로 n번째칸에서 최대 값 value로 표현할 수 있는데 여기서 조건이 연속으로 3칸 갈 수 없으므로 이차원 배열을 사용해서 풀이했다.dpn = value , 연속으로 cnt칸

문제를 보고 처음 생각했던건 BFS 풀이였다. (단순히 DFS로 계산하면 시간복잡도는 nm 각 지점에서 nm 번 탐색이 이뤄질 수 있으므로 500^4 = 624억 이므로 시간초과가 발생한다)dpx는 (0,0) 에서 (x,y)로 갈 수 있는 경로의 수로 정했고, BFS를

시간을 정말 많이 써서 고민했던 문제이다. 결국 풀이를 보고 해답을 얻었다 ㅠㅜ..풀기 위해 고민해야 할 부분을 정리해보자.이렇게 기본 소스가 되는 novel 변수를 합쳐서 하나의 파일을 만드는 문제는 idx가 줄어드므로 시작위치, 끝 위치를 DP 변수로 설정하면 된다

문제는 00 타일과 1타일을 사용하여 만들 수 있는 길이 N의 2진수의 개수를 구하는 문제이다.단순 0 1 DFS를 통하면 2^100만이고, 결과값을 15746으로 나눈 나머지이므로 DP 문제이다.DP 풀이의 순서는 아래처럼 풀면 된다.DP 점화식 구하기DP 초깃값 설

문제 : https://www.acmicpc.net/problem/13335개인적인 스타일로는 구현은 손코딩을 최대한 많이 해놓고 실제 코딩하는게 구조를 기억하고 전체적인 그림에서 하나씩 차근차근 나아가기 좋았다.t=0으로 시작해서 1씩 올릴지, 1을 올리기

문제를 보고 특정한 알고리즘이 아니라 조건문과 반복문을 잘 사용하면 풀 수 있을거같아 구현문제로 판단했다.실제 테스트케이스를 통해 구현을 어떻게 해야할지 조건을 찾았다.먼저 실제 저런 기호로 주어진 수식을 풀어보면 한번 확인하면서 문자열을 넘어갈 수 있다. 즉 O(N)