Skip to content

Latest commit

 

History

History
211 lines (115 loc) · 7.05 KB

220725_Algorithm.md

File metadata and controls

211 lines (115 loc) · 7.05 KB

💻알고리즘이란?

  • 문제 해결 위한 일련의 절차나 행동이다.

  • 문제란 input을 넣었을 때, 원하는 output이 나오도록 하는 것

  • 컴퓨터가 실행되는 일련의 절차가 모두 Algorithm이라고 한다.

  • 절차를 정의하는 과정

🌟즉 알고리즘이란 원하는 output이 나오도록 하는 일련의 논리적인 절차나 행동을 뜻한다.


💻코딩테스트란 무엇인가?

사실 다른 설명이 필요없다. 알고리즘을 활용한 문제 해결 능력을 평가하는 것이 코딩 테스트이다.

  • 코딩을 통한 문제 해결 능력을 테스트

  • 프로그래밍(알고리즘)을 통한 문제 해결 능력을 테스트

🌟코딩테스트에서 평가하는 두가지 사항

  • 문제 해결력:문제 의도를 정확히 파악하고 해결방법 적용이 가능한가?

  • 구현력:해결방법을 프로그래밍을 통해 능숙하게 구현할 수 있는가? (코딩테스트에 있어서 좀 더 중요한 요소라고 할 수 있다. 결국 구현력이 받쳐주지 않으면 문제를 해결할 수 없기 때문이다.)

  • 코딩테스트가 실제 현업 환경과 달리 객체 지향적 코드를 작성하지는 않지만 신입의 실력을 어느 정도 측정하는데 좋은 지표가 된다.

🌟코딩 테스트 시 몇 가지 꿀팁

  1. 문제를 먼저 "정의"하는 것이 중요하다. 무작정 코드를 작성하려고 하지 말고, 펜과 종이를 활용하여 설계를 먼저 해보자. 슈도 코드를 작성하거나, 문제 접근법에 대해서 깊게 생각해보자.

  2. Test Case가 다 맞다고 끝이라고 생각하지 말고, edge case를 확인해보자. 실제로 백준 문제 풀면서 Test Case에만 의존해서 반례를 찾지 못하고 틀린 문제가 굉장히 많았다.

🌟코딩테스트의 유형

  1. 오프라인 유형: 개발형 코딩테스트

  2. 오프라인 유형: 화이트보드 손코딩(지원자가 문제를 어떻게 해결하는지 논리, 과정, 커뮤니케이션 스킬을 평가). 유튜브에서 구글의 화이트보드 손코딩 테스트를 검색해서 보자.

실제로 300~400정도 문제 풀면 코딩테스트에 무난하게 합격 가능한 실력에 도달할 수 있다.

🌟기타 꿀팁

  1. 변수명 대충 짓지 않기

  2. 언어가 가지는 내장 함수, 라이브러리를 적극 활용하기

  3. 반복되는 코드는 함수화를 통해 가동성 있게 작성하자.

  4. 면접을 위해 풀이를 남에게 설명하는 연습이 반드시 필요하다. 코드리뷰를 열심히 하며 해당 실력을 기를 수 있도록 노력하자.


💻데이터구조(Data Structures)

컴퓨터에는 본질적으로 3가지가 있다.

  1. 저장

  2. 반복

  3. 분기


💻데이터의 저장소의 형태

데이터를 저장하는 저장소에는 list, dictionary, set, tuple와 같은 다양한 형태의 저장소가 존재한다. 이해를 쉽게 하기 위해 data를 물이라고 하고 물통을 data structure라고 하자. 문제 해결에 따라 데이터를 저장하는 통의의 형태가 다르고 더 적합한 형태의 통을 활용해야한다.

데이터 구조 == 데이터 + 구조

구조를 안다는 것은 데이터를 "어떻게 저장"하고 "어떻게 활용(조작)"할 수 있는지 알 수 있게 한다.


💻컨테이너의 형태

