백준

문제 링크 ▶︎ 백준 스도쿠 2580 문제 전략 이 문제는 백트래킹 문제이다. 스도쿠의 전략에 맞게 ① 해당 행, ② 해당 열, ③ 해당 3X3 정사각형 을 검사하는 함수가 있어야 한다. 빈칸은 0으로 채워두고, DFS 로 빈칸(0) 을 탐색 시작한다. 빈칸을 찾

문제 링크 ▶︎ 백준 벽 부수고 이동하기 2206이 문제는 BFS 문제이다.graph를 탐색하면서 1번은 벽을 깨고 이동할 수 있다는 것을 보고 visit를 3차원으로 만드는 것이 중요하다.즉, 기존의 2차원 visit을 2개로 겹쳐두고 첫 visit에서 bfs로 진행

문제 링크 ▶︎ 백준 내리막길 1520이 문제는 DFS로 푼 문제이다.(0,0)에서 출발하여 (n-1,m-1)까지 이동하는 과정에서 조건을 만족하면 재귀함수를 호출하는 구조이다.dfs(n-1,m-1) 의 값은 1을 리턴하며,재귀함수 진행이 완료되면 이전 호출로 돌아오며

문제 링크 ▶︎ 백준 특정한 최단 경로 1504이 문제는 다익스트라 알고리즘으로 푼 문제이다.노드는 양방향으로 딕셔너리에 담았다.다익스트라 함수는 start 에서 출발하여 n까지 최단경로로 가는 visit을 리턴한다.힙 배열을 통해 현재까지의 경로 + 다음 노드까지의

문제 링크 ▶︎ 백준 빙산 2573이 문제는 DFS 로 풀고싶어서 DFS 로 풀어본 문제이다.빙산이 있는 좌표를 ice 라는 딕셔너리에 (키-좌표 밸류-1)로 저장해놓는다.ice 딕셔너리를 돌면서 dfs 함수를 수행한다.dfs 는 스택을 통해 구현했다.스택에서 pop

문제 링크 ▶︎ 백준 N과M(9) 문제 전략 이 문제는 백트래킹 문제이다. N과M 시리즈 중에는 시간 복잡도 문제로 까다로운 편이라고 생각한다. 중복된 배열을 검사하는 과정에서 brfore 이라는 변수를 선언하고, 이미 사용된 숫자인가를 검사한다. 어차피 lst 배

문제 링크 ▶︎ 백준 전깃줄이 문제는 DP 문제이다.전깃줄 data를 2차원 배열로 받은 뒤, 2차원 배열의 첫번째 인덱스를 기준으로 정렬한다.n 만큼 반복문을 돌면서 {지금 전깃줄} 과 {전의 전깃줄들} 을 비교한다.그 전까지의 전깃줄들을 검사하면서 겹치지 않는 전깃

문제 링크 ▶︎ 백준 플로이드이 문제는 최단 거리 경로 알고리즘 중 플로이드 워셜 알고리즘 문제이다.다익스트라의 경우 한 지점에서의 최단 경로를 구하는 알고리즘이지만, 플로이드 워셜 알고리즘은 모든 지점에서의 최단 경로를 구할 때 쓰는 알고리즘이다.소스 코드는 다익스트

문제 링크 ▶︎ 백준 겹치는 건 싫어<span style="background-color:이 문제는 투 포인터를 사용해야 할 것 같다.그리고 <span style="background-color:아이디어는 배열에 존재하는 aᵢ의 범위가 1 ~ 100,000

문제 링크 ▶︎ 백준 아기 상어 16236<span style="background-color:<span style="background-color:이라는 조건으로 시간제한을 생각하지 않고 아기 상어가 이동 할 수 있는 곳, 거리를 BFS로 다 찾고 나서 제

문제 링크 ▶︎ 백준 ABCDE 13023<span style="background-color:<span style="background-color:그래서 DFS 함수안에서 그걸 체크하는 로직도 넣어둬야 할 것 같다.boolean 으로 flag를 줘서 fla

문제 링크 ▶︎ 백준 구슬찾기 2617<span style="background-color:무게 순으로 따졌을 때, 절대로 중간에 오지 않는 구슬을 찾는다는 건 나보다 가벼운 구슬이 n/2개 이상있거나, 나보다 무거운 구슬이 n/2개 이상 있는 구슬을 찾는 것과

문제 링크 ▶︎ 백준 스타트 택시 19238문제를 보자마자 어떻게 풀지 막막했는데 먼저 해야할 것은 택시가 어떤 승객을 태우러 가는지에 대한 로직이 필요하다고 생각했다.그리고 승객을 태우고 나서 목적지에 가는 로직도 필요하다. 즉, 최단거리를 탐색하는 과정이 승객을 태

문제 링크 ▶︎ 빗물물이 고이기 위해서는 큰 벽과 작은 벽들, 그리고 큰 벽이 다시 감싸진 구조가 발생해야 그 곳에 물이 고일 수 있고, 큰 벽들 중에서 더 작은 벽의 크기에 맞게 물이 고인다는 사실을 구현하는 것이 중요하다고 생각했다.그래서 물이 고일 수 있는 조건을

