알고리즘 (10) 썸네일형 리스트형 [백준] 1328번 고층빌딩 DP ( python ) 인생 처음으로 푸는 플레 문제이다. DP 문제를 풀면서 느끼는 건데 뭔가 이 알고리즘에 대해 깨달았다. 이 문제 푸는데도 그렇게 엄청 어렵다 정도는 아니었다. ( 패드가 방전되어서 오랜만에 빡지로 풀어보기.. ) 꽤 간단했다. 문제 설명 ) 작은 빌딩을 설치해야 하는 상황이다. 자 우리가 건물을 바라볼 때 큰 건물 뒤에 작은 건물이 있다면 과연 그 건물이 보일까? 이 문제가 그런 방식으로 접근을 하는 것!! 어찌 됐든 작은 빌딩이 양쪽 맨 끝에 두었을 때 보일까? 제일 처음에 있는 빌딩이라 무조건 보인다. 그래서 +1이 된다. 그럼 많고 많은 빌딩 사이에 작은 빌딩이 낀다면? 보이지 않을 것이다. 자 문제의 규칙성을 찾아냈다. 그럼 결론적으로 점화식은? dp [N][L][R] = dp [N-1][L.. [백준] 1012번 유기농배추 (JAVA) https://www.acmicpc.net/problem/1012 문제 접근 누가 봐도 이 문제는 그래프이론을 활용한 문제이다. 탐색을 통해서 배추흰지렁이를 알아내는 문제라고 생각했기에 BFS와 DFS를 사용하여 풀어가는 문제이다. 나는 이번 문제는 DFS를 이용해서 풀어보았다. 물론 BFS도 시도하는게 공부에 정석이라고 생각하지만 차라히 다른 문제를 BFS로 접근해서 풀어보는게 성취감에 더 좋을거 같다. DFS map에서 1인 위치는 배추가 심어진 곳. 연결된 1(배추) 영역은 한 마리의 벌레가 방어하면 되므로, 아직 방문하지 않은 1의 위치에서 DFS 시작할 때마다 벌레 수(count)를 1 증가. DFS는 재귀를 이용해 상하좌우 인접한 배추(1)들을 탐색하며 visit을 통해 중복 방지. df.. [백준] 2230 수 고르기 (JAVA) https://www.acmicpc.net/problem/2230 요새 코드적인 감각이 조금 사라진 것 같아서 구현 문제를 풀어보았다. 비동기식 구조와 SpringBoot를 함께 병행하며 실습 위주로 하다보니 근본적인 코드 짜는 능력이 현저히 퇴화된 것을 느껴버렸다. 그래서 하루에 1개는 아니더라도 2일 1개를 목표로 자바로 간단하게 풀어볼 예정이다. 위의 문제는 백준 기준 골드 5의 문제이며 문제의 이해는 꽤 간단하지만 알고리즘적으로 짜는 방식을 익히고 구현을 보는 문제인거 같다. 사용되는 알고리즘은 핵심적인 투 포인터를 묻는 문제인거 같다. 문제 접근 1. N 과 M 그리고 그에 해당되는 수열의 값들을 먼저 받는다. 이때 문제에서 나온 [1,5,3]을 예로 들어보자.M이 받은 입력 값은 .. 코테 준비를 위한 DP ( Dynamic Programming ) feat. 몇몇 백준 문제 서론 주변에 취업을 하신 지인 분이나 코딩테스트를 몇 번 보신 분들이 필수적으로 코테 알고리즘에서 중요하다고 했던 것들 중에서 바로 동적 프로그래밍을 다룰 것이다. 내 시기는 지금 개발 공부를 더 열심히하고 프로젝트도 많이 해보는 경험을 쌓는 시기라고 많이 느낀다. 그래서 요새는 알고리즘보다는 그냥 개발 공부를 더 한다. 하지만 놓아야 해도 놓을 수가 없는게 나는 나중에 코딩 테스트를 잘 보고 싶은 욕구가 크기 때문에 그냥 닥치는대로 푸는 것이 아닌 알고리즘을 하나 하나 풀어가면서 푸는 방식을 알아가면서 정리만 하고 개발 공부에 집중하려고 한다. 이 DP 블로그는 1주일 간 3시간씩 투자하면서 정리하고 공부했던 일종의 일기? 라고 해야할까 이제 본론으로 들어가기 전에 DP를 공부하며 느낀 것은 규칙을.. [백준] 7569번 토마토 (PYTHON) https://www.acmicpc.net/problem/7569 # 문제 정리 철수의 토마토 농장은 3차원 창고 구조로, 여러 층의 상자가 격자 형태로 쌓여 있다. 각 칸에는 다음과 같은 상태를 가진 토마토가 있다. 1: 익은 토마토0: 익지 않은 토마토-1: 토마토가 없는 칸 익은 토마토는 하루가 지나면 인접한 여섯 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)에 있는 익지 않은 토마토를 익게 만든다. 모든 토마토가 익기까지 걸리는 최소 일수를 구하는 것이 목적 ! 다음 조건을 만족해야 한다. 만약 익지 않은 토마토가 모두 익을 수 없는 경우 -1을 출력.처음부터 모든 토마토가 익어있으면 0을 출력. 이에 대한 접근 방식은 3차원 배열로 구성된 그래프 이론 알고리즘으로 접근할 것이다. 특히 이.. [백준] 17609번 회문 / C언어 https://www.acmicpc.net/problem/17609 백준 기준 난이도는 골드 5이며 생각하기에 유사회문에 대해 문제 해결 방식을 생각해 내면 그렇게 어렵지 않게 알고리즘 보다는 구현 쪽으로 푸는 문제인거 같다. # 문제 이해 팰린드롬은 문자열이 짝수면 인덱스 기준으로 맨 처음과 맨 끝이 같고 그렇게 맨 처음은 인덱스 +1 / 맨 끝은 인덱스 -1이런식으로 하면 'abba' , 'baab' 와 같은 형식이 바로 팰린드롬이다. 홀수면 제일 중간 인덱스를 제외하고 나머지가 짝수처럼 앞 뒤가 같으면 팰린드롬이 된다. 자료구조를 배우면서 스택과 큐를 쓰면서 해본 기억이 있다. 하지만 이 문제에는 또 다른 조건식인 유사회문이 있다. 유사회문이란 어떤 문자열에서 문자 하나를 지우게 되면 회문이 되.. [백준 / 올림피아드 ] 28325번 호숫가의 개미굴 ( DP , greedy / c언어) 학교에서 친해진 형이 추천으로 코딩 학원 초,중등부 학원 알바를 하게 되었다. 그 중에 한 학생이 정보 올림피아드 1차 예선을 붙어서 2차 준비를 맡게 되었다. 중등부 정보 올림피아드 문제를 보는 순간 약간 당황스러웠던 점이 많았다. 일단 생각보다 난이도 더 높았다. 특히 시간 복잡도, 공간 복잡도를 하나 하나 체점을 하는 방식이다. 총 올림피아드 문제는 4문제로 2문제만 정확히 맞추면 되는 목적으로 가르치라고 명을 받게 되었다. 그 중 2번 문제인 이 문제는 난해한 구현 문제였다. 그래서 어떻게 최적의 알고리즘을 짜야할지 고민을 많이 했다. 백준 기준 골드 5의 난이도 DP 문제이다. https://www.acmicpc.net/problem/28325 DP(Dynamic Programming)란.. [백준] 1260 DFS와 BFS (그래프 탐색 / C언어 ) 이번 학기( 2024년 1학기 ) 자료구조를 배우며 그래프 활용에 대해 어려움을 많이 겪었다.끝나고 몇 번의 복습을 거쳐서 이 문제에 적용하여 풀게 되었다. 그래프를 표현하기 위한 대표적인 자료구조 설정은 인접행렬과 인접리스트 방법이 있다.그래프 표현 후에 DFS( 깊이 우선 탐색 )와 BFS ( 너비 우선 탐색 )을 활용하여 푸는 문제이다. 백준 기준으로 실버 2인 문제이다. https://www.acmicpc.net/problem/1260 여기서 그래프 이론을 알기 전에 DFS와 BFS가 무엇인지부터 알아야 풀 수 있는 지식이 필요한 문제이다. EX ) 인접리스트 ( 그래프 탐색은 dfs bfs 둘 다 사용이 가능하다 ! ) DFS ( 스택 활용 / Depth First Search ) >> 임.. 이전 1 2 다음
