본문 바로가기

CodingTest26

👩🏻‍💻 취준하며 공부한 Greedy 유형 총정리 (Python) 그리디 현재 상황에서 가장 좋아보이는 것만을 고르는 알고리즘 Gold 5~ 3 정도의 문제를 풀 정도라면, 왠만한 기업 코테 수준이라고 한다. 👇 그리디 문제 특징 → 똑같은 걸 두번 했을 때 다시 자기로 돌아온다. 그말은 즉, 한 번 한거는 다시 하지 않는다. GREEDY는 사실 유형이 많지 않고, 감으로 맞추는 경우가 많은 유형이다. 아래의 12문제(⭐️ 으로 구분), 2가지 알아 둘 것(✏️ 으로 구분) 을 참고하면 왠만한 그리디 문제에 숙련될 것 이라고 생각한다. ⭐️ 백준 11399 ATM 문제 : 실버 3 (👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 쉬운 문제라 별도 설명 없습니다.) 더보기 N = int(input()) a = list(map(int, input().split())).. 2022. 6. 9.

[필!수!] 백준 코딩테스트 문제 풀기 쉽게 VSCODE 세팅하기 VSCode 코테에 맞게 세팅 백준을 풀다보면, input 테스트 케이스가 엄청 많은 경우가 많다. 그거 일일히 다 하기엔 넘 낭비..니까 input을 파일 형태로 바꿔줄 수 있다. 방법은 아래와 같다. 1️⃣ launch. json 에 아래 추가 "args": ["","output.txt"] 즉, input.txt 파일을 인풋으로 쓸 것이고, 해당 아웃풋은 output.txt 파일에 쓰겠다는 선언이라고 보면 된다. 쉽게, 백준 testcase를 "input.txt"에 넣고, ".py" 를 실행하면 ".py" 내에서 input() 에 대한 것이 "input.txt" 에서 가져와진다는 이야기 이고, ".py" 결과는 "output.txt"에 보이게 된다. 2️⃣ 3분할이 가장 PERFECT하다(개인 의견).. 2022. 6. 9.

Mac VScode C 언어 환경 설정 + VScode 완전 삭제 방법 잘 모르고.. C 언어 extension 만 깔고 이것 저것 만져 놓아서 세팅 값을 모두 삭제 하고 싶은 일이 생겼다. 그래서 먼저, VScode 완전 삭제 하는 방법을 정리하면 1. 응용프로그램에서 VScode 삭제 2. 터미널로 완전 삭제 명령 (base) MacBookPro ~ % rm -fr ~/Library/Preferences/com.microsoft.VSCode.helper.plist (base) MacBookPro ~ % rm -fr ~/Library/Preferences/com.microsoft.VSCode.plist (base) MacBookPro ~ % rm -fr ~/Library/Caches/com.microsoft.VSCode (base) MacBookPro ~ % rm -fr .. 2022. 1. 13.

[Python] DP, 동적계획법 DP, 동적계획법 >> 주어진 문제를 작은 문제로 쪼개서 더 큰 문제의 답을 구하는 것을 반복 하는 패러다임 (분할정복과 비슷하다) 분할 정복과 DP 의 차이는 아래 그림과 같다. Memoization 메모이제이션, 한 번 구한 답들은 저장해두자! >> 부분 문제들의 답을 전역 변수 리스트 같은 것에 넣고 사용할 때마다 꺼내 써야 한다. Top-down ? Bottom-Up? Top-down Bottom-Up 재귀 반복문 큰거 ➡ 작은 거 작은 거 ➡ 큰거 직관적/ 코드 가독성 👍 덜 직관적(문제 따라 다름) 시간-메모리 save 여지 O 백준 문제 풀며 DP 유형 이해 하기 DP 유형은 아래 3가지를 찾겠다는 생각을 하고, 찾은 후 풀어나가야한다. 1. 정의: f(i) = i번째 피보나치 수. 입력 N.. 2021. 5. 19.

