알고리즘
-
[백준] 1697번 숨바꼭질알고리즘/백준 2025. 6. 13. 18:13
문제링크https://www.acmicpc.net/problem/1697 해설seconds 배열 요소가 갱신됐으면 새로운 값으로 갱신되면 안 된다. 새로 갱신되는 값은 기존 값보다 무조건 클 것이기 때문이다. 우리는 최소 값을 구해야 하니까 방문한 요소는 건너뛰어 값을 보호하고 비효율도 예방한다. 그전에는 이런 최소 값을 구할 때 queue를 pair로 선언해 위치값과 거리 값을 같이 관리하는는 걸 선호했지만 이번에는 (x, y) 형태의 좌표에 관한 문제가 아니라 값을 갱신해나가면서 최소 값을 찾는 것이기 때문에 별도의 visited 배열을 두지 않고 하나의 정수형 배열에서 방문/미방문을 구분할 수 있다. 전체 코드#include #include #include using namespace std;in..
-
[백준] 7569번 토마토알고리즘/백준 2025. 6. 13. 12:37
문제 링크https://www.acmicpc.net/problem/7569 해설3차원 배열로 풀어도 되고 2차원 배열로 풀어도 된다. 나는 2차원 배열로 풀었다. 2차원 배열로 풀 때는 행 인덱스 처리를 잘해줘야 하는 케이스는 행이 바뀔 때 층이 바뀌는 때다. 3차원 배열로는 안 풀어봤지만 층 인덱스가 별도로 있으니 실수할 가능성이 적지만 2차원으로 할 때는 층이 바뀌는 경우를 그냥 지나칠 수 있다(내 얘기). 인접 토마토를 검사에서 가로 세로를 검사할 때 같은 층인 경우에만 탐색을 해야 한다. 코드가 최적화 여지가 있어 보이긴 한데..일단 넘어간다. while (q.empty() == false) { auto [pos, day] = q.front(); auto [n,..
-
[백준] 2644번 촌수 계산알고리즘/백준 2025. 6. 7. 16:20
문제 링크https://www.acmicpc.net/problem/2644 내 코드가 대단히 메모리를 적게 먹거나 코드 길이가 짧은 편에 속하지는 않는다. 그동안 제출된 현황의 코드를 보니까 메모리와 코드 길이 기준으로 대충 상위 30%에는 속한다. 가독성은 더 좋다고 생각한다. 내가 작성해서가 아니라 그냥 평범한 로직이라서 그렇다. #include #include #include using namespace std;int N, M;int p1, p2;vector parents;bool visited[101];queue> q;int main(){ cin >> N; cin >> p1 >> p2; cin >> M; parents.resize(N + 1); for (int i = 0..
-
[백준] 2667번 단지번호 붙이기알고리즘/백준 2025. 6. 1. 02:34
문제 링크https://www.acmicpc.net/problem/2667 해설반복문 돌면서 조건이 맞을 때 dfs() 함수를 호출한다. 일단 호출이 되면 인접한 집을 전부 돌고 나서 처음 호출한 곳으로 리턴한다. dfs() 호출이 끝나면 카운트를 우선 순위 큐(최소 힙)에 저장하고 0으로 초기화하고 이어서 반복문이 수행되도록 한다. 당연한 소리지만 bfs()로도 풀리는 문제다. 메모리 효율이나 속도는 bfs()가 더 좋다.#include #include #include using namespace std;priority_queue, greater> pq;bool map[25 + 2][25 + 2];bool visited[25 + 2][25 + 2];int N;int adj_dir_row[] = { 1,..
-
[백준] 2178번 미로 탐색알고리즘/백준 2025. 5. 30. 23:28
문제 링크https://www.acmicpc.net/problem/2178 로직이 분명히 문제가 없는데 틀렸다고 나오는 게 이해가 안 됐다. 알고 보니 경계 문제였다. 경계는 늘 문제구만. 거리 계산하는 부분을 별도로 배열로 관리하면 채점 상에 나오는 메모리가 (40kb) 정도 절약되지만, 큐를 통해 한 번에 관리하는 게 나는 더 편하다. 처음에는 DFS로 풀어보려다 복잡해질 것 같아 BFS로 거리 계산을 해보려고 하니까 금방 됐다. 경계만 아니었다면.. #include #include using namespace std;queue, int>> q;int N, M;int map[102][102];bool visited[102][102];int dist[102][102];int dir_n[] = { 1, ..
-
[백준] 1260번 DFS와 BFS알고리즘/백준 2025. 5. 30. 19:46
아주 아주 오랜만에 풀다 보니까 사소한 실수들이 있었다. 익숙해지는 수밖에 없겠지. 문제 조건 중에 방문할 수 있는 정점이 여러 개라면 정점 번호가 작은 것부터 순회하라고 했다. 어차피 인덱스 번호 = 정점 번호라서 반복문 돌릴 때 1번부터 하면 된다.#include #include #include using namespace std;void dfs(int start);void bfs();queue q;bool map[1001][1001] = { false };bool dfs_visited[1001] = { false };bool bfs_visited[1001] = { false };int N, M, start;int main(){ cin >> N >> M >> start; for (int i = 0; ..
-
공원 산책알고리즘/프로그래머스 2023. 5. 11. 10:38
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/172928 해설 이차원 배열로 공원 맵을 만들면 편하게 작업할 수 있다. 공원의 길이가 가로, 세로 각각 50이기 때문에 O(N^2)의 시간복잡도를 가져도 괜찮다. 코드 class Solution { public int[] solution(String[] park, String[] routes) { int[] startPoint = new int[2]; int height = park.length; int width = park[0].length(); char[][] parkMap = new char[park.length][park[0].length()]; for (int i = 0; i ..
-
추억 점수알고리즘/프로그래머스 2023. 5. 11. 10:32
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/176963 해설 길이가 많이 길지 않으므로 O(N^2)로 편하게 풀면 된다 코드 import java.util.*; class Solution { public int[] solution(String[] name, int[] yearning, String[][] photo) { Map nameYearingMap = new HashMap(); int size = name.length; for (int i = 0; i < size; ++i) { nameYearingMap.put(name[i], yearning[i]); } List answer = new ArrayList(); for (int i..