Blog for Programming

1. 문제 및 예시 실행 결과 solved.ac의 CLASS가 올라갈수록 모르는 알고리즘이 많다. 어제 토스 코테 한번 찍먹하고 많이 반성하게 됐다. 모르는 것을 공부하는게 맞는 것 같다. Union-find를 활용한 크루스칼 알고리즘을 공부하고 적용해보았다. 한큐에 초록 글자가 떠서 너무 좋았다. 출처: https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 문..

1. 문제 및 예시 실행 결과 투 포인터를 활용하는 문제... 나름 재밌었다. 보통 이런 경우는 이분탐색 처럼 구현을 하게 되는데 그 과정은 어렵지 않지만 어떤 문제로 접근해야하는지 찾는 과정이 이분탐색 혹은 투 포인터 문제의 핵심이라는 생각이 든다. 출처: https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 입력 2. 이분탐색 진행 왼쪽과 오른쪽으로 부터 시작하여 두 값의 합이 0보다 크면 음수쪽이..

1. 문제 및 예시 실행 결과 간단한 다익스트라 문제이지만, 경로를 출력해야한다. 처음에는 문자열을 옮기는 방식으로 풀었는데, 원인을 알 수 없는 이유로 틀렸다는 문자만 계속 떴다. 그래서 경로를 배열에 저장하는 방식을 사용했다... 문자열도 같은 원리인데 대체 왜 그러는지 참... 출처: https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 입력 2. 다익스트라 진행 3. ..

1. 문제 및 예시 실행결과 이 글의 소제목이 DFS 알고리즘이지만, 나는 DFS알고리즘을 모르는 상태이다...... 그냥 내가 생각한 방식대로 풀었더니 그것이 DFS 알고리즘이었던 것이다. 다른점이 있다면 나는 자료구조를 queue를 사용하였지만 DFS 알고리즘은 stack을 사용한다고 한다. 이 글은 DFS알고리즘의 설명보다는 1012번을 푸는 방법에 대한 글이라고 생각해줬으면 좋겠다. 출처: www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 중요한 점은 이놈의 지렁이..

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

1. 문제 및 예시 실행결과 수학 카테고리에서 문제를 풀기 전 문자열 카테고리와는 다른 종류의 겁이 들었던 기억이 난다. 코딩을 잘 한다는 것이 아직도 뭔지 모르겠다. 문법을 잘 알고, 에러를 만들지 않는 사람도 있고 수학적 기교로 코드수를 줄이거나 알고리즘을 잘 설계하는 사람이 있을 것이다. 전자와 후자 전부 대단하지만, 나는 이 모든 부류를 공부할 때 겁을 먹는 것 같다. 언젠가는 이런 겁도 안먹기를 바란다. 이번 문제는 규칙을 파악하는 것이 매우 중요한 문제이다.(모든 코딩문제가 그런 것 같지만......) 실제로 나는 이 문제를 위해 그림도 그렸다 ㅠㅠ 다음은 문제와 예시 실행결과이다. 출처: https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육..

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

1. 문제, 실행결과 예시 별찍기는 반복문을 활용하는 가장 대표적인 문제라고 생각한다. 사실 프로그래밍을 하다보면 수학적으로 규칙을 구하고, 일반화를 시켜 그 식을 적용하는 코드를 짜야할 때가 많은데, 아마 별찍기가 이런 부분을 연습하는데 있어서 정말 좋은 문제라고 생각한다(지극히 개인적인 생각입니다). 사실 스택을 풀다가 갑자기 별찍기를 푸는 이유는, 단계별로 풀기에서, 실습 1번부터 차례로 푸는 것을 목표로 잡았기 때문이다. 소프트웨어 마에스트로 코딩테스트를 대비하기 위함도 있고, 나름의 목표를 잡는 것도 좋다고 생각하기 때문이다. 다음은 이번에 푼 문제와 실행결과 예시이다. 출처: https://www.acmicpc.net/problem/2523 2523번: 별 찍기 - 13 첫째 줄부터 2×N-1..