본문 바로가기

Coding Test

 (17)
[Algorithm] DP(Dynamic Programming) DP: 동적계획법 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 구현 탑다운: 하향식 재귀함수 이용 메모리제이션: 한 번 계산한 결과를 메모리 공간에 메모하는 기법 (캐싱) 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴 - 한 번 계산된 결과를 담아 놓기만 하고 사용안할수도 ? 보텀업: 상향식 먼저 계산한 문제를 사용 반복문 사용함 DP테이블: 저장용 리스트 조건 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결 피보나치를 다이나믹 프로그래밍으로 생각하기 - 탑다운: ..
[카카오기출] 프로그래머스_튜플_Lv2 https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 여기서 중요한 점은 어떤 순서로 각원소들을 저장할 것이냐인듯하다 만약 원소의 갯수가 4개라면 1개, 2개, 3개, 4개로 나뉘므로 나는 해당 집합을 길이로 정렬시켜줬다. 그리고 각각의 1개, 2개, 3개, 4개의 원소들을 돌면서 answer에 순서대로 값을 넣어주게 했는데, 리스트로 바꿔서 리스트의 원소 유무 방법인 'in'연산자를 사용하니 매우 간단하게 문제가 풀렸다. answer에 1개,..
[소프티어] 장애물 https://softeer.ai/practice/6282 Softeer - 현대자동차그룹 SW인재확보플랫폼 자율주행팀 SW 엔지니어인 당신에게 장애물과 도로를 인식할 수 있는 프로그램을 만들라는 업무가 주어졌다. [그림 1] 지도 예시 우선 [그림 1]과 같이 정사각형 모양의 지도가 있다. 1은 장애물이 softeer.ai from collections import deque N = int(input()) visited = [[0 for col in range(N)] for row in range(N)] ground = list() def bfs(x, y): queue = deque() queue.append((x, y)) visited[x][y] = 1 cnt = 1 while(queue): x, y..
[BFS&DFS] 프로그래머스_미로찾기 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def bfs(x, y, maps): dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque() queue.append((x, y)) while(queue): x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx < 0 or..
[BFS&DFS] 백준_2583_영역구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 입력 풀이 처음에는 좌표로 왼쪽 아래에서 시작해야할 것 같아서 이 그림을 어떻게 뒤집을까 고민했는데 생각해보니 왼쪽 위에서부터 시작하면 그냥 아래에 거울 둔것처럼 뒤집히기 때문에 영역(너비)구하는데에는 무리가 없어서 2차원 배열로 풀어줬음! 사용 알고리즘 : BFS 이 문제를 처음 보자마자 든 생각은 좌표에 해당하는 직사각형 너비는 다 1로 만들어주고 직사각형 너비에 해당..
[DFS&BFS] 백준_1303_전쟁전투 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 문제 입출력 풀이&사용알고리즘: BFS 그래프 직접 만들어주기 w,b의 그래프 따로 만들어주기 w, b 에 해당하는 bfs 개별적으로 이루어지도록 하고 접수 넣어주기 전체코드 from collections import deque def bfs(x, y , maps): queue = deque() queue.append((x, y)) checked_list = list() ..
[1주차] 스터디 시작 및 완전탐색 https://cordelia-gg.notion.site/CodingTest-af544713dee444949693a52479a951ba CodingTest 🥇 스터디 목표: 원하는 기업 들어가기 🙏🏻 cordelia-gg.notion.site
CHAPTER5. DFS/BFS 1. 꼭 필요한 자료구조 기초 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조 push(데이터 삽입), pop(데이터 삭제) 오버플로: 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입연산을 수행할 때 발생 언더플로: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태 스택: 선입후출, 후입선출 append(): 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입 pop(): 리스트의 가장 뒤쪽에서 데이터를 꺼냄 큐: 선입선출 구조 리스트 자료형에 비해 효율적 스택과 큐의 장점을 모두 채택한 것 deque 객체를 list자료형으로 변경하고자 하면 list() 메서드..

티스토리툴바