문제 링크 ▶︎ 배열 돌리기1문제의 가장 큰 특징은 레이어 별로 회전한다는 것이다. 가장 바깥에 존재하는 레이어는 해당 레이어끼리 시계방향으로 회전하고, 그 안의 레이어도 해당 레이어끼리 회전한다.그리고 회전의 횟수만큼 반복문을 시행하기에는 최악의 경우 300 x 30

문제 링크 ▶︎ 가르침이 문제는 알파벳 중에서 어떤 k개만을 선택했을 때 최고의 선택이 되는지를 구하는 문제이기 때문에 백트래킹으로 풀려고 생각했다.시간을 조금이라도 줄이기 위해서 전체 알파벳이 아닌 문제에서 주는 알파벳을 가지고 백트래킹을 돌리면서 최선의 선택을 구하

문제 링크 ▶︎ 4와 7굉장히 간단한 문제라 4와 7이 순서대로 숫자 뒤에 추가되는 순서로 쭉 이어지면 된다. 4와 7이 구성되어있고 4 뒤에 4가 붙어서 44, 4 뒤에 7이 붙어서 47, 7 뒤에 4가 붙어서 74, 7 뒤에 7이 붙어 77, 이런식으로 진행하면 한

문제 링크 ▶︎ 로봇 청소기문제에는 이러한 조건에 따라서 로봇 청소기가 움직이는데 크게 보면 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있느냐 없느냐로 두 갈래로 나뉘고 그 다음은 각각의 오더가 있기 때문에 항상 현재 칸에서 주변 4칸 검사를 하는 것이 선행되어야

문제 링크 ▶︎ 주사위 굴리기초기에 세팅된 주사위의 위치를 저장해서 한번씩 굴릴때마다 주사위 눈이 변경되는 것을 위치에 맞게 이동시키는 것이 중요해보인다. 그리고 주사위와 좌표의 숫자에 따라서 조건이 바뀌기 때문에 해당 로직을 잘 구성해야할 것 같다.주사위 눈은 정육면

문제 링크 ▶︎ 틱택토문제에는 많은 조건이 있는데 이런 조건들을 잘 검사하는 것이 중요해보인다.우선 X를 O보다 먼저 놓기 때문에 격자에 O가 더 많은 경우는 있으면 안되고, 또한 한줄 완성에 따라서 경기가 끝나는데 만약 한줄 완성이 되지 않더라도 빈칸 없이 무승부로

문제 링크 ▶︎ 컨베이어 벨트 위의 로봇문제가 이해하기 힘들게 설명되어 있지만, 결론은 컨베이어 벨트는 1-2n까지 한칸씩 이동하는 것이고 로봇은 1-n까지만 이동하고 n에서 내린다. 그리고 로봇이 존재하는 칸은 내구도가 하나씩 감소하는 것이 중요하고 다음 칸에 로봇이

문제 링크 ▶︎ 링크텍스트문제에서 노드 사이의 간선의 cost가 음수가 존재한다고 했기 때문에 그냥 value를 우선순위큐에 넣어서 작은 cost의 간선으로 확장해나가는 것은 어렵다.그리고 "시간을 무한히 오래 전으로 되돌릴 수 있다"는 말이 있는데 이건 간선의 순환을

문제 링크 ▶︎ 트리의 지름트리가 주어지고 가중치의 합산이 가장 긴 지름을 구하면 되는데, 해당 지름은 당연히 리프노드들 간의 가중치의 합산으로 이루어진다. 이 그림에서 이해할 수 있듯이, 아무런 노드에서 출발해서 가장 먼 노드를 찾고나면 해당 노드가 끝점이 될거고,

문제 링크 ▶︎ 스도쿠이 문제는 스도쿠의 빈칸이 정확하게 몇개인지 알려주지않아서 시간복잡도를 알 수는 없지만, 완전탐색으로 풀기 위해서는 빈칸의 갯수가 n이라고 가정했을 때, 9의 n제곱만큼 돌기 때문에 완전탐색으로는 어렵다.그래서 백트래킹 + 가지치기를 해야하는데,

문제 링크 ▶︎ 거짓말처음에는 각 파티에 참여한 사람의 정보를 받은 배열을 순회하면서 진실을 아는 사람과 함께 파티에 참석한 사람을 진실을 안다고 바꿔주는 식으로 생각했는데, 더이상의 전파가 없을 때까지 반복해서 하는 작업이 구현이 더 어려울 것 같아서 bfs로 진실을

문제 링크 ▶︎ 파티이 문제에서는 도로가 단방향으로 이루어져있어서 x에서 가는 도로와 x로 들어오는 도로를 따로 구해야 x도시를 왕복하는 cost를 구할 수 있다. 즉 각 도시에서 x 도시로 가는 최소 비용과 x 도시에서 각 도시로 가는 최소 비용을 모두 구해서 각 도

문제 링크 ▶︎ 텀 프로젝트문제에서 주어지는 정수 배열에 대해서 각 index(실제로는 index+1)에 해당하는 학생이 그 밸류에 해당하는 학생을 지목해서 단방향으로 그래프가 그려진다고 생각할 수 있다. 그러면 사이클이 형성이 되면 팀이 구성되는것이고, 혼자 지목해서