Blog for Programming

1. 개요2시간 녹인 문제... 늘 내 블로그에 적는 말이지만 구현은 초반 설계가 잘못된다면 정말 힘든 문제인 것 같다. 여러 예외도 생각해야하고... 이래서 난이도 높은 문제들은 구현인가...? 싶기도 하다. 문제를 나누고 나올 수 있는 예외를 전부 처리해야 성공하는 문제이기에 시간도 많이 들고 힘도 많이 들었다... 출처: https://www.acmicpc.net/problem/2933 2. 본문내가 생각한 구현 문제의핵심은 다음과 같다. 물론 말 그대로 타고난 능력이 좋은 사람들은 저런 방법이 필요 없겠지만 말이다.. ㅋㅋㅋ1. 문제를 단계별로 나눈다.2. 예외사항을 처리한다.3. 구현- 문제 나누기 문제를 나누면 다음과 같다.1. 방향에 맞는 미네랄 제거.2. 떨어지는 미네랄 조사.3. 떨어질 ..

1. 문제 및 예시 실행 결과  중구난방으로 알고리즘 문제를 풀다 이러면 아무것도 안 될 것 같아서 내가 약한 유형의 문제를 우선적으로 공부해야겠다는 생각해 DP문제를 쭉 풀어보았다. 바킹독님의 블로그에서 공부하고 있는데 풀이가 달라 한 번 정리해보았다. 출처: https://www.acmicpc.net/problem/25792. 본문  DP는 데이터 구조를 먼저 생각해보고 점화식을 세우는 두가지의 단계로 나뉜다고 생각한다. 물론 점화식을 세운다는 것 자체가 안 되는 문제이기에 구현 다음으로 손에 익어야하는 문제가 아닌가 싶다. 어쨎든 해당 문제의 데이터 구조와 점화식은 다음과 같이 정했다.데이터 구조: cache[i] = i번째 계단으로 얻을 수 있는 점수 중 최대값. 이제 데이터 구조를 구하는 점화식..

1. 문제 및 예시 실행결과 다익스트라 문제라는 것을 처음부터 알게 되었다. 문제 잘 읽고 푸는 습관을 들여야하는데... 부등호하나 잘못써서 두번의 틀렸습니다가 찍힐뻔 했다... 다익스트라가 손에 조금 익어서 해당 알고리즘을 사용하고 있는데 플로이드 워셜로 나중에 공부해서 적재적소에 사용할 수 있으면 좋겠다. 출처: https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 2. 풀이 과정 문제 쪼개기 1. 입력 2. 모든 노드를 시작점으로 설정 - cache..

1. 문제 및 예시 실행결과 BFS문제인 것은 파악했는데 visited 배열을 처리하는 과정에서 조금 힘들었다. 논리적으로 길을 먼저 세워 풀면 되는 문제를 너무 급하게 덥벼든 것 같다. visited를 배열에 삽입하기 전에 처리하는 것이 좋을 수 있지만(Queue가 커지는 것을 방지) 이 문제 처럼 같은 depth의 중복을 처리해야하는 문제는 queue에서 노드를 꺼내서 visited처리를 하는게 좋을 수 있다는 것을 깨달았다. 다음은 예외 케이스이다. 1 3 출처: https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)..

1. 문제 및 예시 실행결과 구현과 시뮬레이션 문제이다. 어우 힘들어... 구현은 아무래도 높은 집중력과 예외처리를 위한 설계가 중요시 되는 것 같다. 한번 오류나면 멘탈이 나가서 문제 난이도가 생각보다 높게 느껴진다. 재능있는 사람들은 처음부터 오류없는 코드를 잘 작성하겠지만, 나는 그런 것 같지는 않으니 최대한 고심해서 코드를 짠다. 그래서 이리 힘든 것인지... 출처: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 과정 알고..

1. 문제, 실행결과 예시 백준 알고리즘 카테고리에 글을 쓰는게 정말 오랜만인 것처럼 느껴진다. 아마 실제로도 오랜만일 것이다 ㅎㅎ. 이 문제에 대한 풀이를 올리는 이유는 시간 초과라는 새로운 문제를 만났기 때문이다. 실제로 소수를 구하는 문제는 정말 많이 풀어봤지만, 이번 문제의 최대 입력값은 100000으로 기존에 사용하던 방법( 1 ~ N 까지의 모든 수를 비교하는 방법 )을 사용하면 시간초과가 날 수 밖에 없었다.( 심지어 숫자 하나당 줄바꿈을 해야하는 문제이다. ) 때문에 소수를 찾는 다른 방법을 사용해야 했다. 방법은 아래에서 자세히 설명할 것이다. 다음은 문제와 실행결과 예시 이다. 출처: https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의..

1. 문제, 예시 시행결과 이번 문제는 나름 시간이 걸린 문제이다. 문법으로 틀린 문제가 아니라, 논리로 우류가 났기 때문에...... 사실 이런 문제도많이 틀려가면서 스스로 부족한 점을 알아가려는 것에 목적이 있지만, 찾는데 꽤 오랜 시간이 걸렸다...... 결론 부터 말하면 논리 연산자 때문인데, 이 부분을 자세히 설명하는 새로운 글을 쓸 계획이다. 이 글에서는 문제 풀이 만을 설명할 것이다. 다음은 문제 및 예시 실행결과이다. 문제: https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 문제 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- d..

1. 문제 예시 실행결과 이번 문제는 입력받은 값만큼 한 문자를 반복해서 출력하는 문제이다. 나름 간단한 문제이지만, 결과 문자열을 어떻게 다루냐에 따라서 나름 생각이 깊어질 수 있는 문제이다. 다음은 문제와 예시 실행결과이다. 출처: https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문제 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 www.acmicpc.net 다시한번 말하지만 이 문제는 출력형식에 따라 까다로워질 수 있다. 다음은 풀이 과정이다. 2. 문제풀이 첫번째 입력은 간단하다. 솔직히 말하면 두번째 입력..