전체 글
0518_백준 11403번 : 경로찾기 / 플로이드-워셜 알고리즘
[문제 풀이] 이번 경로찾기 문제는 전형적인 DFS문제이다. 처음 예제를 확인할 때는 주어진 정점 간의 연결 상태를 파악하는 게 다소 이해가 안 갔는데, '플로이드-워셜 알고리즘'을 통해 간단하게 문제를 해결할 수 있었다. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다. (출처_나무위키https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C..
0515_알고리즘 백트래킹(Backtracking) 정리
그 동안 문제 풀면서 자주 들었던 말.. "이거 백트래킹으로 풀면 돼^^" 찾아야 하는 경우의 수를 줄이는 것은 알았지만, 정확히 어떤 식으로 해결하는 지는 몰랐는데 드디어 오늘 SSAFY 라이브 강의에서 백트래킹 개념을 배웠다. [개념 정리] 백트래킹을 내 식대로 정리하자면, 가장 기본적으로는 '해를 찾는 것'이다. 근데 해를 어떻게 찾느냐 하면, 깊이우선탐색(DFS)와 비슷하게 풀이된다. 이때 다른 점은 깊이우선탐색은 가능한 모든 경우의 수를 탐색하는 것이고, 백트래킹은 조건에 만족한 노드만을 찾아 탐색하다가 해를 찾으면 탐색을 멈추기 때문에 결과적으로 훨씬 적은 경우의 수를 탐색하게 된다. (물론 그렇지 않을 때도 있다.) 즉, 기본적인 뼈대는 DFS지만 만족해야 하는 조건을 넣어주어 탐색하는 경우..
0514_백준 14890번/경사로_파이썬
"가로 세로 모두 확인해야 함, zip으로 전치행렬 활용" 새로 써본 것은 ziiiiiiip! [풀이 과정] - 특별한 알고리즘 없이 주어진 조건을 빠짐없이 고려하여 푸는 문제 - 가로행, 세로열 두번 탐색해야 해서 -> zip 함수 활용 zip(*iterable)은 동일한 개수로 이루어진 자료형을 묶어 주는 역할을 하는 함수 - 내가 고려한 조건들은 아래와 같다. ① 경사로를 놓는 방법을 크게 '높은 곳에서 낮은 곳으로 향하는 것', '낮은 곳에서 높은 곳으로 향하는 것' 두 가지로 나눔. 그리고 경사 높이 차이를 비교 -> 1차이가 나는지 확인 ② 범위를 벗어나지 않게 인덱스 위치 확인 ③ 경사로를 놓았는지 확인해주기 위해 visit 배열 활용 - 한 행, 한 열씩 돌아가며 길이 되는지 확인하는데 이..
0513_백준 14891번/ 톱니바퀴_파이썬
"deque 모델의 rotate 메소드 사용하기" [문제 접근] - 처음에는 주어진 톱니바퀴 번호에 따라 분기처리 하여 하드코딩 했다가, 중간에 실패했다. 이유는 톱니바퀴 4개가 한번에 돌아야 하는데 내가 구현한 코드는 순차적으로 돌아가다 중간에 끊겨서 제대로 된 결과를 얻기 힘들었다. - 타 블로거님들의 코드를 참고하여 다시 풀었는데, collections 모듈의 deque(double ended queue)의 rotate 메소드를 활용했다. - rotate의 기본적인 구조 : rotate(n) 요소 n의 값에 따라 음수면 n만큼 왼쪽 회전, 양수면 n만큼 오른쪽 회전(시계방향) - 시작 톱니를 잡아 ①12시 방향을 기준으로 2번, 6번에 위치한 톱니의 극(1 또는 0) 정보와 ② 회전방향(시계 또는 ..
0512_백준/14499번/주사위 굴리기_파이썬
[문제 접근 방법] - 특별한 알고리즘이 있지 않고, 주어진 상황을 코드로 구현하는 문제였다. - 기본적인 로직은 주어진 명령의 방향에 따라 주사위의 면을 바꿔주는 것이다. - 기타 조건으로는 배열의 인덱스 에러 여부를 확인해주는 것 그리고 지도 위의 이동 칸이 0인지 아닌 지에 따라 주사위면과 이동칸의 숫자를 바꿔주는 로직을 넣어줘야 했다. - 주어진 상황을 빠짐 없이 조건으로 넣어주면 풀 수 있는 문제 [피드백] - 주사위의 윗면과 아랫면이 정해져 있는데, 처음에 문제를 잘못 읽어서 아랫면이 1이라고 착각했었다. - 주사위의 면을 방향에 따라 어떻게 바꿔줄지를 많이 고민했지만, 결국 하드 코딩으로 작성했다. [코드 구현] n, m, x, y, k = map(int, input().split()) ar..
0410_Data Structure /Linked List /Python / 클래스 구현
오랜만에 블로그를 쓴다. 며칠 만인지.. 그 동안 web을 중점적으로 공부하느라 알고리즘에 소홀했는데 (시험 점수는 거짓말 하지 않지ㅠ) 앞으로 하루에 한문제씩은 알고리즘 문제를 풀면서 감을 챙길 생각이다. 어제 오늘 싸피에서 수업했던 내용은 바로 'Linked List'. 말은 쉽지만 코드로 구현해 내기까지 시간이 좀 걸렸다. 처음 과제로 받은 두 개의 문제 중 하나는 단순 리스트로 만들어서 풀었지만, 두 번째는 runtime error... 클래스 피해가려다 더 멀리 돌아가게 됐다ㅎ 사실 처음에는 class 정의해서 푸는 게 생각보다 복잡해 보이고(왜냐,, 나는 객체지향이 아직 낯설기 때문이다.) linked list에 대한 완벽한 이해도 되지 않은 상태라 도전할 엄두가 안 났지만, 과제는 해야겠고 ..
0316_Web page를 꾸미는 역할, CSS
CSS (Cascading Style Sheets) 기존 HTML이 정보에 집중하는 언어라면, CSS는 디자인적 요소를 책임지는 별도의 언어이다. HTML로 웹 페이지에 들어갈 정보를 일단 입력하고 나면, CSS를 통해 사용자로 하여금 간편하고 보기 좋도록 페이지를 꾸며준다. 도입 배경을 간단히 설명하면 다음과 같다. 원래는 HTML 의 기존 틀 안에서 스타일적 요소를 넣어 페이지를 꾸미다 보니 정보 요소와 디자인적 요소가 혼재되어 코드가 지저분해지고 용량이 커지며 사용자들이 많아질수록 불편을 겪을 수 밖에 없는 구조가 되었는데, 이런 문제를 해결하기 위해 새로운 언어를 개발하였고 그게 바로 CSS이다. 장점 CSS 덕분에, 코드의 중복성을 제거하고 / 웹페이지의 유지 및 보수가 용이해지고 / 코드 가독..
0315_First step to Web, Summary about HTML
HTML - HyperText Markup Language HTML은 무엇인가. => Language의 개념. 결론부터 말하자면 웹페이지를 구성하기 위해서 작성하는 컴퓨터 언어이다. 쉽게 말해 개발자가 의도하는 대로 웹브라우저가 읽어들여 웹페이지를 구성할 수 있도록 하는 일종의 명령어인셈이다. 따라서 웹페이지를 만들기 위해서는 필수적으로 알아야 한다. HTML는 1980년대쯤? 처음 만들어졌다고 하는데 일반인들에게는 1990년대에 공개된 것으로 알고 있다. 자세한 history는 모르니까 ->위키피디아 참고. (https://ko.wikipedia.org/wiki/HTML) 그래서 HTML은 무엇이 중요할까. 바로 'Information(정보)'이다. 웹 페이지에서 HTML이 가지고 있는 것은 바로 정보..