Swifting Swifting

문제 링크 : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net DFS 응용력을 길러준 문제이다. DFS로 탐색을 진행하면서 빨강 / 파랑으로 번갈아서 색칠을 한다고 가정하였다. 색칠 탐색을 끝낸 후에, 인접 리스트 그래프에서 자신과 같은 색깔로 칠해진 인접 노드가 있는지 확인한다. 인접 노드 중에 같은 색깔로 칠해진 노드가 있다면, 이분 그래프를 생성할 수 없다. 주의할 점 : 1. 1번 노드에 대해서만 DFS를 진행해서는 안된다. 주어진 그래..

문제 링크 : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 2가지 해법으로 이 문제를 풀어보았다. (1) 도착점에서 출발점으로 깊이 우선 탐색 (DFS) (2) 출발점에서 도착점으로 DFS 1번 풀이에서의 dp[x][y] == (x, y)에서 (0, 0) 까지 갈 수 있는 경로의 개수 2번 풀이에서의 dp[x][y] == (x, y)에서 (N-1, M-1) 까지 갈 수 있는 경로의 개수 😊 풀이 1 : 도착점부터 출발점까지 거슬러 올라가는 방법 ..

문제 : https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 😊 정답 코드 from collections import deque def s..

문제 : https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 2021 카카오 채용연계형 인턴십 3번으로 출제된 문제이다. 문제 이해 자체는 어렵지 않지만, 효율성 테스트를 통과하는 것이 어려워 난이도가 높다. 대놓고 첫째줄에 경고 문구가 적혀있다,, 😨 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 효율성 테스트를 통과하기 위해서 가장 중요한..

알고리즘 문제 풀 때 고려할 것 (내가 보려고 만듬) 자료구조 3가지 Stack Queue Heap 파이썬의 데이터 타입 4가지 List Tuple Dictionary Set 탐색법 3가지 순차탐색 이진탐색 해쉬탐색 문제가 풀리지 않을 때 고려해볼 알고리즘들 Dynamic Programming Prefix Sum (구간합 계산) Two Pointer

문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 최단거리 알고리즘 문제를 읽고, 최단거리 알고리즘을 이용해 풀이 해야한다는 것은 판단할 수 있었다. 다음은 대표적인 최단거리 알고리즘 2개이다. 다익스트라 알고리즘 (Dijkstra) 플로이드 워셜 알고리즘 (Floyd-Warshall) 😨 잘못된 풀이 : 플로이드 워셜 처음엔 아무생각 없이, 다익스트라보다 플로이드 워셜 알고리즘이 더 사용하기 편했기 때문에 플로이드 워셜 알고리즘으로 문제를 풀었다. def solution..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제 접근 처음에 문제를 읽어내려가면서, 그리디 알고리즘과 다이나믹 프로그래밍을 떠올렸다. 하지만, 제한사항을 읽고 이진탐색 문제라는 것을 깨달아 버렸다. Input 조건이 10^9 (10억) 이상이라면, O(N) 이상의 알고리즘을 작성했을시 효율성 테스트를 통과하지 못한다. 그래서 O(log N)의 복잡도를 가지는 이진탐색을 사용해야 하는 것이다. 이진..