1.시퀀스형: 순서가 있음. 순서가 있다는 말은 인덱스로 해당 원소에 접근이 가능하다는 말이다.

  • 리스트(mutable): 주요 메서드 및 함수로는 append(), sort(), extend(), insert() 등이 있다.

  • 튜플(immutable): 주요 메서드 및 함수로는 add(), count(), index 등이 있다. 리스트와의 가장 큰 차이는 원소를 삭제하거나 변경할 수 없다.

  • 레인지(immutable): range()로 사용한다. 주로 for 문에서 범위를 정하기 위해 사용되며, range(start, end, step) 에서 인자(start, end, step)를 받는다.


2.비시퀀스형: 순서가 없음. 인덱스를 통해 원소에 접근이 불가능하다.

-세트(mutable): 중복된 데이터를 더할 수 없고, 순서를 가지지 않는다. 주요 메서드 및 함수로는 add(), update(), remove(), intersection(), set_a & set_b 등이 있다.

-딕셔너리(mutable): 튜플처럼 순차적으로 요솟값을 구하지 않고, key-value 쌍을 활용하여 원소에 접근한다. 해시 값을 활용하는데 이는 추후에 알아볼 예정이다. 주요 메서드 및 함수로는 get(), items(), keys(), values() 등이 있다.


💻데이터구조:

구체적인 저장소의 종류는 조금씩 차이가 있으나, 컴퓨터 과학적인 측면에서 데이터 구조는 크게 아래와 같이 나뉜다.

list, set, dict, stack, queue

💻코딩 테스트를 위한 데이터 구조와 알고리즘

위의 데이터 구조에서 조금더 구체적으로 들어가서 데이터 구조를 분류해보자.

🌟데이터 구조의 종류:

자세한 종류 및 정의는 추후에 차차 알아가보자.

Array

Linked List

Hash

Stack

Queue

Priority Queue

Heap

Tree

Graph


🌟알고리즘의 종류:

자세한 종류 및 정의는 추후에 차차 알아가보자.

재귀(Recursion), 완전탐색, 시뮬레이션, DFS, BFS, 백트래킹


💻입력 및 출력

말 그대로 뭔가를 입력 받는 행위와 결과를 출력하는 행위이다.

  1. 입력 활용 예시(input)

  • input()은 사용자의 입력 한 줄을 문자열로 받는 함수

  • 컴퓨터가 제어권을 사용자에게 넘겨주고 우리가 입력을 하면 입력한 데이터가 해당 변수에 저장된다.

  • input()과 map함수 이용하여 원하는대로 입력 받기

word = input()

b = int(input())
c = float(input())

d,e = map(int, input().split())
f,g,h = map(float, input().split())
a,b,c = map(int, a) => a b c
a: input().split()

  1. 출력 활용 예시(print)

  • print()는 데이터를 출력할 수 있는 함수이며, 자동적으로 줄 바꿈 발생이 된다.

  • 콤마(,)를 이용해 여러 인자를 넣으면 공백으로 인식한다.

  • end,sep 옵션을 사용해서 출력을 조작 가능하다.

a = 'Hello'
b = 'World'
print(a, end='@')
print(b) # Hello@World

print(a,b,sep='\n')
# Hello
# World
a,b,c = map(int, input().split())
print(a,b,c) # 1 2 3

a,b,c = map(int, input().split())
print(a,b,c, end='&') # 1 2 3&

References

https://www.w3schools.com/python/python_lists_methods.asp (파이썬 리스트 메서드)

https://www.w3schools.com/python/python_ref_tuple.asp (파이썬 튜플 메서드)

https://withcoding.com/79 (파이썬 레인지 사용법)

https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=heartflow89&logNo=221071487845&redirect=Dlog&widgetTypeCall=true&directAccess=false (파이썬 set 함수 및 메서드)

https://wikidocs.net/1015 (파이썬 set 특징 및 메서드/함수)

https://wikidocs.net/16 (파이썬 딕셔너리 특징 및 메서드/함수)