백준
1.백준 16397 탈출
bfs + 약간의 구현.버튼 B연산의 예외 처리에 대해 조금 고민을 해봐야 함.코드를 더 깔끔하게 만들기 위해 B연산은 따로 getNext 함수로 계산함.
2.백준 17425 약수의 합
n도 백만에 테케도 십만이라 시간초과를 고려해서 풀었으나 시간초과가 떴다...첫 번째 풀이시간 내에 통과하기에는 어림도 없었다.두 번째 풀이전처리 과정에서 O(n√n) 시간복잡도를 가져 아슬아슬하게 통과하지 않을까 했는데 시간초과가 떴다.계속 고민하다가 a의 배수는 a
3.백준 17396 백도어
신경 써줘야 할 조건들이 꽤 있었던 dijkstra 문제이다.1\. 거리들의 합이 int 범위를 벗어난다는 점2\. dist\[now] < cost인 경우 continue를 해야하는 점3\. 시야에 보이는 분기점에 갈 수 없는 조건을 전처리하는데 도착지점은 예외
4.백준 1038 감소하는 수
일단 나는 처음에 문제를 어떻게 풀어야 할 지 감을 잡기 위해 작은 자리수부터 차례대로 감소하는 수를 나열했다. 한 자리 : 0 1 2 3 4 5 6 7 8 9 두 자리 : 10 20 21 30 31 32 ... 97 98 세 자리 : 210 310 320 321 41
5.백준 11509 풍선 맞추기
자기 자신보다 1이 큰 원소는 개수를 세지 않는 게 문제의 핵심이다.구현 난이도는 매우 쉬운 편이고 난이도는 사람마다 편차가 심할 것 같다.
6.백준 1484 다이어트
나는 이 문제를 수학적으로 접근했다.A = 이전 몸무게, B = 현재 몸무게라고 할 때,B^2 - A^2 = G를 만족하면 된다.위 식을 정리하면,(B - A)(B + A) = G를 만족하고 우변이 자연수이고 B와 A는 정수이고 (B + A) > 0를 만족한다.따라서
7.백준 9663 N-Queen
예전부터 잘 안 풀렸던 문제인데 오랜만에 다시 시도해보니 통과했다. 어떻게하면 시간초과가 나지 않을까 고민을 했다. 편의상 행 = row, 열 = col, 오른쪽 대각선 = rdiag, 왼쪽 대각선 = ldiag라고 하겠다. 우선 row는 dfs 함수의 paramete
8.백준 17175 피보나치는 지겨웡~
dp 정복 프로젝트 day 1굳이 설명할 필요가 없는 문제다.
9.백준 1987 알파벳
알파벳 방문관리를 하며 백트래킹을 수행하면 되는 문제이다.알파벳은 'A' ~ 'Z'까지 있고 이를 0 ~ 25의 숫자로 대응시킨다.
10.백준 13023 ABCDE
깊이가 5에 도달했을 때(코드 구현 상으로는 4) 1을 출력하고 종료하면 되고 도달하지 못했을 경우 0을 출력하면 되는 문제이다.모든 경우에 대해 따져봐도 2,000 \* 2,000 = 4,000,000 약 4백만밖에 되지 않기 때문에 그냥 하고싶은 대로 하면 된다.
11.백준 14940 쉬운 최단거리
목표지점 까지의 거리 = 목표지점에서 각 지점까지의 거리임을 생각해내면 쉬운 문제.
12.백준 20529 가장 가까운 세 사람의 심리적 거리
비둘기집 원리에 대해 배울 수 있는 좋은 문제였다.그리고 나는 처음에 모든 MBTI를 0~15 사이의 숫자로 변환한 뒤 xor하는 방법으로 심리적 거리를 계산했는데 오히려 이 방법이 문자열을 비교하는 방법보다 4배나 느리다는 것을 확인하고 비트연산으로 풀 수 있는 문제
13.백준 21736 헌내기는 친구가 필요해
board를 string으로 관리하는 정석적인 DFS/BFS 탐색 문제.
14.백준 1167 트리의 지름
모르면 풀기 어려운 문제다. 임의의 정점에서 최대 거리를 갖는 정점을 찾은 뒤 그 정점에서 다시 최대 거리를 갖는 정점까지의 거리가 트리의 지름이다. 이에 대한 증명은 여기 클릭.어쨌든 아이디어를 안 이상 구현은 어렵지 않은 문제였다.
15.백준 1753 최단경로
유명한 dijkstra 문제이다.나는 처음에 두 정점 사이에 여러 간선이 있을 수 있다. 라는 조건 때문에 두 정점 사이에 여러 간선이 있을 경우 최단거리만 저장하는 방식으로 코드를 짰다. 코드는 다음과 같다.그런데 어차피 최단거리를 찾는 과정에서 두 정점 사이에 여러
16.백준 1238 파티
다익스트라 알고리즘은 한 정점에서 나머지 정점들까지의 최단거리를 구하는 알고리즘이다.이를 응용하면 그래프를 역방향으로 저장할 경우 나머지 정점들에서 한 정점으로의 최단거리를 구할 수 있다.
17.백준 1504 특정한 최단 경로
최단거리의 합 = 최단거리임을 파악하기.1\. v1 == 1 || v2 == n2\. 간선의 개수 = 0이 두 가지 케이스에 대한 체크만 해주면 쉽게 풀리는 문제이다.
18.백준 17266 어두운 굴다리
가로등의 위치는 불규칙한 간격을 가지고 놓여 있다. 이 때 모든 굴다리를 비추기 위해서는 가로등 사이의 간격이 가장 큰 것을 찾으면 된다. 왜냐하면 가로등 사이의 간격이 가장 클 때를 기준으로 해 가로등의 높이를 설정하면 나머지 간격들은 무조건 비출 수 있기 때문이다.
19.백준 1057 토너먼트
나는 처음에 이 문제를 다음과 같은 과정을 통해 해결했다.1\. 서로 떨어지면 떨어질수록 나중에 붙는다(라운드 번호는 커진다)2\. 그렇다면 어느정도 떨어질 때 라운드가 커지는가?3\. 토너먼트니까 2의 거듭제곱과 관련이 있지 않을까?4\. n = 16일 때, 1~8과
20.백준 1940 주몽
n <= 15,000이라는 조건을 보고 O(n^2)풀이도 통과하겠다 싶어 bruteforce로 먼저 풀었다.92ms로 통과했다.근데 너무 쉽게 통과해서 뭔가 더 빠른 풀이가 없을까 생각해보았다.1\. 우선 정렬을 생각해보았다.2\. 하나의 숫자를 a라고 하면 다른