[Python] DFS & BFS 그래프나 트리 구조에 대해서 충분한 설명이 있는 글은 아닙니다. python 으로 DFS , BFS 를 구현하는 간단한 코드와 그에 대한 개념을 정리하고 있습니다. 그래프란? - 사용 지도, 네이게이션에 쓰임 SNS, 메신저(팔로우/언팔로우) 깃 VCS 에 쓰임 - 정점(vertext == node) 과 간선(edge)로 이루어져 있음. - 구분 1. 무방향 그래프(==양방향 그래프) 2. 방향 그래프 -------------------------------- 1. 순환 그래프 2. 비순환 그래프 방향성 비순환 그래프(DAG) Directed Acyclic Graph - 연결요소 트리란? - 순환성X, 무방향 - 루트 노드, 리프 노드 - 노드 A에서 노드 B로 가는 경로는 반드시 존재하며 유일하다. 그.. 2021. 5. 12.

[Python]백준 1764 ::듣보잡 문제 풀이 ☝️뭘 사용? 딕셔너리 ✌️어떻게 접근 하고 어떤 것이 중요했나? 중복이 있는 것을 찾아 내야 한다. 첫번째 n 에 대한 값을 받을 때는 중복없이 쭉 들어오기 때문에, 딕셔너리에 key는 이름으로, value는 0으로 추가한다. 두번째 m 에 대한 값을 받을 때는 n에서 받았던 것과 중복이 있을 수 있고 그부분을 잡으면된다. 그부분에 해당하면 result 로 넣는다. result를 정렬해주고, 길이와 result를 출력한다 🤟구현 코드 n, m = map(int, input().split()) dict_n_m = {} result = [] for i in range(n): name = input() dict_n_m[name] = 0 for j in range(m): name = input() keys =.. 2021. 5. 12.

[Python]백준 1874 ::스택수열 문제 풀이 뭘 사용? 스택 두개 어떻게 접근 하고 어떤 것이 중요했나? 스택1은 값들을 넣는 스택이고 스택2는 스택1에서 팝해와서 만들어야 하는 수열을 만드는 스택이다. 먼저, 만들어야 하는 주어진 수열에 pinindex를 설정해서, 해당하는 인덱스의 값을 스택 1에서 찾을 수 있는지를 보고, 없다 하면 1부터 차례대로 추가해준다. 만약에 스택1에 있다면 젤 마지막 값이 원하는 값인지를 보는데, 만약 원하는 값이면 스택1에서 팝해서 스택 2에 넣으면 된다. 만약에 아니면 그건 만들 수 없는 수열이 된다. 구현 코드( 주석 부분은 어떻게 동작하면 되는지 파악 할때 쓰였다.) n = int(input()) stk_n = [] # 이 수열을 만들어야 함 [4,3,6,8,7,5,2,1] stk_1 = [] stk_2 = .. 2021. 5. 12.

