전체 글

정의 및 장단점 DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 연결되어 있는 노드를 깊숙히 바고 들어간다. 그 노드의 끝을 보고 다시 돌아오면서 연결되어있는 다른 노드를 찾을시 이번엔 그 노드를 끝까지 파고든다. 스택을 기초로 하고 있다. 구현방법 스택, 재귀함수를 이용하여 구현한다. 스택을 기초로 하지만 직접적으로 사용하지는 않음. O(N)의 시간이 소요. 문제 예시 NxM의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구머이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크..

정의 연결되어 있는 객체 간의 관계를 표현하는 비선형 자료구조 가장 일반적인 자료구조의 형태로, tree도 그래프의 특수한 경우이다. 예를 들면, 전기회로의 소자 간 연결 상태나 혹은 운영체제의 프로세스와 자원 관계 또한 그래프로 표현이 가능하다. 그래프의 종류 1) 무향 그래프 (undirected graph) : 무향 에지는 양방향의 의미임. 예컨대 조합(combination)처럼 (A,B) = (B,A)로 순서에 의미가 없다는 것. 2) 방향 그래프 (directed graph) : 에지를 통해서 한쪽 방향으로만 갈 수 있다는 특징. 즉, ≠ 라는 특성을 보임. cf.) 가중치 그래프: 각 간선에 가중치를 부여한 형태의 그래프. 예를 들면 edge에 비용을 부과하는 형식으로 가중치가 부과될 수 있음..

이 문제는 이것이 코딩테스트다 책 149페이지의 문제이다. DFS의 제일 기초적인 문제이다. 구현자체는 빠르게 했는데 변수이름을 잘못적어 오류를 찾느라 시간이 생각보다 오래 걸렸다... DFS문제는 주기적으로 풀어주어야겠다. 아래는 나의 코드이다. import sys myMap=[] move=[(-1,0),(1,0),(0,1),(0,-1)] N,M= map(int,sys.stdin.readline().split()) visited=[[True]*N for _ in range(M)] for i in range(M): temp = (sys.stdin.readline().split()) myMap.append(list(map(int,temp[0]))) print(myMap) def search(start_x,..

학과수업인 임베디드시스템설계및실험 수업이 드디어 끝났다... 한학기내내 나를 괴롭혔던 과목이다.. 맨날 집에도 못가고... 마지막 프로젝트때문에 이틀밤을 샜다.... 진짜 죽을 것 같았다.. 마지막시연 때 로봇차가 제대로 작동하지는 않았지만... 그래도 후련했다.. 후우 프로젝트에 대한 내용은 보고서파일에 친절히 나와있기 때문에 링크만 걸어야겠다.. 다신 듣기 싫은 과목이다.. 그래도 임베디드관련해서 좋은 경험이 된 것 같긴하다.. https://github.com/yunzae/Embeded-System/tree/main/Embeded/프로젝트

정의 및 특징 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다. 떠오른 풀이방법을 구현하기 위해서는 프로그래밍언어의 문법을 알아야며 요구사항에 맞게 실수없이 코드를 작성하여야한다. 구현은 흔히 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다. 문자열을 파싱하여 처리하는 문제, 코드가 길어지는 문제, 사소한 설정이 많은 문제 등이 구현문제의 예이다. 크게 완전탐색,시물레이션 문제가 코딩테스트에 자주 출제된다. 구현문제의 경우 문자열처리가 쉽고 기본적으로 메소드를 많이 지원해주는 파이썬이 유리할 수 있다. API개발문제 또..

정의 및 장단점 가장 나중에 넣은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조로 Last In First Out(LIFO) 방식이다. 프링글스나 쌓아놓은 책과 같다 구현방법 리스트를 이용하면 된다. 리스트 맨 뒤에서의 작업은 시간복잡도가 낮기 때문에 따로 스택라이브러리가 필요하지 않다. #a_list.append(1) : 괄호 안의 요소를 리스트 맨 뒤에 넣음 a_list = [1,2,3] a_list.append(1) => [1,2,3,1] #a_list.pop() : 리스트의 맨 뒤에 요소를 꺼내고 리스트에서 삭제함 a_list = [1,2,3] a_list.pop() => [1,2] print(a_list.pop()) 출력: 2 a_list : [1]

이 문제는 이것이 코딩테스트다 118페이지에 있는 문제이며 난이도는 2/3 이고 풀이시간은 40분이다. 이 문제는 한번 풀어본 적이 있어서 풀이시간안에 풀 수 있었다. DFS 문제와 거의 흡사한 듯하다. 아래는 나의 코드다. import sys direction=[(0,-1),(1,0),(0,1),(-1,0)] #북,동,남,서 mymap = [] n,m=map(int,sys.stdin.readline().split()) x, y, start_direction = map(int,sys.stdin.readline().split()) for i in range(n): mymap.append(list(map(int,sys.stdin.readline().split()))) result=0 def move(x,y,..

이것이코딩테스트다 118페이지 문제이다. 풀이제한시간은 20분이며 제한시간에 딱 맞게 푼 것 같다. 오랜만에 파이썬 언어를 사용하니 헷갈리는게 많아서 시간 소비가 많았다.. 항상 구현문제를 풀다보면 그냥 노가다를 할까 라는 생각이 많이 드는데 실력이 부족해서 인듯하다.. 아래는 나의 코드이다. myinput=input() row_list=['a','b','c','d','e','f','g','h'] row=myinput[0] column=int(myinput[1]) row1=0 row2=0 col1=0 col2=0 for i in range(len(row_list)): if row_list[i]==row: row_num=i+1 row_check2=[row_num+2, row_num-2] # 좌우 두칸che..