* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중... * 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기 Greedy 9 / 50 탐색 12 / 50(NEW!) 기초 동적 프로그래밍 9 / 50 투포인터 2 / 10 이분탐색 0 / 10 문제 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net → solved.ac 기준 실버 2 문제 해결 아이디어 A에서 B로 바꾸되, 연산의 최솟값이므로 BFS를 이용하여 탐색 → 처음 시도: 평소 풀던 것처럼 0에서 B까지 graph를 초기화하고, 방문 ⇒ 메모리 초과 발생 → a에서 b로 가는데 안 가는 곳이 더 많을 것. python의 딕셔..
* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중... * 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기 Greedy 9 / 50 탐색 11 / 50(NEW!) 기초 동적 프로그래밍 9 / 50 투포인터 2 / 10 이분탐색 0 / 10 문제 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net → solved.ac 기준 골드 4 문제 해결 아이디어 최소 경로를 구하는 문제로, BFS를 이용 ⇒ 스크린에 있는 이모티콘의 갯수(screen)와 클립보드에 있는 ..
* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중... * 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기 Greedy 6 / 50 탐색 8 / 50(NEW!) 기초 동적 프로그래밍 6 / 50 투포인터 1 / 10 이분탐색 0 / 10 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net → solved.ac 기준 골드 4 문제 해결 아이디어 "바이러스가 퍼진다"라는 구문에서 이전에 풀었던 토마토..
* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중... * 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기 Greedy 4 / 50 탐색 4 / 50(NEW!) 기초 동적 프로그래밍 4 / 50 투포인터 0 / 10 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net → solved.ac 기준 실버 1 → class 3 문제 해결 아이디..
* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중... * 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기 Greedy 3 / 50 탐색 4 / 50(NEW!) 기초 동적 프로그래밍 3 / 50 투포인터 0 / 10 문제 1697번: 숨바꼭질 (acmicpc.net) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net → solved.ac 기준 실버 1 문제 해결 아이디어 걷는다면, x - 1 또는 x + 1로 이동 순간이동하면..
* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중... * 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기 Greedy 50문제 풀기 1 / 50 탐색 50문제 풀기 1 / 50(NEW!) 기초 동적 프로그래밍 50문제 풀기 1 / 50 투포인터 10문제 풀기 0 / 10 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 해결 아이디어 (이것이 취업을 위한 코딩테스트다에서 나온 BFS 예제 문제와 해결 방법이..
문제 문제 링크 : https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 네 개의 명령어 D, S, L, R을 사용하는 간단한 계산기가 있다. 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자. 1. D : n을 두 배로 바꾼다. 결과가 9999보다 크면 10000으..
문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 풀이 풀이 - BFS와 DFS 이분 그래프는 쉽게 말하자면 그래프에서 연결되어 있는 노드끼리 같은 색깔을 칠했을 때 총 두가지 색깔이 나온다는 의미다. 모든 노드를 탐색하면서 색깔을 칠하는 방식으로 해결했고 이 때 DFS를 이용했다. (BFS로도 풀 수 있다고 한다.) 재귀로 풀면서 해결하는데 문제는 비연결 그래프인 걸 감안하고 풀어야 한다.(이거 때문에 계속 오류남..) 탐색을 하면서 인접한 노드에 dfs를 수행..