728x90 전체 글249 백트래킹(Backtracking) 백트래킹(Backtracking)은 답을 찾아가는 도중, 정답이 아닐거 같으면 뒤로 돌아가서 다시 답을 찾아가는 과정을 통해 해답을 구하는 방식의 알고리즘입니다. DFS을 알고 있다면, 이해하기 쉽습니다. DFS : 1번 방문한 곳은 다시 방문하지 못한다. 백트래킹 : 1군데를 여러번 방문할 수 있다. ex) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IO.. 2023. 1. 25. SPFA(Shortest Path First Algorithm) SPFA(Shortest Path First Algorithm) 알고리즘은 "음수 간선을 포함한 데이크스트라 알고리즘"으로 이해하면 편한 "벨만 포드 알고리즘"을 개선한 알고리즘 입니다. BFS - 데이크스트라 - 벨만포드(SPFA)로 학습을 진행하시면 편합니다. 벨만 포드는 "모든 간선에 대해 업데이트를 진행"하지만, SPFA는 "바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행"합니다. 벨만포드를 학습하지 않고, SPFA를 학습하셔도 태그로 벨만포드가 들어간 문제를 대부분 해결하실 수 있습니다. ex) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주.. 2023. 1. 24. Dijkstra - 데이크스트라(다익스트라) 데이크스트라(Dijkstra)는 BFS 알고리즘을 알고 있다면 조금 더 쉽게 이해할 수 있다. 시작 지점 부터 가고자하는 도착지점까지 최소한의 시간으로 도착할 수 있는 거리를 구하는 알고리즘이다. ex)https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 예제 입력은 1번에서 출발하여 5번까지 도착하는데 걸리는 최소 시간을 구하는 문제입니다. 1 -> 4 -> 5을 이동하게 된다면 1 + 3 = 4의 시간이 걸리게 .. 2023. 1. 22. BFS - 너비 우선 탐색 / DFS - 깊이 우선 탐색 너비 우선 탐색(Breadth First Search) / DFS(Depth First Search)은 시작지점부터 갈 수 있는 지점들을 들리면서, 더이상 갈 곳이 없을때까지 반복한 후 종료한다. ex) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 해당 문제는 이런 모양의 간선과 노드들로 이루어져 있습니다. 1번 컴퓨터에 바이러스가 걸리게 된다면, 1과 2, 3, 5, 6 총 4개의 컴퓨터가 1번 컴퓨터에 의해 바이러스에 감염되면서, 5개의 컴퓨.. 2023. 1. 22. 백준 랭킹 1페이지 달성! 2023 / 01 / 03 2022년 목표였으나 미뤄져 2023년 목표 중 하나인 랭킹 1페이지를 달성했습니다. 2513문제로 100등을 달성하였습니다. 오늘 하루동안 26문제를 해결하였고, https://www.acmicpc.net/problem/25822 요기 나오는 24문제의 기준점을 넘어버렸습니다! 25822번: 2000문제 푼 임스 이 문제는 문제 출제를 위해 꾸준히 문제를 풀어 2000문제 풀이를 달성한 임스가 처음으로 출제한 문제입니다. 임스는 문제 출제를 위해 매일 0 ~ 24문제를 풀었습니다. 임스가 스트릭을 끊기지 않 www.acmicpc.net solved.ac 현 상황 앞으로 랭킹을 빼앗기지 않는 이상 1문제씩만 풀면서 스트릭을 유지할거 같습니다. 2023. 1. 3. 2022년 회고 / 2023년 목표 2022년을 돌아보면서, 다가올 2023년의 목표를 정리해보기 위해 적어보았다. 2022년 회고 1. 졸업을 했다. 2022년 2월 다니던 대학교 컴퓨터공학과를 졸업했다. 마지막 프로젝트는 Spring boot + React.js로 게시판 웹사이트를 만들어 보았다. 이때부터 취준생 생활 시작이다.. 2. 알고리즘 2022년 1월 1일 기준 1467solve에서 2455 solve로 1년동안 988문제 대략 하루에 평균 2.7문제를 풀은 셈이다. 백준을 통해 첫 대회를 개최해 보았다. (https://lms0806.tistory.com/131) 2000문제를 풀어, 이를 기념하기 위해 백준을 통해 대회가 아닌 개인 문제를 개최해 보았다. (https://www.acmicpc.net/problem/25822.. 2022. 12. 31. [백준] 25430번 : 다이제스타 https://www.acmicpc.net/problem/25430 25430번: 다이제스타 첫째 줄에 커널의 개수 $N$과 연결통로의 개수 $M$가 주어진다. $(1 ≤ N ≤ 50,000, 1 ≤ M ≤ 100,000)$ 두번째 줄부터 $M$개의 줄에 연결통로를 통해 연결되어 있는 두 커널과 연결통로의 길이가 주어진 www.acmicpc.net 해당 문제는 조건이 여러가지가 있습니다. 1. 양방향 연결통로 2. 이동방법 중 총 이동 거리가 가장 짧은 경로를 이용한다. 3. 항상 전에 이동했던 연결통로보다 더 길이가 긴 연결통로를 이용해야만 한다. 4. 한번도 연결통로를 이용한 적이 없다면, 아무 연결통로나 이용 할 수 있다. Node 클래스를 만들어 현재 위치, 총 소요 거리, 이전 거리를 저장한다... 2022. 12. 4. 구름 알고리즘 챌린지 후기 구름에서 "알고리즘 먼데이 챌린지"를 진행하였습니다. 알고리즘 학습 및 개발직군 학습을 하면서 취업 준비하는 알고리즘 톡방을 통해 소식을 접하였고, 10/3일 알고리즘 챌린지가 시작하는 날부터 매주 꾸준히 문제풀이를 진행하였습니다. 주차별 난이도는 이렇게 분배되었고(맞는진 모르겠음), 매주 4문제가 나왔습니다. 그 중 1~2번은 알고리즘을 어느정도 학습을 한 상태라면 풀 수 있었고, 3번은 조금 생각해야 되는 문제, 4번은 심화 알고리즘이 나왔던 걸로 기억합니다.(4번은 많이 풀지 못함...) 문제들 중, 몇몇 문제들이 "필요 없는 설명이 들어가 있음" and "이상한 방식으로 해야지만 풀림" and "데이터가 부족하여 시초가 나와야 하는데 맞음" 등 문제가 있었지만, 저는 항상 첫날에 풀어가지고 다른 .. 2022. 12. 2. [백준] 26068번 : 치킨댄스를 추는 곰곰이를 본 임스 2 https://www.acmicpc.net/problem/26068 26068번: 치킨댄스를 추는 곰곰이를 본 임스 2 첫 번째 줄에는 임스가 받은 기프티콘의 개수 정수 $N$이 주어진다. ($1 \le N \le 1\,000$) 두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 기프티콘의 남은 유효기간 $x_i$가 D-xi 와 같은 형식으로 주어진다. ( www.acmicpc.net 처음 문제를 출제하였던 "치킨댄스를 추는 곰곰이를 본 임스"의 스토리를 이어가는 문제입니다. https://www.acmicpc.net/problem/25191 25191번: 치킨댄스를 추는 곰곰이를 본 임스 콜라 $4$개, 맥주 $2$개로 치킨을 $4$마리까지 먹을 수 있지만, 치킨집에 치킨이 $3$마리밖에 없으므로 임스도.. 2022. 12. 1. 이전 1 ··· 9 10 11 12 13 14 15 ··· 28 다음 728x90
