백준 문제 풀이 (심장 뛰는 문제 위주)
1.[백준 #1202]: 보석도둑(python)
\[백준version 1초기에는 간단하게 보석의 가격을 이용하여 정렬하고 가방에 담을 수 있는 무게를 이용하여 정렬을 한 뒤 크기가 작은 가방부터 가능한 최대한 비싼 보석을 담는 방식으로 해결하려고 하였다.하지만 당연하게도 시간초과가 발생하였다.version 2그 다음
2.[백준 #1339]: 단어수학(python)
\[백준이 문제에서 중요한 점은 알파벳의 우선순위를 정하는 것이다. 우선순위를 정하기위해서 입력된 알파벳마다 해당 자리수를 이용하여 가중치를 두었다. 그리고 크기순으로 정렬한 뒤 크기가 큰 순서대로 큰 수를 부여해주면 된다.
3.[백준 #1715]: 카드정렬(python)
\[백준\`\`\`pythonimport heapqimport sysindex = int(sys.stdin.readline())heap = int(sys.stdin.readline()) for \_ in range(index)heapq.heapify(heap)song
4.[백준 #1759]: 암호만들기(python)
\[백준이 문제는 알파벳이 암호에서 증가하는 순서로 배열되어있다고 하니 정렬을 해준 뒤 combination 함수를 이용하여 가능한 모든 조합을 구하고 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어있다는 조건을 만족시켜주는 것만 출력해
5.[백준 #1806]: 부분합(python)
\[백준문제 자체는 간단하다. 하지만 시간제한이 0.5초라는 점을 주목해야한다. 그래서 두 포인터 알고리즘을 사용해야한다.먼저 end포인터를 출발시킨 뒤 해당 값을 더해준다. 만약 더해준 값이 입력해준 값보다 작다면 end포인터를 움직여 값을 증가시켜주고아니라면 sta
6.[백준 #2437]: 저울(python)
\[백준이 문제는 아이디어로 푸는문제이다. 알고리즘은 간단하다. 작은수부터 차례대로 더해주는데 만약 다음 값보다 작다면 이어지지 않는다는 뜻이기때문에 해당값을 출력해주면 된다. 이해가 되지않는다면 아래 링크를 참고하자좋은 풀이
7.[백준 #9663]: N-Queen(python)
\[백준\`\`\`pythonimport sysindex = int(sys.stdin.readline())song = 0 \* indexcount =0def check(row,col): for i in range(row): if songi==col o
8.[백준 #2447]: 별찍기(python)
\[백준이 문제는 재귀함수를 이용하여 해결하여야한다. 재귀적인 방법으로 index//3을 이용하여 index가 3일때 기본 모양을 반환해준다. 그리고 해당 모양을 이용하여 원하는 모양을 찍어주는 방식이다.즉 3의 패턴을 가지고 9의 패턴을 알게되고, 9의 패턴을 가지고
9.[백준 #14719]: 빗물(python)
\[백준해당 코드는 시간복잡도를 생각하지않고 구현한 코드이다. 단순히 직관적으로 블록이 쌓인 모습을 2차원 배열로 구현한뒤 행을 기준으로 차례차례 확인한다. 만약 블록이 쌓인 곳이 아니라면 양쪽에 블록이 있는지 확인하고 블록이 있다면 count를 해주는 모습이다. 하지
10.[백준 #7576]: 토마토(python)
\[백준해당문제는 자료구조 큐를 활용하여 해결하였다. 먼저 익은 토마토의 위치를 큐에 저장한다. 그 다음 pop해준뒤 해당 위치를 기준으로 토마토를 익었다고 처리한다. 이때 중요한 점은 결국 날짜를 출력하여야하니 +1로 처리하여준다. 그리고 해당 위치들 또한 큐에 저장
11.[백준 #3085]: 사탕 게임(python)
\[백준해당 문제는 브루트포스 알고리즘을 활용하여 해결하였다. 모든 사탕의 위치들을 바꾸어 보고 가장 많이 연결 된 사탕의 개수를출력하면 된다. 나는 최대한 효율적으로 구현하기위해 좌우를 기준으로 위치를 바꿀 경우에는 해당 사탕들의 행에대한 검사와 각각의 사탕에 대한
12.[백준 #1062]: 가르침(python)
\[백준해당 문제는 브루트 포스 방식으로 해결할 수 있다. 하지만 시간 초과를 해결하기위해 비트마스킹 기법을 사용해야한다. combinations을 사용하여 a,c,i,t,n을 제외한 문자들로 이루어진 모든 경우의 수를 만들고 비트마스킹 기법을 이용하여 포함관계에 있는
13.[백준 #1700]: 멀티탭 스케줄링(python)
\[백준해당문제는 골드1수준치고는 쉬운문제였다. 그리디 알고리즘을 이용하여 푸는 문제인데 알고리즘 자체는 간단하다.일단 멀티탭에 자리가 있다면 꼽아주고 자리가 부족하다면 멀티탭에 해당 코드가 있는지 검사해준다. 만약 없다면 꼽아야하는 코드중에서 현재 꼽혀있는 코드와 비
14.[백준 #1916]: 최소 비용 구하기(python)
\[백준해당문제는 다익스트라 알고리즘을 활용하면 굉장히 쉽게 풀린다. 중요한 포인트는 효율을 위해 내가 원하는 도시에 최단경로가 확정이 났을경우 출력시켜주고 프로그램을 종료시켜준다.
15.[백준 #1197]: 최소 스패닝 트리(python)
\[백준해당 문제는 최소 신장트리를 크루스칼 알고리즘을 이용하여 구현하여 해결하였다.
16.[백준 #4195]: 친구 네트워크(python)
\[백준해당문제는 서로소집합 자료구조를 활용하여 해결하였다. 하지만 효율적인 구조를 위해 union_parent함수를 수정하였다.count 딕셔너리형 변수를 추가하여 해당 변수에 자식 노드의 개수를 더하도록 설계하였고 해당 변수를 출력한다.
17.[백준 #14890]: 경사로(python)
\[백준이 문제는 아이디어만 잘 생가각하면 쉽게 풀 수 있는 문제이다. 각각의 길을 들고와서 현재 블럭과 이전블럭을 비교한다. 만약 현재 블록과 이전블록의 차이가 1보다 크다면 경사로를 설치할 수 없으니 바로 끝낸다. 만약 -1 또는 1이라면 현재블록이 이전블록보다 작
18.[백준 #1786]: 찾기(python)
\[백준문제 설명에서도 잘 나와있듯이 KMP 알고리즘을 활용하여 풀면 된다. kmp에 대한 설명은 아래 링크를 참고하면 된다.KMP 정리
19.[백준 #1185]: 유럽여행 (python)
백준#1185:유럽여행 > 이 문제는 크루스칼알고리즘으로 해결할 수 있다. 하지만 중요한 점은 가중치를 a + b + (c x 2) 로 계산해야한다. 왜냐하면 MST에서 다시 시작 노드로 돌아오는 경우는 되돌아오는 경우 밖에 없기 때문이다. 하지만 여기서 의문점이 들
20.[백준 #14003]: 가장 긴 증가하는 부분 수열 5 (python)
\[백준\`\`\`pythonimport sysfrom bisect import bisect_leftinput=sys.stdin.readlineN=int(input())L=list(map(int,input().split()))dp_table=-float('inf')st
21.[백준 #11723]: 집합 (python)
\[백준해당 문제는 비트마스킹기법으로 해결하면 되는 문제이다. 하지만 배열을 이용하여 풀어도 시간과 메모리가 별 차이없는 모습을 보인다.
22.[백준 #1525]: 퍼즐 (python)
\[백준해당 문제는 기본적인 bfs문제이다. 하지만 중요한점은 2차원 배열으로 처리할 경우 시간이 오래 걸린다. 그래서 문자열로 처리해야한다.
23.[백준 #12865]: 평범한 배낭(python)
\[백준해당 문제는 전형적인 다이나믹 프로그래밍 문제이다. 위에 사진을 보면 이해 될 것이다.
24.[백준 #17484]: 진우의 달 여행(python)
\[백준다이나믹 프로그래밍을 활용해서 풀었다. 실버 문제이긴 하지만 생각보다 어려운 문제라 기술하겠다.각각의 위치값을 저장할때 사용하는 리스트에 방향을 담는다는 아이디어만 생각하면 풀 수 있다.현재 위치 값을 계산하려면 이전 방향에서 왼쪽대각선으로 오는지 아래로 오는지