알고리즘 공부방

https://www.acmicpc.net/contest/view/999 2023 SCON Open Contest 사용 가능한 언어 C++17 Python 3 C11 PyPy3 Java 15 www.acmicpc.net 대회 때는 4문제 밖에 풀지 못 했지만, 업솔빙을 했고, 총 7문제를 풀었다. A -정보섬의 대중교통 단순 사칙연산 문제 b - n + n 소스코드 B - 팀명 정하기 단순 정렬문제 소스코드 C - 등차수열의 합 N = 1이면 무조건 가능하고, N > 1이면 배열 안이 정확이 K만큼 증가한다면 무조건 가능하다. 출력해주는 방법은 다양한다. 소스코드 D - 선택 정렬의 이동 거리 구현 문제였다. 나같은 경우는 정렬과 맵 자료구조를 이용하여 정렬 전 상태와 정렬 후 상태를 비교하여 그 거리를..

S사의 하계인턴쉽 코딩테스트를 오늘 12시에 봤다. CS문제와 코딩 문제, 이렇게 총 50문제가 출제되었고, 시험 시간은 1시간이었다. 내 전략은 코딩 문제같은 경우는 금방 풀 수 있을 것이기에 제일 먼저 코딩 문제를 다 풀고, CS문제를 보자는 전략이었다. 먼저 코딩 문제는 총 5문제가 나왔었다. 1번 기본 구현 기본적인 10진법과 16진법을 활용하는 문제였다. 2번 구현 배열을 주어주고 이 배열 등차수열인지 아닌지를 판단하는 문제였다. 3번 그래프 + 구현 문제 지문이 진짜 이상한 문제였다. 지문이 이해가 안되서 몇 분동안이나 계속 읽기만 했다 그냥 그래프 탐색에 구현섞인 문제였다. 4번 정렬 두 개의 배열을 주고 두 개의 배열을 합칠 때 중복되는 것을 빼고 합친 뒤 정렬해주면 되는 문제였다. 5번 ..

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 알고리즘 분류: Math, 유클리드 호제법 문제 풀이 먼저 입력 값과 시간을 보면 일일이 다 확인하는 브루트포스로는 풀 수 없다는 것을 알 수 있다. n이 100이고, 최대로 입력되는 값이 10억이므로 브루트포스로는 풀 수 없음을 알 수 있다. 그러면 이 문제는 수학적으로 접근을 해야한다는 것인데, 이 문제를 수식으로 써보면, 먼저 모든 수의 나머지가 같은 경우를 간단히 생각해보면 모든 수가 나누어 떨어지면 된다..

https://www.acmicpc.net/contest/view/994 2023 부산대학교 CodeRace Open Contest www.acmicpc.net 근로장학하는 중에 심심해서 한번 풀어보았다. 시간은 11시 ~ 14시까지 했고, 12시 ~ 1시 동안은 점심을 먹었다. A - 첨탑 밀어서 부수기 단순 구현 문제였다. 현재 위치의 높이가 다음 높이의 위치보다 높은 것을 세어주면 된다. (살짝의 실수로 5분정도 걸림) 소스코드 B - 영역 색칠 그리디와 case-work느낌이 나는 문제였다. 붓을 가로방향으로만 칠할 수 있으므로, 각 행마다의 열만 체크해주면 되는데, 여기서 색깔이 칠해져있는지, 안 칠해져있는지, 칠해져있다면, 같은 색깔인지 다른 색깔인지를 판단하고, 다른 색깔이면 개수를 세어준다..

https://www.acmicpc.net/contest/view/927 보드게임컵 www.acmicpc.net 이번 대회에서 5솔을 했다. 1시간 뒤에 들어간 것과, D번에서 진짜 바보같은 실수를 한 것 때문에 잘 못 했다. A - 노 땡스! 단순 구현 문제 AC - 1:02 소스 코드 B - 할리갈리 map 자료구조를 사용하면 쉽게 풀림 (map을 쓰지 않고, 입력받은 문자열의 앞글자 만으로도 풀림) AC - 1:04 소스 코드 C - 크레이지 타임 이 문제 또한 단순 구현 문제이다 AC - 1:18 소스 코드 D - Yacht Dice 이 문제가 이번 대회의 문제점이었다. 문제 자체는 그냥 단순 구현 문제였다. 하지만 바보같이 i와 j를 바꿔쓴 탓에 계속 WA를 받고 있엇다. 이것을 발견하기까지 1..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 유형: DP, Math 문제 풀이 생각을 했을 때 n이 주어지면, (n - n보다 작은 수 중 가장 큰 제곱 수)의 dp값에서 +1을 해주는 것이 정답이라 생각했다. 그러다 충분히 반례가 존재할거라 생각하여, (n - n보다 작은 수 중 제곱수인 수)의 dp값 + 1 중 가장 작은 것이 정답이라 생각했다. 1부터 n까지 바텀업 방식으로 dp를 돌린다. ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 유형: DFS, DP 문제 풀이 이 문제는 dfs로 돌리면서, 오른쪽 끝점까지 갔던 경로를 dp로 저장하면서 푸는 문제이다. 예를 들어 (3,3)에서 (10,10)으로 가는 경로가 3이라 했었을 때 (1,1)에서 출발하여 (3,3)에 도착하면, (10,10)까지 가지 않아도 경로를 알 수 있게 되는 것이다. 전체 코드 import java.io.*; import java.util.*; public..

백준을 시작한지 223일 만에 플레5 달성했다!