BUILD_SSO

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 예제 입력: players = ["mumu", "soe", "poe", "kai", "mine"] callings = ["kai", "kai", "mine", "mine"] 예제 출력: result = ["mumu", "kai", "mine", "soe", "poe"] 풀이 해설진은 선수들이 자기 바로 앞의 선수를 추월할때 추월한 선수의 이름을 부른다. 결기가 끝난 후 선수들의 이름이..

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/136798 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 예제 입력: 5 3 2 10 3 2 예제 출력: 10 21 풀이 프로그래머스 레벨 1 문제라 그런지 문제 자체는 간단하다. number 범위에 해당하는 각 숫자의 약수를 구하고, 그 약수의 개수가 제한 수치를 넘는지 확인하여 적절한 무기의 공격력을 결정한 뒤 필요한 철의 무게를 누적하면 되는 문제이다. 처음 작성한 코드: def solution(number, limit, power):..

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/142086 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 예제 입력: "banana" "footbal" 예제 출력: [-1, -1, -1, 2, 2, 2] [-1, -1, 1, -1, -1, -1] 주어진 문자열 's'에 대해 문자열 내에서 이전에 나타난 위치와의 차이를 계산하고, 그 결과를 answer로 return하는 문제이다. 파이썬 내장함수인 enumerate와 dictionary 타입을 쓰면 문제가 쉽게 해결된다. enumerate..

문제링크: https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 예제 입력: 3 1 예제 출력: 1 2 3 🔵백트래킹 백트래킹 이론을 아무리 봐도 이해가 가지 않아 N과M 문제의 코드를 먼저보고 분석해보았다. 백트래킹이란 DFS에 기반을 두고 있는 전략으로, 불필요한 경우를 배제하며 원하는 답에 도달할 때까지 탐색하는 알고리즘이다. DFS를 기반으로 하고있기 때문에 스택(stack)을 이용해 퇴각하며 다음 탐색을 진행한다. 백트래킹 같은 경우 기본..

문제링크:https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 예제 입력: 4 0 1 2 3 4 0 5 6 7 1 0 2 3 4 5 0 예제 출력: 0 예제 입력: 6 0 1 2 3 4 5 1 0 2 3 4 5 1 2 0 3 4 5 1 2 3 0 4 5 1 2 3 4 0 5 1 2 3 4 5 0 예제 출력: 2 문제유형: 백트래킹, 조합 풀이 스타트팀과 링크팀의 능력치 차이의 최솟값을 구하는 문제이다. + 백트래킹은 아직 감이 안 잡혀서 처음에 백트래킹 유형이라는 것을 ..

문제링크:https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 예제 입력: 2 5 6 0 0 1 0 예제 출력: 30 30 문제유형: 백트래킹, 구현, DFS 풀이 사칙연산의 모든 경우를 탐색하여 최댓값과 최솟값을 구하는 문제이다. 문제에서 구하고자 하는 것은 주어진 사칙연산을 이용하여 만들 수 있는 모든 결괏값 중 최대와 최소이다.(output) 풀이하며 엄청 헤맸던 문제 중 하나이다.. 단순..

🔵구현(시물레이션과 완전탐색(brute force)) #구현 - 머리속에있는 알고리즘을 소스코드로 바꾸는 과정 - 구현 유형의 문제란? => 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 뜻함 - 일반적으로 알고리즘 문제에서의 2차원 공간은 '행렬(matrix)'의 의미로 사용된다. => 행렬에서는 왼쪽상단이 (0, 0) 지점이다. - 시물레이션 및 완전탐색 문제에서는 2차원 공간에서의 '방향 벡터'가 자주 활용돤다. => 세로축; x(위 방향;- / 아래 방향; +), 가로축; y(좌; - / 우; +) => dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0] 🔵브루트포스(brute force) - 가능한 모든 조합을 다 탐색한다.(답이 나올때까지) -답을 무조건 찾을수는..

🔵탐욕법 #1 - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 정당성 분석이 중요 => 문제에서 요구하는 최적의 해를 구할 수 있는지 검토하는 것이 중요하다. #2 - 내 상황에서 가장 큰값을 고르는 알고리즘이라고 볼 수 있다. #3 - 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. - 코딩테스트에서는 그리디알고리즘, 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 출제하는 경우가 많다. 거스름돈 n = int(input()) #1260원 일 때 count = 0 array = [500, 100, 50, 10] for i in array: #화폐의 종류만큼 for문이 반복된다. count += n // i #1. 500원으로 2번만큼 거슬러줄 수 있다. n %= i ..

문제링크: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 예제 입력: 4 6 101111 101010 101011 111011 예제 출력: 15 풀이 과거에 풀었던 문제를 DFS/BFS 복기할겸 다시 풀어보았다. 최단거리라고 생각해서 DFS문제라고 생각했는데 과거에도 똑같은 방식으로 실수했던 기록이 있었다...(도대체 왜?) 문제를 다시 파악하고 BFS로 풀이하였다. 좌측 상단(1, 1)에서 우측 하단(4, 6)으로 이동하는 최소의 칸 수를 구하는 문제이다. 이것을 pyth..

📌DFS, BFS를 알아보기전 알아야하는 자료구조와 개념 탐색(search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 스택(stack) - FILO(First In Last Out): 박스 쌓기 - list로 간편하게 구현 가능(삽입: append, 삭제: pop) - 시간복잡도: O(1) 큐(queue) - FIFO(First In First Out): 입구랑 출구가 모두 뚫려있는 터널 - from collections import deque(삽입: append, 삭제: popleft) - 시간복잡도: O(1) 재귀함수(recursive function) - 자기 자신을 다시 호출하는 함수 - python 에서는 '최대 재귀 깊이 제한'이 있기 때문에 별다른 설정이 없다면 오류메세..