이 문제는 이것이 코딩테스트다 책 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..
우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조입니다. 이 말은 내부적으로 데이터를 정렬된 상태로 보관하는 메커니즘이 있다는 뜻이고, 좀 더 구체적으로 얘기하면 heapq 모듈을 통해 구현되어 있습니다. 내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(log n)의 시간 복잡도를 가집니다. 코드예시 from queue import PriorityQueue que = PriorityQueue() # que = PriorityQueue(maxsize=8) 디폴트사이즈는 무한대이..
정의 및 장단점 큐는 선입선출,FIFO(First In First Out)의 방식이다. 가정 먼저 들어온 데이터가 가장 먼저 나간다. 제일 먼저 들어온 데이터를 HEAD, 맨 뒤의 데이터를 TAIL이라고 한다. 구현방법 파이썬에서는 리스트방식 또는 라이브러리를 이용한 방식으로 나뉜다. 리스트방식: pop(0) 또는 insert(0,x)등의 방법은 복잡도가 O(n)이므로 아래의 다른 방법보다 불리하다. 리스트의 마지막 원소의 삭제는 O(1)이지만, 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다. 자료구조 뒤에서 추가/삭제는 덱과 리스트는 속도 차이가 없지만, 첫번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생합니다. 데이터가 커지고 데이터의 양끝에서 ..
