선택과 집중

목차 문제 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 설계&풀이 이전에 백준에서 풀었던 이중 우선순위 큐에서 힙을 사용했기에, 힙 사용법을 대략적으로 파악하고 있어서 큰 어려움은 없었다. 설계는 다음과 같이 했다. 1. scoville 배열만큼 heap 배열에 담아주고, 해당 배열을 heapq로 힙 형태로 전환시켜준다. heappop() 을 사용하면 가장 왼쪽(0번인덱스) 가 추출됨과 동시에..

목차 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 설계&풀이 가장 기초적인 DFS/BFS 문제다. 이전에 비슷한 문제를 풀어서인지, 동일한 폼으로 풀 수 있었다. 풀면서 새로 안 사실이 있는데, 파이썬에선 전역변수 설정을 별도로 해줘야 하는 것이었다. dfs와 bfs 함수 안에 cnt로만 해두면 알아서 전역변수로 찾아가는건줄 알았는데, 그게 아니라 global로 선언해줘야 되더라; 몰랐음.. 기초적인 문제다보니 특별한 설명은 필요없을듯 하다..

목차 문제 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 설계&풀이과정 먼저 시간초과가 난 내 코드다. import sys # 시간초과 풀이 n, m = map(int, input().split()) hPeople = [ sys.stdin.readline().rstrip() for _ in range(n) ] sPeople = [ sys.stdin.readline().rstrip() for _ in range(m) ] answer = [] ..

목차 이 글은 Notion에서 작성 후 재편집한 포스트입니다. 개요 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다 다익스트라 최단 경로 알고리즘은 ‘음의 간선’이 없을 때 정상적으로 동작한다. 음의 간선이란, 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 ‘가장 비용이 적은 노드’를 선택해서 임의의 과정을 반복하기 때문이다. 참고 https://www.youtube.com/watch?..

목차 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 설계 및 풀이 DP 문제이다. 사실 문제 유형을 어떻게 알아내는지는 좀 더 문제를 풀어봐야 알 것 같다. 처음엔 재귀로 풀었는데, 재귀로 풀다보니 시간 초과가 되어서 뭘까 고민하다가 결국 답지를 봤는데.. DP더라... 먼저, 재귀로 푼 코드다. cntZero = 0 cntOne = 0 def fibonacci(n): global cntZero global cntOne if n == 0: cntZero += 1 return 0 elif n == 1: cntOne += 1 return..

이 글은 Notion에서 작성 후 재편집한 포스트입니다. 목차 개요 업무를 진행하면서 뽑기 확률로 진행되는 이벤트에 관한 로직을 짜야했다. 고정적인 값으로 들어오는 확률로 뽑는건 너무 단순해서 구글링하면 많이 나오지만, 가변리스트의 경우는 생각보다 별로 없어서 그냥 나름대로 한번 만들어봤다. 짱구를 좀 굴려봤다. 확률 알고리즘이 대충 어떤느낌으로 돌아가는지만 알아보고 나머지는 직접해봤다. 혹시 더 좋은 방법이 있다면 댓글 부탁드립니다. 참고 yoonbumtae.com/?p=518 Java 예제: 랜덤박스 (Math.random 이용) - BGSMM 일본산 온라인 과금 게임같은 경우 랜덤박스로 카드를 뽑을 수 있는 시스템이 있습니다. 여기서 나오는 카드의 등급은 희소성을 기준으로 SSR(Super-supe..

목차 목차 1번목차입니다 1.1번 목차입니다. 본문본문 블라블라 ㅂ바바바 본문우웅눙 1.2번 목차입니다. 본문쓸말 블바륿랍랄 2번목차다 쓸말 할말 랄랄랄 응ㅇ잉잉애ㅐㅇㅇ이 2.1번 목차다 쓸말이야 으아앙 3번 목차다 3.1번 목 차차찻

문제 www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B > up >> down >> top; int answer = top / (up - down); cout = top ? answ..

문제 www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌�� www.acmicpc.net 설계 먼저 이 벌집의 규칙성은 다음과 같다. 이 그림에서, 같은 크기의 방 (같은 색깔로 색칠 된 곳)을 도는 수 즉, 층을 i라고 가정할 때 i 가 1일때는 1 (예외처리) i 가 2일때는 2~7 i 가 3일때는 8~19 .... 의 범위 안에 숫자들을 포함한다. 즉, 1층엔 1, 2층엔 2~7 3층엔 9~36번의 숫자가 포함된다. 그리고 층이 끝나는 지점의 숫자를 기점으로 나열해본다면. 이런 규칙성을 찾을 ..

문제 www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 설계 처음엔 굉장히 쉬운문제라고 생각했다. 그래서 while문을 돌렸다 대부분의 사람들은 아마 보자마자 나처럼 생각했을 것이다. "그냥 1000 + 70*n < 170*n 조건으로 while문 돌리면 풀겠는데?" 라고 생각했는데, 결과는 시간초과였다. 그렇게 무식하게 풀지 말란 소리였음. 그래서 짱구를 열심히 굴려봤다. 그래서 다음과 같은 결론을 도출했다. 물건의 가격이 170이고, 가변비용이 70이므로 고정비..