백준

문제 : 백준 1504번 특정한 최단 경로알고리즘 : 다익스트라설명주어진 두 개의 노드를 거쳐 1번 노드에서 N번 노드로 방문하는 최단 경로 구하기노드, 에지 중복 가능1번 → 경유지1 → 경유지2 → N번1번 → 경유지2 → 경유지1 → N번두 가지 경로 가능1번,

알고리즘 : 벨만-포드 알고리즘 느낀 점 ㅇㅇ 링크 : https://www.acmicpc.net/problem/11657

문제 : 백준 11404번 플로이드알고리즘 : 플로이드-와샬 알고리즘알고리즘 설명모든 노드 간의 최단 거리를 저장하는 리스트를 만듦각 원소를 돌면서 k를 지나는 거리와 지나지 않는 거리를 비교해 갱신k를 1부터 n까지 증가시키며 bottom-up으로 DP 수행주의할 점

코드

상, 하, 좌, 우로 인접한 구역의 개수를 카운트해서 출력하는 문제모든 좌표를 돌면서1이면서 visited==False인 좌표에 대해 DFS 수행count += 1현재 좌표에 대해 visited=True네 방향을 모두 검사하여 재귀적으로 DFS 수행https:

출처 : https://www.acmicpc.net/problem/12100풀이방법 : 완전탐색순서각 시행마다 가능한 4가지 경우(up, down, left, right) 모두 대입시행 횟수가 5회 이상일 경우 리스트에 최대값 추가 후 종료리스트에서 최대값 출

출처 : 아기 상어풀이 방법 : 최단 경로 (벨만포드)순서모든 노드까지 거리 구하기(relax 연산 반복)거리가 최소인 노드로 이동반복relax 연산 방법목표 노드까지의 거리 > 직전 노드까지의 거리 + 에지 크기 이면목표 노드까지의 거리 = 직전 노드까지의 거리 +

출처 : 구슬 탈출 2 풀이 방법 : 모든 경우의 수 구하기 순서 10번의 시행 중 각 시행 당 4가지 경우의 수 구하기 (4^10) ㅠ 각 경우의 수 마다 성공할 경우 몇번째 시행인지 append & break 최솟값 출력 소감 푸는데 굉

출처 : 테트로미노풀이 방법 : 각 인덱스 별로 가능한 모양 모두 가져옴구현 방법각 조각 별 함수 만듦함수 안에 대칭 회전한 모양에 대해 합을 구해서 addmax 함수 사용소감베스트인지는 모르겠음다른 문제보다는 쉬웠다

출처 : 로봇청소기풀이 방법구현 안 된 함수 미리 호출하는 방식으로 수도 코드 작성이후 구현소감계속 구현에 실패해서 2번이나 처음부터 다시 짰다새로 시도한 풀이 방법이 좋은 것 같다

출처 : 연구소풀이방법 : 완전탐색 / DFS / 재귀순서board에서 값이 0인 좌표 중 3개 선택 (Combinations)각 조합마다 2와 속해 있는 구역을 2로 채움 (DFS)0 개수를 카운트최댓값 출력소감 : 수월했다

출처 : 적록색약알고리즘 : 재귀, DFS풀이각 좌표를 순회아직 check가 안 됐으면서 인접 좌표와 값이 같으면 check소감 : 풀이 자체는 쉬웠는데 코딩하는데 시간이 좀 걸렸다

출처 : 다리만들기풀이방법DFS로 섬의 테두리 좌표를 집합에 저장 (이후 리스트에 append)이중 for문으로 섬 별 최소 거리 구하기최소 거리의 최솟값 출력소감pypy 정답 ㅠ풀이가 다른 문제에 비해서는 직관적으로 떠올랐다

출처 : https://www.acmicpc.net/problem/16236알고리즘 : DFS, 재귀DFS 구현 방법현재 좌표에서 경로 길이 update26일 경우 종료상, 하, 좌, 우로 재귀visited = True, 재귀, visited = Falsevi

출처 : https://www.acmicpc.net/problem/14500알고리즘 : BFS풀이큐를 사용해 BFS 구현거리를 저장하는 배열에 벽을 (부수고 도달한 거리, 부수지 않고 도달한 거리)를 모두 저장\-1로 초기화 (도달 X)마지막 좌표의 두 거리

