🍎🍏 — 🍎🍏

[DFS와 BFS] [Python / C++] 1707. 이분 그래프

2021.04.14

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데..

✍️ 코테 준비/DFS, BFS

[DFS와 BFS] [Python / C++] 7562. 나이트의 이동.

2021.04.13

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테..

✍️ 코테 준비/DFS, BFS

[DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.

2021.04.12

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. 출력 첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다. 해결 방법 최단 경로 문제이다. 이 문제를 처음 접했을 때는 DFS로 풀어야하는 줄 알았다. 벽을 부셨는지 확인하는 bool..

✏️ 알고리즘/Graph

5. Floyd Warshall(플루이드 와샬) : 최단 경로 탐색 - 3

2021.03.31

Floyd Warshall (플루이드 와샬) 최단 경로 탐색 - 3 오랜만에 포스팅이다. 주말마다 한 개씩은 쓸라했는데 주말에 좀 바빠서 못썼다... 어제 백준에서 플루이드 와샬 문제를 풀고 갑자기 블로그 포스팅이 생각나서 쓰게 됐다! 다익스트라, 벨만 포드에 이은 플루이드 와샬 알고리즘 최단 경로 탐색 카테고리의 마지막 내용이다. 다익스트라, 벨만 포드는 특정 노드에서 다른 노드까지의 최단 경로를 탐색해준다. 조금 생각을 바꿔서 모든 노드에서 다른 노드까지의 최단 경로를 탐색하려면 어떻게 해야할까? 우선 기존에 배웠던 다익스트라와 벨만 포드를 사용하여 탐색할 수 있다. 다익스트라에서 입력 값으로 넣어주는 src, 즉 출발 노드를 모든 노드로 설정하면 된다. 그만큼 반복문을 돌아야하기에 시간복잡도는 N만..

⛹️ 라이프/코딩 테스트

[스코페 2021] Startup Coding Festival 2021 - 1차 예선 결과

2021.03.23

동아리 톡방에 관련 공지가 올라와서 백준도 어느정도 풀어봤겠다 싶어서 실력을 테스트할 겸, 카카오 코테 준비하는 겸 해서 스코페에 참가하게 됐다! 스코페 2021, SCOFE 2021 스타트업 기업들이 주최하는 코딩테스트였다! 왓챠, 쏘카, 오늘의 집, 마켓컬리, 브랜디, 번개장터 다들 한번씩은 들어본 이름이라고 생각한다! 문제마다 특정 기업이 들어가있었던거보면 기업별로 1문제씩 출제한 것으로 보인다. 언어는 내가 제일 좋아하는 파이썬으로 진행했다. 총 문제 6문제. 배점은 20 / 20 / 20 / 20 / 30 / 30 으로 총점 140점이였다. 내가 획득한 점수는 대략 110점 정도 되는 것 같다. 문제별로 테스트 케이스를 모두 통과하면 "맞았습니다" 가 출력된다. 문제당 확인할 수 있는 테스트 케..

✏️ 알고리즘/Graph

4. Bellman-Ford(벨만 포드) : 최단 경로 탐색 - 2

2021.03.07

Bellman Ford (벨만 포드) 최단 경로 탐색 - 2 오늘은 지난번 다익스트라에 이어 최단 경로를 탐색하는 알고리즘을 정리하려고 한다. 지난번 다익스트라 포스팅에서 다익스트라는 음의 사이클이 있는 그래프에서는 사용이 불가능하다고 하였다. 그 이유는 무엇일까? 우선, 다음과 같은 그래프의 시작 정점이 A라고 했을 때의 최단 경로를 구해보자. [예상 결과] A : 0 B : -4 C : 3 D : -7 E : 1 F : -3 [실제 결과] 시작 정점에서 이상한 값이 출력되는 것을 볼 수 있다. 다른 예시를 보자. [예상 결과] A : 0 B : 2 ( 재방문을 하지 않는다고 가정) C : 5 D : 1 E : 3 [실제 결과] 역시, E 정점에서 이상한 값이 출력되는 것을 볼 수 있다. 이유가 뭘까?..

✏️ 알고리즘/Graph

3. Dijsktra(다익스트라) : 최단 경로 탐색 - 1

2021.03.02

Dijsktra (다익스트라) 최단 경로 탐색 - 1 정말 오랜만에 포스팅이다. 원래 목표대로 진행했으면 개강을 하기 전에 DP까지 포스팅을 했어야하는데 요새 조금 바빴다...(사실 의욕이 없던걸 수도...) 아무튼 이번 3-1 과목에 알고리즘 응용이라는 과목을 수강하는데 작년에는 딥러닝과 관련하여 수업했다고해서 신청했는데 이번에 교수님이 바뀌면서 정말 알고리즘에 대해 학습하는 수업이 되어버렸다. 살짝 아쉬웠지만 강의계획서를 보니 2-2 알고리즘 수업과 거의 비슷해서? 학기 초에 미리미리 정리해두려고 한다. 서론이 길었다. 다익스트라는 최단 경로를 탐색하는 알고리즘이다. 다음과 같은 그래프의 최단 경로를 탐색해보자. graph 변수에 연결된 정점과 가중치가 저장되어 있다고 본다. graph[1] = [2..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 2565번. 전깃줄

2021.02.01

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 입력 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 출력 첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 ..

✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 11054번. 가장 긴 바이토닉 부분 수열

2021.02.01

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다. 해결 방법 이전 문제인 가장 긴 증가하는 부분 수열의 변형 문제이다. (아직 풀지 않았다면 아래 문제를 먼저 풀어보도록 하자.) www.acmicpc.net/problem/11053 11..

⛹️ 라이프/2020 겨울방학 모각코(개인)

[코독하구만 팀] 2021.01.27(수) - 6주차 개인 결과

2021.01.27

- 목표 - codekodo.tistory.com/42 [코독하구만 팀] 2021.01.27(수) - 6주차 개인 목표 - 목표 - 다이나믹 프로그래밍의 개념을 실습 문제를 통해 학습하고, 이를 응용하여 백준 문제에 적용해본다. 1. 피보나치 피보나치 수열의 N번째 항을 출력하시오. [입력 값] 0 [출력 값] 0 [입력 codekodo.tistory.com 1. 피보나치 재귀로 풀어도 되지만 dp를 활용하면 더욱 빠르게 정답에 접근이 가능하다. 2. 가방 점화식을 유도해야한다. 행은 가방의 최대 무게이고, 열은 주어진 물건의 무게이다. 이를 이용하여 최대한의 값어치를 구하고 표를 채우면 다음과 같이 채울 수 있다. 0 1 2 3 4 5 0 0 0 0 0 0 0 2 0 0 3 3 3 3 3 0 0 3 4..

전체 글

[DFS와 BFS] [Python / C++] 1707. 이분 그래프

[DFS와 BFS] [Python / C++] 7562. 나이트의 이동.

[DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.

5. Floyd Warshall(플루이드 와샬) : 최단 경로 탐색 - 3

[스코페 2021] Startup Coding Festival 2021 - 1차 예선 결과

4. Bellman-Ford(벨만 포드) : 최단 경로 탐색 - 2

3. Dijsktra(다익스트라) : 최단 경로 탐색 - 1

[동적 계획법 1] [C++] 2565번. 전깃줄

[동적 계획법 1] [C++] 11054번. 가장 긴 바이토닉 부분 수열

[코독하구만 팀] 2021.01.27(수) - 6주차 개인 결과

티스토리툴바