문제 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
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net [풀이] 나이트가 이동하는 방향만 잘 고려한다면 결국 최단 거리를 찾는 문제와 동일하기 때문에 전형적인 BFS 문제입니다. 다른 기본적인 BFS 최단거리 문제에서 사용하는 상하좌우로 이동 대신 나이트가 이동 가능한 8방향으로 이동하며 탐색합니다. 목적지까지의 Depth를 찾으면 되는 간단한 문제였습니다. 더보기 #include #include #include using namespace std; i..
문제 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 가장 처음에 생각난 풀이는 n^3 * logn의 풀이인데 (임의의 세수 합을 구해서 이분탐색으로 찾기) n 이 최대 1000이기 때문에 시간초과가 난다. 정답을 구하기 위해서는 n^2 또는 n^2logn의 풀이를 생각해야 했고 a + b + c = k 라고 할 때 a + b의 값을 갖는 배열을 만들기로 했다. a + b 배열을 만든 뒤 k..
* 개인 블로그에 작성한 내용을 복사해왔습니다. [Algorithm] BOJ 2251 BOJ 2251번 물통BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, 풀이를 하는 데 조금 시간이 걸렸습니다.처음에는 방문\_여부\[물통 A의 velog.io BOJ 2251번 물통 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net Intro BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, ..
