웹개발일지

코테 풀이를 하고나서 내가 쓴 코드와 비교하여 다른 사람이 쓴 코드가 배울 점이 많다고 생각하여 기록하게 되었다. 문제해석 아래 두 자료가 주어진다. 여기서 height보다 큰 수가 array에서 몇 개인지 찾는 문제이다. array = [160, 175, 180, 195] height = 170 내가 쓴 코드 def solution(array, height): count = 0 for i in array: if i > height: count += 1 return count 굉장히 직관적으로 푼 편이다. height 보다 큰 요소의 '개수'를 구하는 것이므로, count 변수를 지정하여 array를 순회하며 조건문을 통해 height 보다 클 때 마다 count를 1씩 증가시켜 준 뒤 return 하였..

주말 과제로 프로그래머스의 달리기 경주를 풀었다. 문제는 이해하고 바로 작성하기 쉬운 편이어서 떠오르는대로 금방 작성해볼 수 있었다. 그런데 시간 복잡도를 전혀 고려하지 못해 관련해서 조금 다뤄 보려고 한다. 문제 요약 문제는 리스트 안의 요소들을 순회하며 탐색한 뒤 해당 요소들을 가지고 또 다른 리스트에 접근하여 Swap 시켜주는 문제였다. 내가 짠 코드 players = ["mumu", "soe", "poe", "kai", "mine"] callings = ["kai", "kai", "mine", "mine"] def solution(players, callings): for i in callings: a = players.index(i) b = players.index(i)-1 players[a],..

이 글은 유데미 컴공선배 파이썬 알고리즘 강의 수강 내용을 정리한 글입니다. 공통점 모든 경우의 수를 찾는 완전탐색 방법을 이용한다. 차이점 탐색 순서의 차이 DFS ( Depth First Search) 깊이 우선 탐색 방법이다. 모든 노드를 탐색하고자 하기 위함이다. BFS 보다 간단하다 느리다. 스택(Stack), 재귀를 사용해서 구현한다. BFS (Breadth First Search) 너비우선 탐색 방법이다. 인접한 노드를 먼저 탐색한다 -> 최단 경로를 찾을 때 유리하다. 큐(Queue)로 구현한다. 주로 두 노드 사이에 최단 경로를 찾고 싶을 때 BFS 방법을 선택한다. 지구 상에 존재하는 모든 친구 관계 그래프로 표현한 후 Sam 과 Eden 사이에 존재하는 경로를 찾는 경우 깊이 우선 탐..

오랜만의 자료구조 포스팅입니다! 오늘은 연결리스트에 대해 공부한 내용을 정리하고자 합니다. 연결리스트는 코딩테스트에서는 잘 쓰이지 않지만 다른 자료구조들을 구현할 때 많이 쓰입니다. 오늘은 이러한 연결리스트가 배열과는 어떤 차이점이 있는지 시간복잡도의 개념과 함께 알아보고자 합니다. 우선, 시간 복잡도는 알고리즘의 최악의 경우의 실행시간을 뜻하며 입력량 N에 비례하여 얼만큼 연산을 많이하는지를 나타냅니다. 이러한 알고리즘의 효율성 척도를 나타낸 것을 또 빅오 표기법이라고 합니다. 표기 방법은 ‘O(N)’ 입니다. 흔히 O(N)이면 N번을 모두 연산 해야하는 경우기 때문에 효율성이 낮다고하고 O(1)이면 데이터의 수에 상관없이 연산횟수가 고정인 유형의 알고리즘으로 효율성이 좋다고 합니다. 흔히 배열은 삽입..

www.acmicpc.net/problem/2420 이 글은 백준 2420을 풀며 관련 개념을 정리한 내용입니다. 2420번: 사파리월드 첫째 줄에 두 도메인의 유명도 N과 M이 주어진다. (-2,000,000,000 ≤ N, M ≤ 2,000,000,000) www.acmicpc.net 문제파악 두 정수가 주어지면 절댓값을 구하는 문제였다. 첫 접근방식 조건문으로 두 수의 차를 양수로 나오게 할 알고리즘을 구현했다. a,b = int(input(" 두 수를 입력하세요")) if a >= b: a-b else : b-a print(type(a, b)) 두 번 런타임 에러 (value error)가 나서 찾아보니 타입 오류라는 것이었고 테스트를 위해 타입 출력도 해보았으나 첫 번째 줄에서 나는 오류였다. ..

맵 key와 value로 이루어진 자료구조이다. "": ""의 형태로 JSON 구조와 비슷하다. 값은 중복 가능하나 키는 중복일 수 없다. 키로 검색해서 값을 찾는 구조이기 때문에. 시간복잡도 C++의 삽입/삭제 시간복잡도는 log(N)이다. 맵에 값을 한번 넣을때 혹은 삭제할 때 마다 시간복잡도가 log(N)인 것. log(1)보다 엄청 느린 것은 또 아니다. 파이썬은 어떤 키 값이 주어졌을 때 해시 함수 y = f(x) 에 키 값을 x에 대입하면 y가 나오는데 y는 해시 테이블에서 이 키에 해당하는 value를 어디에 담을지 주소값에 해당한다. 따라서 키를 넣으면 해시테이블의 위치를 바로 알 수 있다. 이 함수 자체의 시간복잡도가 O(1)이다. 물론 충돌이 나는 경우 등 1이 아닌경우도 있지만, 따라..