PS817 백준 2638 자바 - 치즈 (BOJ 2638 Java) https://www.acmicpc.net/problem/2638 안쪽에 빈 공간은 공기에 접촉하지 않은 것으로 가정하므로, 단순히 배열 전체를 확인하며 공기부분의 상하좌우를 파악하면 안됨. 치즈가 존재하지 않는 외곽에서 시작해서 (코드에선 (0, 0)에서 시작함) dfs나 bfs를 돌려 인접한 공기들로 탐색하면서 인접한 치즈를 확인해야 함. 구현은 사실 간단했음. 반복문 돌리면서 매번 다음의 처리를 해줌. 1. 매번 (0, 0)부터 dfs 돌리면서 상하좌우로 접한게 치즈라면 해당 치즈 부분의 값을 +1 해줌. 접한게 공기라면 그쪽으로 dfs 계속 진행함. (42 line) 2. 치즈인 부분의 갯수를 세줌 (cnt 변수) 3. 공기와 접한 부분이 2면 이상이라면 (코드상으로는 따로 배열 만들기 귀찮아서 .. 2021. 9. 28. 백준 1655 자바 - 가운데를 말해요 (BOJ 1655 Java) https://www.acmicpc.net/problem/1655 발상이 쉽지 않았다. 시간제한도 짧아서 어떻게 구현할지 좀 막막했음. 일단 0.1초같이 극악한 제한시간이 있는 문제들의 경우 자바로는 아예 통과가 불가한 문제들도 있다. 그래서 일단 채점 현황에 자바로 AC 받은게 있나부터 확인했는데 있어서 자바로 도전함 ㅋㅋ 힙을 배열로 어떻게 잘 만들면 O(NlogN)으로 집어넣으면서 바로바로 정렬되고 중간값을 O(1)로 찾을 수 있지 않을까 싶기도 했지만 딱히 구현방식이 생각나지 않았음. 그렇다고 ArrayList에 집어넣고 매번 정렬하는건 당연히 시간초과 날꺼고.. 그다음으로는 이분탐색쪽을 생각해봤으나 역시 구현할 방법이 딱히 떠오르지 않았음. 그러던 중 보통 이런식으로 2부위나 절반씩 나눠 생각하.. 2021. 9. 28. 백준 2157 자바 - 여행 (BOJ 2157 Java) https://www.acmicpc.net/problem/2157 입력 받으면서 서쪽에서 동쪽으로 이동하는 경우는 제외해줬다. (a가 b보다 큰 경우) 동일 노선에 기내식이 별로인 경우도 제외해줌. 처음엔 무지성 Brute Force로 일단 갈겨봤으나 당연히 시간초과났음. ㅠ 다익스트라나 floyd-washall 같은걸로는 m회 이하를 체크하기 힘들꺼라 일단 제외함. 다행히 한방향으로만 진행하면 되므로 그냥 dp 돌리기로 결정함. dp 배열 설정은 dp[i][j] - i:도시번호, j:이동횟수, value:i도시번호까지 j이동횟수로 얻은 최대 기내식 점수 처럼 해줬음. 그럼 이제 dp[1][1] = 0; 을 베이스로 두고 (1번에서 출발했고, 1번도 방문한 도시에 포함되니 [1][1]이 됨. 기내식은 아.. 2021. 9. 26. 백준 2452 자바 - 그리드 게임 (BOJ 2452 Java) https://www.acmicpc.net/problem/2452 어려웠음.. 2일이나 걸렸음.. 기본적인 로직은 아래와 같이 잡음 1. 각 구간은 어차피 동시에 움직이므로 동일 색상으로 된 구간 전체를 하나로 생각함 2. 그러면 배열 전체에 대한 bfs에서, 그래프에 대한 bfs로 압축시킬 수 있음. bfs로 생각한 이유는 결국 각 구역별로 색상이 변하는거니 한칸만 잡고 계속 변경한다고 보면 결국 가장 먼 구역까지의 bfs라고 생각했음. 즉, 구역을 나누고 각 구역별로 모든 지역까지 bfs를 때린다음 그 횟수가 가장 적은게 답이라 생각함. 즉, 3 3 1 0 0 1 0 0 0 1 1 이러한 입력에 대해 구간을 나눠서 숫자를 붙임. (이게 필요할꺼라 생각해서 한건데 하고보니 이게 flood fill 인듯.. 2021. 9. 22. CP 입문 추천 (코딩테스트 연습) CP 입문 추천 CP; Competitive Programing '입문'이라고 적었으나, 애초에 대회라는 특성상 입문이라고 하기엔 난이도가 다소 높은 편. 보통 아무런 공부 없이 참여하면 한 문제도 풀기 힘든 경우가 많음. PS를 경쟁적으로 진행하는 것으로, 프로그래밍 대회 혹은 코테를 부르는 용어라고 보면 됨. 예를들어 대회 접수를 사전에 받고, 9월 16일 오후 9시에 진행되서 2시간이 주어지고 그 동안 5문제를 푸는 경우. 일반적으로 정해진 시각에 시작해서, 정해진 시간동안 진행되며 Score Board로 서로 경쟁할 수 있도록 해두고 순위가 매겨짐. 방식은 개최하는 대회 혹은 개최하는 곳 마다 다르며, 지원하는 언어도 다르므로 확인하고 참여해야 함. (자바, C++, 파이썬은 보통 다 지원함) 프.. 2021. 9. 22. PS 입문 추천 (알고리즘 입문 추천) PS 입문 추천 PS; Problem Solving 해외 사이트들도 많지만, 국내에서 유명한 사이트로 그냥 입문하기 좋아보이는 개인 추천 루트 백준(boj) : 국내 사이트 중 가장 많은 문제수를 가지고 있지만, 기존엔 난이도에 따른 분류가 되어있지 않아서 문제를 잘 찾아 풀어야 했음. 현재는 solved.ac 라는 애드온을 유저중 한명이 만들면서 백준 사이트에도 정식적으로 채택되어 집단지성에 의한 난이도 분류가 되고있는 중이라 단점이 사라지고 있는 중. 사실상 국내 사이트 중 PS만 보면 최고라 생각합니다. 프로그래머스 : 요즘 많은 회사에서 코딩테스트 시 프로그래머스를 사용하는곳이 많아요. 사실상 문제 풀어보는 사이트보다는 코딩테스트 플랫폼이라고 볼 수 있음. 문제 자체는 매우 빈약한편이지만, 코테 .. 2021. 9. 22. PS 란? (알고리즘) Problem Solving 이란? 용어 사용, 용어 해석에 있어 작성자의 개인적인 생각이 포함되어 있습니다. The Feynman Algorithm Write down the problem Think hard Write down the solution Problem Solving(이하 PS)은 '문제 해결'이라는 단어 그대로 주어진 문제를 적절하게 해결 할 수 있는 방법을 찾아 해결하는 것을 뜻합니다. ! 프로그래밍으로 본다면 '원하는 결과를 적정한 시간과 메모리 이내에 처리하는 프로그램을 만드는 것'을 뜻합니다. 여기서 '적정한 시간'은 사람이 문제를 해결하는데 걸리는 시간이 아니라, 해당 프로그램이 입력을 받은 후 결과를 내놓기 전까지 걸린 시간을 의미합니다. 예시 정수 A와 B를 입력받아 A+B를.. 2021. 9. 22. 이전 1 ··· 79 80 81 82 다음
