Coding Test

🔊 본 포스팅의 내용은 나동빈님의 [이것이 취업을 위한 코딩테스트다] 유튜브 강의를 수강 후 정리한 내용을 기록한 글로, 모든 사진과 자료의 출처는 해당 영상에 있습니다. 훌륭한 강의로 지식을 전달해 주신 나동빈님께 감사의 말씀을 전합니다. 목차 정렬 알고리즘 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 정렬 알고리즘 비교하기 정렬 알고리즘 예제 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 선택 정렬 동작 예시 선택 정렬은 반복시마다 탐색 범위가 줄어듭니다. 선택 정렬 코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 ..

https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 직사각형 모서리의 좌표 3개가 주어졌을 때, 남은 1개의 좌표를 찾는 문제이다. x,y좌표 각각 중복으로 입력된 좌표는 삭제하면, 남는 좌표가 정답이다. 예제 입력 1의 경우, x좌표는 5 5 7 이 입력되었으니 7만 남고, y좌표는 5 7 5 가 입력되었으니 7만 남는 것이다. 풀이 1. xor 이용 x = y = 0 # 초기값으로 x와 y를 0으로 설정 for _ in range(3): a, b = map(int, input().split()) # 사용자로부터 두..

문제 (https://www.acmicpc.net/problem/2563) 풀이 요약하자면, 입력한 좌표들로 인해 생성되는 사각형들의 넓이를 구하면 되는 문제이다. 나는 아래와 같이 풀이하였다. 1. 도화지를 1차원 배열로 생성 ( 100*100인 2차원 배열은 길이가 10,000인 1차원 배열로 표현 가능) 2. 입력된 좌표로 생성되는 사각형에 포함되는 부분에 1 할당 3. 배열의 모든 요소 더하기 ( = 면적 ) arr=[0]*10000 for _ in range(int(input())): col,row = map(int,input().split()) for i in range(col,col+10): for j in range(row,row+10): arr[i*100+j]=1 print(sum(arr..

알고리즘 알고리즘은 문제를 해결하는 방법입니다. 한 문제를 해결하는 방법은 무수히 많습니다. 그 중 자주 쓰이는 해결 방법에는 다익스트라, DP, DFS 등과 같이 이름을 붙여서 문제를 해결하는 방법을 패턴화 하였고 이것을 알고리즘 이라고 합니다. 알고리즘을 학습하여 응용, 적응 할 수 있게 된다면 코딩테스트의 문제를 보다 쉽게 해결할 수 있습니다. 알고리즘의 평가 기준 알고리즘의 평가 기준에는 3가지가 있습니다. 1. 시간 복잡도 : 문제를 해결하는데 걸리는 시간 과 관련이 있습니다. 시간이 적게 소요될 수록 좋은 알고리즘이라고 할 수 있습니다. 2. 공간 복잡도 : 한정된 메모리를 최대한 적게 사용할 수록 효율적입니다. 공간 복잡도를 통해 알고리즘이 메모리를 얼마나 차지하게 될 지 나타냅니다. 3. ..

문제 실행시간 제한 : 30sec 요약하자면, start와 end를 입력받고 두 수에 존재하는 a=b+c인 경우의 수를 모두 찾아 개수를 구하는 문제이다. 입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다. 시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다. 입력이 10,000,000 개의 경우: O(N) 알고리즘 입력이 50,000 개인 경우: O(N * log N) 알고리즘 입력이 10,000 개인 경우: O(N * N) 알고리즘 입력이 400개: O(N * N * N) 알고리즘 입력의 최댓값이 1,000,000 이기 때문에, O(n) 알고리즘의 경우 0.1 초가 걸릴것이고..

문제 : 일과를 마치고 온 백설공주의 난쟁이가 일곱명이 아닌 아홉명으로 돌아왔다. 기존 일곱 난쟁이의 키의 합이 100인 것을 기억해 내어 진짜 난쟁이 일곱명을 찾으려 한다. 입력 : 배열안에 난쟁이의 키가 주어진다. 키는 100을 넘지 않는다. 출력 : 입력된 순서대로 일곱 난쟁이의 키를 배열에 담아 출력한다. 입력 예제 1 : [20, 7, 23, 19,10, 15, 25, 8, 13] 출력 예제 1 : [20, 7, 23, 19,10, 8, 13] 해결 방법 전체 난쟁이들 키의 합에서 가짜 난쟁이 두명의 키를 빼면 100이 되야 하는 점을 이용한다. function solution(arr) { let result = []; for (let i = 0; i < arr.length; i++) { for..

문제 설명 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬해 출력한 뒤, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다. # 입력 조건 첫째 줄에 하나의 문자열 S가 주어진다. ( 1

문제 설명 8x8 좌표평면의 특정 한 칸에 나이트가 서 있다. 나이트는 특정위치에서 다음과 같은 2가지 경우로 이동 할 수 있다. - 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 - 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 나이트의 위치가 주어졌을 때 나이트가 이동 할 수 있는 경우의 수를 출력! 행 위치는 1~8, 열 위치는 a~h로 표현 # 입력 조건 첫째 줄에 나이트의 위치가 주어진다. # 출력 조건 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력한다. 입력 예시 출력 예시 a1 2 문제 해결 아이디어 나이트의 8가지 경로를 하나씩 확인하여 각 위치로 이동이 가능한지 확인 리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의 풀이 : input_data = input()..

문제 설명 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. # 입력 조건 첫째 줄에 정수 N이 주어진다. ( 0=6: continue if (i%10)==3 : cnt+=1 continue elif (i//10)%10==3 : cnt+=1 continue elif (i//100)%10==3 : cnt+=1 continue elif (i//1000) %10==3 : cnt+=1 continue elif (i//10000) %10==3 : cnt+=1 continue print(cnt)

구현 ( implementation ) : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 구현 유형의 예시 알고리즘은 간단한데 코드가 지나칠 만큼 어려운 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용된다. 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 백터가 자주 활용된다. ( 0 , 0 ) ( 0 , 1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 1 , 0 ) ( 1 , 1 ) ( 1 , 2 ) ( 1 , 3 ) ( 1 , 4 ) ( ..