* 개인 블로그에 작성한 내용을 복사해왔습니다. [Algorithm] BOJ 23354 BOJ 23354번 물통다익스트라를 사용하여 풀이하면 되는 문제입니다. 처음에는 순열을 사용하여 각 순서대로 다익스트라를 돌려 풀이하였는데, 당연히 시간 초과가 떴습니다.그래서 탈영병 인원만 velog.io BOJ 23354번 군탈체포조 23354번: 군탈체포조 군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다. 어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라 www.acmicpc.net Intro 다익스트라를 사용하여 풀이하면 되는 문제입니다. 처음에는 순열을 사용하여 각 순서대로 다익스트라를 돌려 풀이하였는데..
분류 전체보기
https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 문제 풀이 처음에는 맥도날드와 스타벅스가 없는 정점들을 순차적으로 출발점으로 두고 반복문을 사용하여 맥도날드와 스타벅스의 최단거리의 합을 각각 구했다. 하지만 이 풀이는 시간 초과라는 결과를 가져와 다른 방식으로 접근해야겠다고 생각했다. 먼저 맥도날드에 대해 모든 맥도날드 위치를 출발점으로 두고 최소힙을 사용하여 각 정점들에 대해 거리를 구했다..
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 브루트 포스 탐색을 이용하여 사전순 순열을 출력하는 과정에서, 추가로 가지치기를 통해 주어진 길이와, 오름차순일 경우에만 출력하는 문제이다. 재귀함수를 이용하여 탐색한 이후, 이전 단계로 돌아와 다시 탐색을 하는 식으로 코드를 구성하였다. 그리고 가지치기 조건은 길이가 주어진 길이일 경우, 그리고 인덱스 탐색을 통해 오름차순에 해당할 경우에 출력을 해주었다. import sys n,m=map(i..
문제 https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이 구현 + 브루트포스 알고리즘 문제이다. 문제 조건을 꼼꼼히 읽지 않아서 많이 틀렸는데 오답률이 낮은 이유가 있다.. 북동, 동, 남동, 남 방향으로 확인하면 되는데 범위를 넘어가는 경우나 6개이상 놓여 있으면 안되는 조건을 꼭 숙지해야한다 코드 #include using namespace std; int board[20][20]; // 범위 안에 있는지 확인하는 함수 bool insid..
문제 풀이 주어지는 노선이 양방향이므로 다익스트라 알고리즘을 3번 이용하여 풀었습니다. 입력받는 위치는 총 4가지 입니다. 1과 N, 필수로 들러야 하는 start와 end. 다익스트라 알고리즘을 1, N, start 에서 이용하여 각 경로로 가는 최단거리를 구합니다. 여기서 1 -> start + N -> end 와 1 -> end + N ->start 를 비교하여 더 작은 값을 얻습니다. (start -> end는 동일, 양방향) 이 값에 start -> end 의 최단거리를 더하여 답을 얻습니다. 예외 처리) start가 1과 같은 경우, end와 N이 같은 경우엔 해당 연산을 삭제합니다. 코드 import java.io.*; import java.util.*; class Main { static ..
0. Q & A - 다른 언어로 문제를 풀어도 상관이 없나요? 문제 자료에 나오는 코드가 파이썬, C++이라 C++, 파이썬 코드를 읽을 줄 아시면 상관은 없습니다. - 모의 테스트는 어떻게 진행되나요? 백준 - 그룹 - 연습 기능을 사용하여 백준 문제를 제공할 예정입니다. - 모의 테스트 예시 - 할당량은 몇 문제를 풀게 되는 것인가요? 21년도 겨울방학 활동 기준으로 코딩 테스트 준비 스터디는 일주일에 8문제를 풀었고, 알고리즘 기초 스터디는 최대 36문제(1주차), 최소 10문제(8주차), 보통 20문제 ~ 25문제를 풀었습니다. 1. 코딩 테스트 준비 스터디 대상 - 구현 문제는 어느정도 풀어서 코딩 테스트에 나오는 알고리즘 문제를 풀어보고 싶은 분들 사용 언어 - C++ - Python 3 계획..
안녕하세요! 한국항공대학교 알고리즘 학회 Koala 에서 이번 1학기에 같이 공부하실 분들을 모집합니다! 저희 학회는 프로그래밍 문제 해결 역량을 중요시 하는 현재 기업 채용 추세에 맞춰 알고리즘 스터디를 교외에서 찾을 필요 없이 우리 학교 학생들과 함께 혼자 접근하기 어려운 알고리즘을 다 같이 공부하자는 취지로 만들어졌습니다! 😀저희 학회는 이런 분들에게 추천합니다! ✔알고리즘에 관심이 있으신 분! ✔코딩 꾸준히 해야한다고 생각하는데 혼자하면 안되는 분! ✔삼성, 카카오, 네이버 등 기업 코딩 테스트에 통과하고 싶은데 정보가 없으신 분! ✔acm-icpc, 삼성 scpc 등 알고리즘 대회에 참가하고 싶은데 정보가 없거나 같이 공부할 사람이 없으신 분! 22년 1학기 학회 운영 계획 ✅ 코딩테스트 준비 ..
https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 문제분석 n개의 패턴을 입력받아 n개의 패턴 중 똑같은 것만을 출력하고 나머지 다른 부분은 '?'를 채워 출력하는 문제이다. 소스코드 n = int(input()) name = [] for i in range(n): name.append(input()) tmp = list(name[0]) for i in range(n): for a in range(len(tmp)): if tmp[a] == ..
문제 링크 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 파이썬의 deque 모듈을 이용해 BFS를 구현하였다. BFS를 하기 전 memo 변수에 W팀의 탐색을 진행하는지, B팀의 탐색을 진행하는지 기록하였다. (line 16) 탐색 조건으로 memo 변수에 저장된 팀에 속한 병사인지 체크한다. (line 24) num 변수는 모여있는 병사들의 수를 센다. (line 15) 탐색 조건을 만족하면 num 수를 1씩..
문제링크 예제 입력 1 5 RRRBB GGBBB BBBRR BBRRR RRRRR 예제 출력 1 4 3 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다. 적록색약 : G,R을 구별 못 함 Solution Base: 깊이 우선 탐색을 사용하여 R,G,B 일 때를 모두 탐색 def bfs(x,y,color): global isvisited isvisited[x][y] = True dx = [0,1,0,-1] #위 아래 왼쪽 오른쪽 방향 설정 dy = [1,0,-1,0] for i in range(4): mx = dx[i] + x my = dy[i] + y if 0
문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 dfs와 bfs에 대한 기초를 점검하는 문제이다. 그래프를 인접행렬과 인접리스트로 나타낼수 있는데, 인접행렬보다 인접리스트가 메모리 측면에서 더 좋기때문에 벡터를 이용하여 구현하였다. 입력받을때 양방향 그래프이므로 양쪽모두에 간선을 넣어주고, 각 노드 벡터마다 정렬을 해준뒤 구현하면 된다. 코드 #include #include #include #in..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 코드 #include using namespace std; #include #define PI 3.141592653589793 #define ll long long int a[505][505], d[505][505]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i = 1; i a[i][j]; } } d[1][1] = a[1][1]; for(int i = 2; i
