본문 바로가기
반응형

Algorithm 알고리즘18

[BOJ] 백준 2178 미로탐색 알고리즘 재활 훈련을 하고 있다..그래서 풀어본 문제부터 다시 풀어보면서 풀이법도 다르게하고 하나씩 하나씩 낱낱이 파악하면서 분석하는 형태로 진행하려한다.시간이 조금 오래걸려도 결국 이렇게 진행하는게 다시 실력을 끌어올리는 것에는 가장 빠른 시도일 것이라 생각한다.내가 이전에 미로탐색을 푼 내용은 아래 링크에 있다.https://coder-angrybird.tistory.com/32 [백준]BOJ_2178_미로 탐색_S1https://www.acmicpc.net/problem/2178 2178번: 미로 탐색첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.www.accoder-angrybird... 2024. 9. 23.
[코드트리] 왕실의 기사 대결 feat. JAVA 삼성 코딩테스트 대비로 한 문제씩 풀어보려고 한다.회사 다니면서 준비하느라 시간을 많이 할애하지 못해서 그냥 생각해보는 것에 의의를 두고 하려고 한다.문제를 보고 한시간 안에 못하면 그냥 답을 보고 답지를 만들어보는 방식으로 준비하려고 한다.오늘은 삼성 SDI 현직자 친구가 기출 중에 추천해준 문제인 '왕실의 기사 대결' 이다.https://www.codetree.ai/training-field/frequent-problems/problems/royal-knight-duel/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.. 2024. 9. 4.
[백준] 1920번 : 수 찾기 - JAVA [자바] 백준 1654번 랜선 자르기 문제를 다시 풀려니까 기억이 안나서 찾아보다가이 문제까지 들어오게 되었다.https://www.acmicpc.net/problem/1920 1920번: 수 찾기첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들www.acmicpc.net 이 문제를 통해서 이분 탐색에 대한 개념부터 다시 잡아가려 한다.아래 내용은 https://st-lab.tistory.com/261 이 블로그의 해설을 보며 정리한 내용이다.먼저 이분 탐색이란 무엇인가.이분 탐색은 이진 탐색이라고도 불린다.가장 쉬운 예.. 2024. 3. 6.
[백준] 1654번 : 랜선 자르기 오랜만에 다시 알고리즘을 시작했다.사실 매일 해야하는 것이지만 너무 하기가 싫었고,운동도 어떤 습관도 다 그렇지만 관성이 있어서 계속해서 하다보면 하게되고 안하다 보면 안하게 되기에...여튼 그래서 다시 시작하다가 이분탐색을 사용하는 문제에서 막혀서 정리하려한다.답안을 본 문제들은 이렇게 블로그에 정리를 하는 것을 목표로 하려 한다.먼저 랜선 자르기 문제에서 나는 간단하게 브루트 포스를 사용하는 방법부터 떠올렸고, 그렇게 풀었다.그런데 자꾸 시간초과도 아니고 틀려서 답안을 보게 되었다.브루트 포스를 사용해서 모든 랜선의 길이를 합친 후에내가 원하는 랜선의 수만큼 나눈다.그렇게 구해진 값이 가장 길게 나눌 수 있는 랜선이 될 것이다.그 길이부터 하나씩 줄여나가면서 나눌 수 있는 최대 랜선의 길이를 구하는 .. 2024. 3. 5.
[백준]BOJ_18110_solved.ac_S4 https://www.acmicpc.net/problem/18110 18110번: solved.ac5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다.www.acmicpc.net이 문제는 딱히 로직은 어려운게 없다.시간 초과를 피하느라 시간이 조금 걸렸다.처음에는 정렬을 Arrays로 해서 그런가 해서 Collections로 바꿨다.그래도 시간초과가 떠서 최대한 변수 선언을 없앴고,그래도 시간 초과가 떠서 BufferedReader를 사용했다. https://github.com/Headfish96/Online-Judge/tree/main GitHu.. 2023. 8. 7.
[백준]BOJ_10816_숫자 카드 2_S4 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0www.acmicpc.net오랜만에 다시 알고리즘 게시물을 작성한다.그동안 혼자 조용히 풀기도 했고 깃헙에 올리기도 해봤는데, 내가 공부한걸 정리하기에 블로그만한게 없는 것 같다.일단 누군가에게 설명을 해야하니 더 완벽하게 이해해야하는 것도 있고, 재미도 있어 더 잘 되는 것 같다.당분간은 많은 문제를 풀기보다 한문제씩 풀면서 이곳에 정리하려한다.하도 오랫동안 풀지 않아 감이 다 떨어졌기 때문.. 2023. 8. 6.
SWEA_2115_벌꿀채취_모의역량 이 문제를 처음 보았을 때는 주어진 벌통의 크기인 배열에서 서로 겹치지 않게 가로로 연속된 M칸을 뽑아서 비교하는 것을 생각했었다.하지만 결국 우리는 꿀의 양과 값까지 고려해야한다.따라서 뽑기 전에 꿀의 값을 최대로 할 수 있는 것들을 남겨놓으려고 한다.예시를 들며 설명해보겠다.1. 꿀의 양에 대한 정보가 담긴 배열을 바탕으로 최대 수익 정보가 담긴 배열을 만들어준다.6197985834538267위와 같은 배열이 주어졌다고 가정해보자.N은 4이고 M은 2이고, C는 10이다.M이 2이기에 1행을 보았을때  [(0,0),(0,1)] | [(0,1),(0,2)] | [(0,2),(0,3)] 가 선택될 수 있다.[(0,0),(0,1)] 을 보면61위와 같은 값이 저장되어 있다. 이때 최대 수익을 구하면 6*6.. 2023. 2. 23.
[백준]BOJ_2178_미로 탐색_S1 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.www.acmicpc.net위 문제는 전형적인 BFS 알고리즘, 넓이 우선 탐색 알고리즘을 이용한 문제이다.최단거리, 최적경로와 같은 촤단, 최적이라는 단어가 쓰이면 BFS 알고리즘을 사용한다고 생각하자.BFS 알고리즘은 넓이 우선 탐색으로 노드로 트리를 구성한다고 했을때 트리의 높이, 트리의 레벨이 경로의 길이가 된다.넖이 우선 탐색은 트리로 그려지고 트리로 그린 것을 큐로 넣었다가 빼면서 간선을 이어갈 수 있다.넓이 우선 탐색에서 큐를 그리면서 이해할 수도.. 2023. 2. 20.
[백준]BOJ_2563_색종이_S5 https://www.acmicpc.net/problem/2563 2563번: 색종이가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록www.acmicpc.net1. 접근한 도화지에 색종이를 여러장 놓고 색종이가 붙은 검은 영역의 넓이를 구하는 문제이다.넓이를 구하는 것이라고 해서 수학적으로 접근하여 겹치는 넓이부터해서 구하려고 하면 매우 복잡해진다.도형의 넓이를 구할때 가로와 세로를 곱해서 구할 수도 있지만, 1cm x 1cm의 칸으로 나눠서 하나씩 셀 수도 있다.이 문제도 위와같이 접근한다.도화지에 100 x 100으로 모눈이 그려져 있고, 색종이를 붙인 다음.. 2023. 2. 15.
반응형

티스토리툴바