[Python]백준 1935 ::후위표기식 뭘 사용? 스택/딕셔너리 풀이.어떻게 접근 하고 어떤 것이 중요했나? 숫자면 스택에 넣고 연산자가 나오면 바로 뒤에 두가지 값을 빼서 연산 후 연산을 마친 값을 스택에 다시 넣어둔다. 젤 마지막 연산이 끝나면 스택에는 결과 값 하나만 남아 있게 될 거고, 그게 값이다. 알파벳에 따른 값을 어떻게 처리 해야할까?딕셔너리..?! 딕셔너리로 아스키 값으로 (차례대로 알파벳이 들어온다고 했기 때문에) 만들어서 스택에 실제로 넣을 값은 맨처음 입력 값에 알파벳에 해당하는 value 값으로 했다. 구현 코드 n = int(input()) string = input() stk_1 = [] dict_real_num={} for i in range(n): dict_real_num[chr(65+i)] = int(input.. 2021. 5. 12.

[Python]백준 1406 ::에디터 문제 풀이 두개 스택 사용 풀이.어떻게 접근 하고 어떤 것이 중요했나? 사실 커서 같은 문제가 딱 나오자마자 이전에 풀었던게 생각나서 스택 2개를 사용해야겠다고 접근했다. LAST IN FIRST OUT 비밀 번호 문제 처럼 커서를 기준으로 스택 2개를 사용하는게 좋다고 생각했다. 앞 스택(stk_1)에 들어온 문자를 다 넣는다. 세가지 값은 알파벳하나니까, else 문으로 'P x'를 뺀다. 왼쪽으로 한칸 커서 옮기는게 들어오면 앞스택이 비어있지 않다면 뒤스택으로 마지막 값으로 어팬드한다. 오른쪽으로 한칸 커서 옮기는게 들어오면 오른쪽 스택이 비어있지 않다면 오른쪽 스택의 마지막 값을 앞스택에 어팬드 한다. 커서 왼쪽에 있는 문자 삭제가 들어오면 앞 스택이 비어이지 않다면 마지막 값을 팝한다. 문자 추가는 앞 스.. 2021. 5. 12.

[Python]백준 2346 ::풍선 터뜨리기 문제 풀이 Idea. 배열 사용. (인덱스 값은 항상 가지고 있으니 빠르게 탐색 가능하다고 생각.) 풀이(어떻게 접근 하고 어떤 것이 중요했나?) 입력받은 리스트 외에 인덱스 리스트도 항상 같이 관리해서 결과에 처음 대로 인덱스를 담을 수 있게 한다. 풍선 속 숫자에 따라 다음 인덱스 값을 정한다. 풍선 속 숫자가 음수이면 인덱스에 풍선 속 숫자를 더한 후 리스트의 길이로 나누면 다음 인덱스가 나온다. 풍선 속 숫자가 양수이면 인덱스에 풍선 속 숫자에서 1을 뺀 것을 더한 후 리스트의 길이로 나누면 다음 인덱스가 나온다. 나온 인덱스로 갱신 하고 두 리스트 모두 pop 해서 처리한다. 리스트의 길이가 0이 될때까지 반복한다. 구현 코드 N = int(input()) list_N = list(map(int, inpu.. 2021. 5. 12.

[Python]백준 1158 ::조세퍼스 문제 풀이 배열 사용. (인덱스 값은 항상 가지고 있으니 빠르게 탐색 가능하다고 생각.) 풀이. 어떻게 접근 하고 어떤 것이 중요했나? N 길이의 1부터 N 까지 채워진 리스트를 만든다. K -1 을 처음 인덱스로 정한다. (리스트 안에가 1부터 시작하니까) K-1 번째 해당 리스트의 값을 pop 해서 꺼내고(리스트 길이 짧아짐)결과 리스트에 넣는다. 계속 뒤로 가야 하기 때문에 방금 인덱스에다가 +K-1을 해준다. 이 때 인덱스가 남아있는 리스트 길이보다 길 수 있는데, 그럴땐 앞으로 돌려 줘야 한다. 이때는 그 긴 인덱스를 남아있는 리스트의 길이로 나눈 나머지를 인덱스로 사용 하면 된다. 리스트가 빌때까지 반복한다. 작성한 코드. N,K = map(int, input().split()) list_N = [] f.. 2021. 5. 12.

[Python]백준11286::절댓값 힙 문제풀이 Solution 👉 minheap을 사용 👉 x가 0 이 아닐 때 heap 에다가 튜플(절대값, 진짜값) 로 값을 넣는다. (자동으로 minheap 형태로 된다.) 👉 x가 0 일때 출력을 해줘야 하는데, 만약 들어있는 값이 없다면 0을 출력해주고 그게 아닐 시에는 pop 해주면 된다.(자동으로 가장 위의 노드인 min 값이 팝 된다.) - 이때 pop 시키면서 해당 튜플 값을 k 변수에 저장해두었다가 k의 인덱스 1번 값을 출력해준다.(절대값 아닌 진짜 값!) TIP 👉 import heapq 👉 sys.stdin.readline 👉 heapq.heappush(리스트, 값) / heapq.heapop(리스트) 👉 heapq 는 리스트를 선언하고 그 리스트를 인자로 넣어 주는 식으로 사용한다는 점! 정답.. 2021. 5. 4.

이전 1 2 3 다음

티스토리툴바