출처 : https://www.acmicpc.net/problem/1937알고리즘 : DP풀이1 (top-down)이미 방문하지 않은 모든 좌표를 순회하면서상하좌우의 최대 거리(재귀)+1 vs 현재 좌표의 최대 거리큰 값을 현재 좌표의 최대 거리에 저장풀이2

출처 : https://www.acmicpc.net/problem/5052알고리즘 : 정렬풀이방법문자열 정렬i, i+1 번째 값들을 비교i+1 startswith i 이면 NO, 아니면 YES소감알고리즘 분류가 정렬에 들어가있어서 아이디어가 떠오를 수 밖에 없

출처 : https://www.acmicpc.net/problem/2473알고리즘 : 정렬, 투 포인터풀이n = 5000 → O(n^2) 까지 가능 (파이썬)정렬각 원소 순회 → O(n)현재 원소를 제외한 나머지 배열에 대해 투 포인터 알고리즘을 통해 절댓값의

출처 : https://www.acmicpc.net/problem/2212설명 : 모든 센서를 k개의 구간으로 나누는 것과 동일풀이센서 리스트 정렬모든 센서들 간의 거리 set모든 센서들 간의 거리 정렬k-1번 pop참고 : https://journe

출처 : https://www.acmicpc.net/problem/10800풀이오름차순 정렬자신보다 작은 총 사이즈 누적, 컬러 별 사이즈 누적총 사이즈 - 컬러 누적소감아이디어는 생각이 났는데 구현이 어려워 검색 ㅜ

