백준 풀이
1.[Python] 백준 1946번: 신입사원
문제의 핵심은 "다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. "입니다.
2.[Python] 백준 9375번: 패션왕 신해빈
문제의 핵심은 "같은 종류의 의상은 하나만 입을 수 있다" 입니다.
3.[Python] 백준 10989번: 수 정렬하기 3
풀이 전략은 다음과 같습니다.메모리 제한이 8MB로 매우 작습니다.하지만 정렬해야 하는 수의 개수가 $$1 ≼ N ≼ 10,000,000$$으로 매우 많기 때문에 내장된 sorted 함수를 쓰면 메모리 초과가 뜨는 문제인데요!이 문제처럼 메모리를 적게 사용해야 할 때는
4.[Python] 백준 2108번: 통계학
풀이 전략은 다음과 같습니다.수의 최댓값, 수의 최솟값, 최빈값은 입력 데이터간의 관계를 고려하지 않고, 수행 과정에서 최댓값/최솟값을 선택하는 그리디 알고리즘을 이용합니다.최빈값은 수 n의 빈도 수를 \_count\[4000+n]에 저장하고,진행 과정에서 최대 빈도
5.[Python] 백준 18870번: 좌표 압축
풀이 전략은 다음과 같습니다.N개의 숫자를 순서가 바뀌지 않게 0, 1, 2, ... 와 같은 수로 대체해주면 되는데요!압축 전의 숫자를 key로, 압축 후의 숫자를(0, 1, 2, ... ) value로 가지는 dictionary를 정의해서 매칭되는 숫자의 쌍을 정
6.[Python] 백준 14501번: 퇴사
풀이 전략은 다음과 같습니다. 이 문제는 DP 알고리즘 문제입니다. DP 알고리즘 문제임을 어떻게 알아챌 수 있나요? 최대 이익을 구하기 위해선, 1일부터 N일까지 가능한 모든 상담일 조합을 계산하여 최대값을 구해야 합니다. (금액) / (소요기간)이 높은 순서대
7.[Python] 백준 4949번: 균형잡힌 세상
풀이 전략은 다음과 같습니다.( 가 있다면 다음 괄호는 ) , 가 있다면 다음 괄호는 가 되겠죠?괄호 문제는 스택을 활용하는 대표적인 유형이므로, list를 활용하여 스택을 구현해보겠습니다.입력의 종료 조건이 "온점 하나"라고 되어있네요. 종료 조건이 명시된 문제라
8.[Python] 백준 10757번: 큰수 A+B
풀이 전략은 다음과 같습니다.두 정수 A와 B의 크기가 매우 크네요!단순히 A + B를 print하게 되면 시간 초과가 발생합니다.그렇다면 어떤 방법을 사용하면 될까요?일의 자리부터 두 수의 같은 자리끼리 더하고 더한 값이 10이 넘어가면 carry flag를 만들어
9.[Python] 백준 1158번: 요세푸스 문제
풀이 전략은 다음과 같습니다.1번에서 N번의 사람들이 모두 제거될 때까지 반복하며 요세푸스 순열을 구해야 하는데요,1번에서 N번까지 순회한 다음, 다시 1번으로 돌아가는 과정을 어떻게 구현하면 좋을까요?큐를 이용하면 N번까지 순회한 후 다시 1번으로 돌아가는 과정을 편
10.[Python] 백준 18111번: 마인크래프트
풀이 전략은 다음과 같습니다.땅 높이의 범위가 0~256으로 명시되어 있기 때문에 활용해보겠습니다.땅의 높이가 k일 때의 소요 시간을 time\[k] 에 저장합니다.또한 현재까지 소요 시간이 가장 작은 땅의 높이를 height에 저장합니다.for문으로 g를 0에서 25
11.[Python] 백준 17451번: 평행우주
풀이 전략은 다음과 같습니다.문제가 살짝 헷갈리는데요, 예시를 따라가보며 정리해보겠습니다.예시에서 행성을 통과하는 데 필요한 속도가 각각 300 400 500 400 300이라고 되어있습니다.필요한 속도가 300 400 500 400 300이며, 필요한 속도의 양의 정
12.[Python] 백준 5427번: 불
f와 s의 bfs를 분리하는 코드가 많았는데,저는 f -> s 순으로 큐에 삽입하여 한번에 bfs를 돌았습니다.방문체크는 f는 \*로, s는 @로 표시했고,(nx, ny)의 값이 . 혹은 @이면 불이 번지도록 했습니다.최단 경로, 최단 시간을 bfs로 구하기 위해서는
13.[Python] 백준 1931번: 회의실 배정
시작 시간과 끝나는 시간이 $2^{31}-1$보다 작거나 같은 자연수 또는 0인 문제입니다. dp 배열을 생성한다면, 아마 메모리 초과로 실패가 뜰 것입니다. 그렇습니다... dp인줄 알았으나 그리디였던 문제였습니다. 그리디로 풀려면 회의 시간들을 어떻게 정렬해야
14.[Python] 백준 2457번: 공주님의 정원
최소의 꽃들만 선택해서 3월 1일부터 11월 30일까지 매일 꽃이 피어 있도록 해야 하는 문제입니다.가장 최근에 심은 꽃이 latest_date 날에 진다고 가정했을 때,현재의 꽃에 대해 피는 날짜 <= latest_date < 지는 날짜 이 성립한다면이전에
15.[Python] 백준 11501번: 주식
그리디를 이렇게도 적용할 수 있구나 싶은 문제여서 한번 정리해보려고 합니다.주식에서 최대 이익을 내는 방법은 아래의 과정을 반복하는 것입니다.최대 주가에서 주식을 판다.그 이후의 주가들 중, 최대 주가에서 주식을 판다....예를 들어 1, 3, 2, 5, 1, 4, 2
16.[Python] 백준 4179번: 불
이 문제는 불이 여러 곳에서 날 수 있다는 점과불 -> 지훈 순으로 bfs를 수행해야 한다는 점을 캐치하면 쉽게 풀 수 있는 문제였습니다.
17.[Python] 백준 1941번: 소문난 칠공주
이 문제는 dfs를 이용해서 중복없는 조합을 모두 구하고,bfs를 응용해서 인접한 조합인지 여부를 확인하여 풀 수 있습니다.(0,0), (0,1), ... , (4,4)의 크기가 25인 리스트를 정의한 후, 이들 중 7개를 중복없이 선택하는 조합을 구함조합에서 'S'의