전체 글

16946 - 벽 부수고 이동하기 4https://www.acmicpc.net/problem/16946문제NxM의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 벽이 있는 곳을 나타냄한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 하고 두 칸이 변을 공유할 때 인접하다고 함- 벽을 부수고 이동할 수 있는 곳으로 변경- 그 위치에서 이동할 수 있는 칸의 개수 셈한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸입력: 첫째 줄에 N, M (1 출력: 맵의 형태로 정답 출력/ 원래 빈 칸인 곳은 0, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지풀이벽마다 BFS -> 시간 초과 => 0 영역을 미리 그룹화`int[][] group`: 각 칸이 속한 그룹 번호`in..

2342 - Dance Dance Revolutionhttps://www.acmicpc.net/problem/2342문제DDR은 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임발판은 하나의 중점(0)을 기준으로 위(1), 아래(3), 왼쪽(2), 오른쪽(4)으로 연결되어 있음처음에 게이머는 두 발을 중앙에 모으고 있음(0 위치)게임이 시작되면, 지시에 따라 왼쪽/오른쪽으로 발을 움직이는데 두 발이 동시에 움직임 X/ 두 발이 같은 지점에 있는 것 X ex. 한 발 1, 다른 한 발 3/ 3을 연속으로 눌러야 함 -> 3의 위치에 있는 발로 반복해서 눌러야 함발이 움직이는 위치에 따라 드는 힘이 다름중앙 -> 다른 지점: 2/ 다른 지점 -> 인접한 지점: 3(L -> 위/아래) / 반대..

택배상자https://school.programmers.co.kr/learn/courses/30/lessons/131704풀이`Deque sub = new ArrayDeque()`: 보조 컨테이너`idx`: 다음에 반드시 실어야 하는 `order` 위치`box`: 컨베이어에서 다음에 나올 번호 컨베이어 벨트에서 꺼낼 상자가 남아 있는 동안 보조 컨테이너 X`order[idx] == box`: 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서보조 컨테이너 O지금 상자 X + 현재 스택 top O => 지금 안꺼내면 다음에 X -> 바로 꺼내기지금 상자 X + 현재 스택 top X => 보관 (일단 저장)while (box `!sub.isEmpty()`: 컨베이어 벨트 X But, 보조 ..

2146 - 다리 만들기https://www.acmicpc.net/problem/2146 문제한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 다리를 가장 짧게 하여 돈을 아끼려고 함NxN 크기의 이차원 평면상에 존재하는 이 나라는 여러 섬으로 이뤄져 있음 섬: 동서남북으로 육지가 붙어있는 덩어리가장 짧은 다리: 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리입력첫 줄: 지도의 크기 N (1 다음 N줄: N개의 숫자 빈칸을 사이에 두고 주어짐 (0: 바다, 1: 육지)출력: 가장 짧은 다리의 길이풀이섬 라벨링현재 `map`에는 0: 바다, 1: 육지 -> 어느 섬에서 시작했는지 알 수 없음=> 각 섬을 서로 다른 번호로 변경`map[i][j] == 1 && !visited[i][j]`: 섬이고..

1. 올해 가장 좋았던 카페스티키플로어집 앞이라 마음 편하게 가기 좋고 런치 세트도 너무 맛있고사장님 커플도 친절하고 공간도 예쁨 2. 올해의 best 소비나고야 갈 때 산 산드로 선글라스?근데 지금 시점에 다른 선글라스 더 사고 싶음 화장품은 퓌 쿠션(리뉴얼 전)이 마음에 들었음 3. 올해의 worst 소비딱히 없다고 생각했는데 추천으로는 무인양품 푸딩너무너무 맛 없음 4. 가장 자주 들은 올해의 노래Penthouse (펜트하우스) 노래 많이 들음 올해 좋아했던 노래는 Kimagure Romatic - 나연THIS IS FOR - TWICE 5. 올해 가장 인상 깊었던 영화 주토피아2늘 영화 그냥 그런데 말랑말랑 아주 귀여웠음6. 올해 가장 인상 깊었던 책 혹은 구절 『우리가 열 번을 나고 죽을 때』..

알고리즘 선택 전에 가장 먼저 던질 질문 3가지그래프 문제인가?정점, 간선, 연결, 이동, 경로가 등장하는가최소 / 최대 / 최적화 문제인가?최소 비용, 최단 거리, 최대 값 같은 표현이 있는가구간 쿼리 + 값 변경이 있는가?→ 범위 + 빠른 응답 + 업데이트가 필요한가DFS / BFSKey Words연결되어 있는도달 가능한사이클이 있는지모든 정점을 방문그래프, 트리DFS (Depth First Search)한 경로를 끝까지 파고들었다가 되돌아오면서 처리해야 할 때즉, 탐색 그 자체가 목적일 때void dfs(int v) { visited[v] = true; for (int next : graph[v]) { if (!visited[next]) { dfs(next..