출처 : \[백준 1756] 피자 굽기알고리즘 : 이진 탐색풀이정렬 (https://n-square.tistory.com/21)다운로드이진 탐색이진 탐색 구현 방법재귀 함수middle 값에 도우가 들어가고 middle+1에 들어가지 않을 때 return소감O(

출처 : https://www.acmicpc.net/problem/1939알고리즘 : 이진 탐색, 너비 우선 순회풀이set 에지 연결 리스트BFS in 이진 탐색이진 탐색 구현mid = (low + high) // 2 mid 이상인 cost로 출발지부터 도착지

출처 : https://www.acmicpc.net/problem/8983풀이정렬전체 사대보다 왼쪽에 있는 동물 잡기전체 사대 사이에 있는 동물 잡기전체 사대 오른쪽에 있는 동물 잡기소감이진 탐색은 아니지만 데크로 어찌어찌 풀었다O(NlogN) + O(N+M)

출처 : https://www.acmicpc.net/problem/3020알고리즘 : 이분탐색풀이바닥의 장애물은 그대로, 천장의 장애물은 (높이-길이)로 입력받는다가능한 모든 높이에 대해 개똥벌레가 만나게 되는 장애물 개수를 계산한다최댓값과 최댓값의 개수를 구

출처 : https://www.acmicpc.net/problem/2352알고리즘 : LIS, DP, 이진탐색, lower_boundDP만 이용한 풀이 : O(N^2), pypy3 통과모든 수를 순회length_list에 각 인덱스를 마지막으로 하는 촤장 거리

출처 : https://www.acmicpc.net/problem/9251알고리즘 : DP, LCS풀이현재 인덱스까지의 최장 공통 길이를 저장하는 2차원 리스트 setpadding을 0으로 준다각 인덱스를 순회문자열1i == 문자열2j 이면 최장 길이i-1+

출처 : https://www.acmicpc.net/problem/14002알고리즘 : LIS, DP, 이분탐색, lower bound풀이1수열 리스트를 돌면서 이전 원소들을 검사현재 원소보다 작으면서 현재 위치까지의 길이 < 이전 위치까지의 길이+1 이

출처 : https://www.acmicpc.net/problem/11054알고리즘 : DP, LIS풀이모든 수열을 돌면서현재 원소가 기준 값일 때 증가하는 최장 길이를 구한다감소하는 최장 길이는 reversed로 똑같이 구현소감처음에 보고 엄청 막막했다가 L

출처 : https://www.acmicpc.net/problem/2665문제 : 백준 2665 미로만들기알고리즘 : 그래프, BFS풀이시작 위치에서 BFS를 통해 인접한 벽의 위치를 저장벽의 위치들을 시작 위치로 해서 BFS 반복image카운트 +1목적지 만

출처 : https://www.acmicpc.net/problem/1613문제 : 백준 1613번 역사틀린 풀이 : 위상 정렬, DFS각 노드를 정렬 (위상 정렬)연결되지 않은 노드 분리 (DFS)연결된 노드일 경우 정렬된 리스트에서 인덱스 비교하여 1 또는

문제 : 백준 1865번 웜홀틀린 풀이 : 플로이드-와샬 알고리즘틀린 이유 : 음수 사이클?맞은 풀이 : 벨만-포드 알고리즘설명모든 노드에 대해 거리를 계산할 필요 없음음수 사이클이 존재하면 무조건 가능풀이연결리스트 set1번에서 출발한다고 가정모든 에지를 돌면서 re

출처 : https://www.acmicpc.net/problem/1092 풀이 크레인 리스트, 박스 리스트 내림차순 정렬 모든 크레인에 대해 이동 가능한 무게의 박스 각각 저장 모든 크레인을 돌면서 이동 가능한 무게의 박스 중아직 이동하지 않은

https://www.acmicpc.net/problem/10742차원 배열을 Z모양으로 탐색할 때 주어진 (r,c) 좌표가 몇 번째로 탐색하는지 구하는 문제첫 좌표의 인덱스와 마지막 좌표의 인덱스를 가지고 재귀적으로 2차원 배열에 모든 순서를 저장하려 했으나

https://www.acmicpc.net/problem/16234인접한 좌표 간 인구가 일정 범위 안에 있는 것들끼리 평균 값으로 인구 이동이동 횟수 출력DFS로 연합마다 번호를 매김각 연합에 해당하는 값을 평균 값으로 갱신연합이 생기지 않을 때까지 반복알고

https://www.acmicpc.net/problem/17135적들이 성벽으로 한 칸씩 내려옴궁수들이 적들을 쏨궁수 3명를 배치하여 잡을 수 있는 적 수의 최댓값 구하기combinations로 배치할 수 있는 모든 경우의 수를 찾는다모든 경우에 대해BFS로

https://www.acmicpc.net/problem/1463주어진 N을 세 가지 연산으로 1로 만들 때 연산 횟수의 최솟값 구하기연산1 : 3으로 나누어 떨어질 때 나누기 3연산2 : 2로 나누어 떨어질 때 나누기 2연산3 : 빼기 1작아질수록 좋을 것

https://www.acmicpc.net/problem/2933맵의 양 옆에서 번갈아가며 특정 높이에서 막대기를 던진다막대기에 맞은 미네랄은 떠있을 경우 떨어진다모든 막대기를 던진 후 맵을 출력특정 높이에서 만나는 미네랄 구하기있을 경우 상, 하, 좌, 우로

https://www.acmicpc.net/problem/17070파이프를 밀어서 끝으로 옮긴다파이프의 방향에 따라 옮길 수 있는 위치, 모양이 정해져 있다경우의 수 출력풀이어떤 한 좌표로 갈 수 있는 경우는 총 3가지이다그런데 각 모양마다 이전에 어떤 모양이

https://www.acmicpc.net/problem/16201번 포켓몬부터 N번 포켓몬까지 이름이 주어진다.이후에 번호가 들어오면 이름을 출력이름이 들어오면 번호가 출력자료 구조를 아는지에 대한 문제같다리스트와 딕셔너리를 각각 만든다리스트에서는 숫자를 인

https://www.acmicpc.net/problem/2573board에 좌표의 빙산의 높이가 주어진다일 년에 각 좌표마다 바다(0)와 인접한 수만큼 줄어든다.처음 한 덩어리였던 빙산이 두 덩어리가 되는 것은 몇 년 후인지 출력각 좌표를 돌면서not vis

https://www.acmicpc.net/problem/4179board에 지훈이의 위치 1개와 불의 위치 ?개가 주어진다불은 인접한 빈 칸으로 한 칸씩 번진다 지훈이도 한 칸씩 움직인다지훈이가 탈출할 수 있으면 최소 시간 출력탈출할 수 없으면 IMPOS

https://www.acmicpc.net/problem/1697n, k가 주어짐\+1, -1, \*2로 n에서 k까지 도달하는 최소 연산 횟수 출력n에서 시작해 BFS로 k까지 탐색n, k의 범위가 0~100000이라 범위를 리스트 길이를 0~200000으로

https://www.acmicpc.net/problem/20561~N 번 작업마다 걸리는 시간, 선행해야 하는 작업이 주어진다선행해야 하는 작업이 없는 작업들끼리는 동시에 작업이 가능하다모든 작업을 끝내는데 걸리는 시간 출력1번 작업부터 돌면서현재 작업까지

https://www.acmicpc.net/problem/2630한 변의 길이가 2\*\*N인 정사각형이 있다모두 0이거나 1이면 카운트아니면 1/4로 잘라 반복카운트 0, 카운트 1 각각 출력재귀 함수 구현현재 범위에 대해 체크모두 1이거나 모두 2일 경우

https://www.acmicpc.net/problem/7576board에 썩은 토마토 위치가 주어진다인접해있을 경우 하루마다 주변 토마토가 썩는다비어있는 칸이 있다모두 썩지 않으면 -1모두 썩으면 최대 일 수 출력BFS로 거리에 따라 탐색마지막에 남은 0이

https://www.acmicpc.net/problem/7662I, N이 주어지면 N 삽입D, 1이 주어지면 최댓값 삭제D, -1이 주어지면 최솟값 삭제연산 후 최댓값, 최솟값 출력heapq로 최대힙, 최소힙을 만든다I, N일 때양쪽에 모두 삽입dict에 c

https://www.acmicpc.net/problem/1717초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다0, a, b 일 때, a가 속한 집합과 b가 속한 집합을 합한다1, a, b 일 때, a가 속한 집합과 b가

https://www.acmicpc.net/problem/1647마을에 집들이 있다집들을 연결하는 길들이 있다마을을 두 개로 분할하려 한다그리고 마을 안에서도 유지비를 최소로 하는 길만 남기고 길을 없애려 한다이 때 총 유지비 출력유지비에 대해 오름차순 정렬두

https://www.acmicpc.net/problem/16562친구에게 돈을 주면 친구가 되어준다친구의 친구는 친구다모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용 출력모든 노드를 돌면서 한 클러스터의 최소 비용을 구한다클러스터 별 비용

https://www.acmicpc.net/problem/1005건물을 짓는 순서가 주어진다건물을 짓는 시간이 주어진다특정 건물을 짓는데 걸리는 최소 시간 출력현재 건물을 짓는데 걸리는 최소 시간현재 건물을 짓는데 반드시 건설되어야 하는 건물들 중 최대 시간

https://www.acmicpc.net/problem/17472모든 섬을 다리로 연결다리는 가로, 세로로 직선만 가능다리 길이 2 이상다리 길이 합의 최솟값 출력연결이 불가능하면 -1 출력섬에 번호를 매김BFS다리 리스트를 구함바다와 인접한 부분에서 다른

[백준] 9470번 Strahler 순서

https://www.acmicpc.net/problem/94652행 N열 보드가 주어진다스티커마다 점수가 주어진다한 스티커를 선택하면 인접한 스티커는 선택할 수 없다점수의 최댓값 출력dp0, dp1, dp0, ... 순서로 돌면서 점수 계산어차피 위, 아래는

https://www.acmicpc.net/problem/11660board 가 주어진다특정 좌표 y1, x2 부터 y2, x2 까지의 합을 출력처음에 그때 그때 합을 구해봤지만 당연하게도 시간초과DP로 (0, 0)부터 특정 좌표까지의 합을 모두 저장범위가 주

https://www.acmicpc.net/problem/9663퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력행별로 백트래킹 수행열을 돌면서 해당 열이 가능한 열인지 체크가능할 경우 check = TrueDFScheck = Falsej열에 퀸이 왔을

[백준] 2632번 피자판매

문제링크 / 문제설명 / 풀이 / 느낀점 / 코드

[백준] 1918번 후위 표기식

[백준] 1916번 최소비용 구하기

[백준] 5972번 택배 배송

[백준] 5021번 왕위 계승

[백준] 3190번 뱀

[백준] 14499번 주사위 굴리기

[백준] 14890번 경사로

[백준] 14891번 톱니바퀴

[백준] 15683번 감시

[백준] 15685번 드래곤 커브

[백준] 15685번 드래곤 커브

[백준] 16235번 나무 재테크

[백준] 15684번 사다리 조작

[백준] 20056번 마법사 상어와 파이어볼

[백준] 15686번 치킨 배달

[백준] 17822번 원판 돌리기

[백준] 17144번 미세먼지 안녕!

[백준] 17140번 이차원 배열과 연산

[백준] 19237번 어른 상어

[백준] 17143번 낚시왕

[백준] 20061번 모노미노도미노2

[백준] 16236번 아기 상어

[백준] 1759번 암호 만들기

[백준] 21608번 상어 초등학교

[백준] 9935번 문자열 폭발

[백준] 2096번 백준

[백준] 21609번 상어 중학교

[백준] 1253번 좋다

https://www.acmicpc.net/problem/1068트리가 주어짐노드 하나를 삭제했을 때 리프 노드의 개수 출력입력이 부모 리스트로 주어져서인접 리스트를 만들어주고BFS를 사용했다

https://www.acmicpc.net/problem/19238택시 승객 태우고 데려다 주고 반복한 칸에 1씩 연료 소모데려다 주면 소모한 연료 \* 2 충전모두 데려다 줄 수 있으면 남은 연료 출력아니면 -1 출력BFS로 가장 가까운 승객 찾기, 데려다

https://www.acmicpc.net/problem/1062문자열 리스트가 주어짐antatica를 무조건 포함소문자 알파벳 중에서 k개를 선택해서 가르침단어를 온전히 읽을 수 있는 개수의 최대값 출력antic를 미리 선택나머지 중에서 k-5개 선택선택한

https://www.acmicpc.net/problem/5430두가지 함수 리스트가 주어짐reversepopleft숫자 리스트가 주어짐반영그대로 구현하니 시간 초과가 난다함수는 무조건 한번씩 체크해야해서 함수때문은 아니고그때그때 reverse하면 N번을 더

https://www.acmicpc.net/problem/5670타이핑 할 때 자동으로 입력 가능한 글자가 있으면 자동으로 입력해주는 기능 개발사전 단어 리스트가 주어짐평균 타이핑 횟수 출력트라이 구현Node 클래스 구현 후 root 노드에 계속해서 삽입BFS

https://www.acmicpc.net/problem/11000수업 시작 시간, 종료 시간 리스트가 주어짐최소 강의실 개수 출력우선순위 큐에 강의실의 마지막 수업 종료 시간을 저장한다수업 시작 시간의 오름차순으로 가능한 강의실이 있는지 검사한다해당 시작 시

https://www.acmicpc.net/problem/1261board가 주어짐벽을 부수며 (n,m)으로 갈 때, 벽을 부순 횟수의 최솟값 출력bfs 반복하면서 벽 부수기노드 개수 N일 때, O(N^2) -> 10000^2

https://www.acmicpc.net/problem/109422000개 숫자가 주어짐100만개 start, end 인덱스가 주어짐start ~ end 가 팰린드롬이면 1, 아니면 0 출력dp 배열을 놓는다dps : s~e가 팰린드롬이면 1, 아니면 0양

문제 링크 https://www.acmicpc.net/problem/2042 문제 설명 숫자 리스트 주어짐 (100만개) 수정, 구간 합 구하기 반복 (2만번) 풀이 세그먼트 트리 init 구현 리프가 아닐때 왼쪽 노드 생성 리프가 아닐때 오른쪽 노드 생성

https://www.acmicpc.net/problem/5052주어진 전화번호 목록이 일관성이 있으면 YES없으면 NO 출력문자열 길이로 정렬 후 트라이 구현

https://www.acmicpc.net/problem/2638board 주어짐1초마다 외부 공기와 2칸 이상 인접한 칸 사라짐외부 공기 기준 BFS 반복1초마다 2칸 이상 닿는 좌표 삭제

https://www.acmicpc.net/problem/3649투포인터테스트케이스 여러개 처리를 안해줘서 좀 헤맸다

https://www.acmicpc.net/problem/20164

https://www.acmicpc.net/problem/2671체크해야할 패턴을 함수별로 나눠서 재귀겁먹었는데 다행히 풀었다

https://www.acmicpc.net/problem/10868

https://www.acmicpc.net/problem/1275

https://www.acmicpc.net/problem/11505

https://www.acmicpc.net/problem/17425시간 초과

https://www.acmicpc.net/problem/13459