Jinlib

문제 링크: https://www.acmicpc.net/problem/2178 풀이 1. 논리적인 순서 확정 입력1: 미로를 만들기 위한 행(N), 열(M)의 수 입력2: 줄바꿈(개행문자)을 기준으로 행의 수(N)만큼 추가적으로 입력을 하는데, 각 입력에는 열의 갯수(M)만큼의 숫자를 입력한다. 출력: 시작점부터 N,M까지 최단경로를 지나는 정점의 갯수 출력 이 미로문제를 격자형 그래프로 바라봤을때, 시작점부터 종착지까지 그래프의 연결노드 갯수(vertex)*_가 출력하고자하는 값과 동일함을 알수있다. *_격자형 그래프를 만들기 위해서는, 처음 시작하는 점에서 인접한 정점이 1일 경우 간선(Edge)을 만들어 줄 수 있다. 먼저, 격자형 그래프를 만들고 격자형 그래프를 만들게 되면 하나의 연결요소를 만들..

그래프 탐색 문제 그래프 탐색 문제란? 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을때, 시작점에서 간선(Edge, E)을 타고 이동할 수 있는 정점(Vertex, V)들을 모두 찾아야 하는 문제를 의미합니다. 이 문제를 해결하는 그래프 탐색 알고리즘에는 흔히 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있습니다. 이에 대해서 알아보도록 합시다. 두 알고리즘의 공통점은 그래프 탐색 문제에 대한 해답을 올바르게 찾는다는 점이다. 각 알고리즘의 특성을 살펴보자. 1. 깊이우선탐색(Depth-First Search, DFS) DFS는 깊이 우선 탐색이라고 불리며 그 이유는 그래프의 시작점에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하기 때문입니다. 알고리즘 개요는 시작점-> 시작..

서론 구현 3번째 문제이다. 이번 문제는 문자열을 정렬하는건데, 문자열 다루는 코딩테스트 문제는 대표적으로 카카오 계열에서 많이나온다고 한다. 본론 머릿속으로 생각해보면 전혀 어려워보이지 않는다. def stringSort(S): slist = list(S) num_sum = 0 asci_list = list(map(lambda x: ord(x), slist)) asci_list.sort() new_list =[] for index,sub_s in enumerate(asci_list): if ord('1')

서론 구현 2번째 문제이다. 이번 문제는 dx dy 방향벡터를 활용해서 문제를 풀어보도록 하겠다. 본론 1) a -> 1, b->2 ... h->8 으로 해석할 수 있겠구나! 이를위해 ord()함수를 써서 문자열을 아스키 코드로 바꿔서 행렬계산해보자(*chr()은, 숫자를 아스키코드로 바꾸는데 사용) def kingKnight(S): x = ord(S[0]) - 96 y = int(S[1]) cnt = 0 if x - 2 > 0 and y - 1 > 0: cnt+=1 if x - 2 > 0 and y + 1 > 0: cnt += 1 if x + 2 > 0 and y - 1 > 0: cnt += 1 if x + 2 > 0 and y + 1 > 0: cnt += 1 if x - 1 > 0 and y - 2 ..

서론 구현(Implementation) 문제는 머릿속에 있는 알고리즘을 소스코드로 바꾸는 문제를 일컫는말로 주로 시뮬레이션과 완전 탐색에 초점을 맞춘 문제유형이다. 일반적으로는 머릿속으로 떠올리는 것을 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 때로는 적정한 라이브러리의 능수능란한사용법을 요하는 문제도 존재한다. ex) 모든 순열, 모든 조합을 찾을때 python라이브러리를 활용하면 매우 간결하게 작성할 수 있다. 일반적으로 알고리즘 문제에서 2차원 공간은 행렬(Matrix)의 의미로 사용된다.위처럼 행렬을 이용해서 문제를 푸는일이 많다. 시뮬레이션 및 완전탐색 문제에서는 2차원 공간에서의 방향벡터를 자주 활용합니다  연습문제 코드 def checkTF(N): if N % 10 == 3 or N..

1. 서론 강의링크: https://youtu.be/2zjoKjt97vQ 2. 본론 그리디 알고리즘은 '현재 상황에서 당장 좋은 것만' 고르는 방법을 의미한다. 코딩 테스트 문제에 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 문제를 잘읽고 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 잡고 문제 풀이를 진행하자. 1) 예제문제: 모험가 길드 여기서 나는 함수형태로 만듬으로, [] 리스트 형태로 1개 받는걸로 하겠다. (1) 내코드 A. 오름차순으로 정렬 B. 모험가 수보다 cur가 크면 stop import heapq def heapsort(dataset): h = [] result = [] for value in dataset: heapq.heappush(h, value) for..

1. 서론 강의링크: https://youtu.be/2zjoKjt97vQ 2. 본론 그리디 알고리즘은 '현재 상황에서 당장 좋은 것만' 고르는 방법을 의미한다. 코딩 테스트 문제에 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 문제를 잘읽고 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 잡고 문제 풀이를 진행하자. 1) 예제문제: 곱하기 혹은 더하기 (1) 내코드 A. 0 혹은 1이면 곱셈보다는 덧셈이 유리 B. 문자열이 1개 밖에 없으면 자기 자신 리턴 def multiOrPlus(s): tmp = list(map(lambda x: int(x), list(str(s)))) result = tmp[0] if len(tmp) == 1: return result else: for cur..

1. 서론 강의링크: https://youtu.be/2zjoKjt97vQ 그리디 알고리즘, 탐욕 알고리즘 이라고 불리는 이것은 추후 배우게될 완전 탐색이나 dfs,bfs 등 역량을 키우는데 중요한 경험이 될것이다. 2. 본론 그리디 알고리즘은 '현재 상황에서 당장 좋은 것만' 고르는 방법을 의미한다. 코딩 테스트 문제에 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 문제를 잘읽고 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 잡고 문제 풀이를 진행하자. 1) 예제문제: 1이 될 때 까지 어떠한 수 N이 1이 될 때까지 2가지 연산을 반복적으로 수행할 수 있다. N에서 1을 뺀다 N을 K로 나눈다.내 코드 (1) 내코드 A. N이 1이 되면 반복을 멈추라고 함 B. 처음에 K로 나눠지..

1. 서론 하나라도 제대로 풀어보자. 퇴근이후에 코딩테스트를 풀기란 체력적으로 가용할 수 있는 머리가 부족하다. 이럴땐, 목표를 좀 낮추고 포기하지 않고 하나씩 서서히 해나가야 한다. 꾸준히 하자. 2. 본론 1) 공부자료 나동빈 저자의 이것이 코딩 테스트다 + 유튜브 강의 류호석님의 패스트 캠퍼스 강의자료 + 문제 모두 공인된 분들이시고 SW 취업 관련 오픈채팅방에서도 자주 거론되는 자료들이다. 2) 공부계획 최소 1문제는 문제를 풀자. 문제를 풀고나서 다른 모범답안에는 무엇이 있는지 찾아보고 내꺼 만들것. 진행사항을 꾸준히 이 게시글에 남길것. (1) 커리큘럼 동빈님 그리디&구현 동빈님 DFS&BFS + 호석님 그래프 탐색 동빈님 정렬 + 호석님 정렬 동빈님 이진 탐색 + 호석님 이분 탐색 동빈님 D..

1. Background Knowledge1) 삽입 정렬참조링크2) 버블 정렬참조링크 2. 예제2) 삽입 정렬1234567891011121314151617181920212223242526272829303132333435#include#include#define scanf scanf_sint* irtsort(int* A,int max) { int tmp; int vot; for (int i = 1; i = 0; j--) { if (vot