Victory in my life

📌문제SILVER1 / 너비 우선 탐색 / 그래프 이론 / 그래프 탐색https://www.acmicpc.net/problem/7562 [문제 설명]체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?[입력]입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나..

📌문제SILVER1 / 두 포인터https://www.acmicpc.net/problem/20922[성능 요약]메모리: 53288 KB, 시간: 232 ms[분류]두 포인터 [문제 설명]홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100000100000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.[입력]첫째 줄에 정수 N (1≤N≤2000001≤N≤200000)과 KK (1≤K≤1001≤K≤100)가 주어진다.둘째 줄에..

📌문제SILVER4 / 브루트포스 / 완전탐색 / 구현 / 알고리즘https://www.acmicpc.net/problem/28215📌문제 분석 및 설계역대급 바보짓한 문제다.. 문제이해부터 알고리즘 구현까지 30분만에 해놓고 초기화잘못된 거 못 찾아서 1시간30분을 날렸다 하핳 아무튼, 문제 읽었을때 조합 함수 사용하고 완탐하면 되겠구나 ! 하고 바로 알고리즘을 작성했다. 나의 실수는 result를 -1로 초기화를 했다는 것이었다.모든 집이 대피소로 지정되는 예외사항을 고려를 하지 못한 것이다.결국 모든 집이 대피소로 지정되는 경우 other not in daepi 조건이 항상 False가 되어, result가 그대로 -1인 상태로 남아버려서 계속 틀렸다.다들 조심. 📌소스 코드import mat..

📌문제SILVER3 / 다이나믹 프로그래밍 (dp)https://www.acmicpc.net/problem/1463📌문제 분석 및 설계문제보고 그냥 바로 while 쓰다가 갑자기 어..? 이거 dp문제인거같은데...? 싶어서초기화하면서 식을 찾아나갔다. 쓰다보니 해당 수의 dp[하나작은수]+1과 3으로 나뉘면 dp[ 3으로 나눈 몫]+1과 비교해 최솟값으로 ,아님 2로 나뉘면 dp[2으로 나눈 몫]값과 비교해 최솟값으로 ,만약 3과 2로 둘다 나뉘어진다면  dp[하나작은수]+1 과 dp[ 3으로 나눈 몫]+1, 그리고 dp[2으로 나눈 몫]과 비교해 최솟값으로 지정!!! 나능 사실 마지막 3과2로 둘다 나뉘어질때를 고려를 안해서 틀리다 발견했다. 이러니 설계부터 완전히 하고 코딩하는게 좋다.그리고 B..

📌문제SILVER2 / 그래프 / 그래프 탐색 / BFS / DFShttps://www.acmicpc.net/problem/11724📌문제 분석 및 설계dfs를 몰라서 개념공부할겸 정한 문제이다.bfs도 적용가능해서 두 버전으로 코드를 돌려봤다. 아래 코드에 있는 DFS와 BFS가 딱 해당 알고리즘의 코드이니, 모르시는 분들은 우선 냅다 외워둬도 괜찮을 것 같다. 중요했던건 sys.setrecursionlimit(10**6)  해당 코드를 안넣으면 백준에서 계속 런타임에러가 났다.. 기억하기 ..📌소스 코드 DFS버전import sysfrom collections import dequesys.setrecursionlimit(10**6)input=sys.stdin.readlineN,M=map(int,..

📌문제SILVER5 / 구현 / 그리디 알고리즘https://www.acmicpc.net/problem/1343📌문제 분석 및 설계문제를 봤을 때,X뭉터기랑 .뭉터기를 분리하는게 이 핵심이라고 생각했다. 따라서 아래와 같은 요소들로 설계를 했다.1. split를 통해서 분리2. 나누기로 A,B삽입3. 반례로 .만 있을때 케이스 분리(자꾸 틀려서 그제야 반례찾으면서 알게 됨) 하지만... replace를 쓴다면 굉장히 간단하게 끝난다..하핳📌알게된 팁문자열에 +연산을 계속하면, 문자열은 불변(immutable) 이라서 O(N^2) 성능이 될 수 있다 👉 리스트에 append() 해서 나중에 "".join()으로 합치는 게 더 효율적!!📌소스 코드처음코드는 아래와 같고 original=input()..

📌문제SILVER1 / bfs / 그래프이론 / 그래프탐색https://solved.ac/contribute/14940📌문제 분석 및 설계제목 그대로 쉬운 최단거리 구하는 문제이다.보자마자 뭐야 쉽네 하고 걍 bfs여러번돌렸다가 시간초과나와서아? 하고 생각하니 걍 도착지점에서 모든 distance를 구하면 되는 거였다. 다 푼 후에 코드를 정리하려고 보니,원래는 2인 지점을 따로 반복문에 넣고 찾은후에 bfs돌리고 도달할 수 없는 위치 처리해줬는데 불필요한 반복이라우선 이중 반복문을 통해 위에 말한 처리들을 한번에 해주고 그 후에 bfs가 돌아가도록 했다 📌소스 코드from collections import dequen,m=map(int,input().split())grid=[list(map(int..

📌문제SILVER1 / bfs / 그래프 탐색 / 그래프https://www.acmicpc.net/problem/2178📌문제 분석 및 설계문제를 봤을 때, [ 최소의 칸 수 / 입력 처리 ]가 핵심이라고 생각했다.완전히 기본중에 기본 bfs문제라, bfs 처음 연습할 때 좋은 문제다. 따라서 아래와 같은 요소들로 설계를 했다.1.  bfs로 탐색하면서 이전 위치를 기록하고, 탐색을 마친 후 N,M부터 역으로 1,1까지 가면서 경로추적하며 최소 칸 수 계산2. grid를 줄 때, 입력을 붙여서 주기때문에 따로 처리 생각해보니 경로추적이 불필요하다고 생각해 최단거리 추적하는 방식으로 변경했다.두 버전 모드 코드를 업로드했다. 📌소스 코드#경로 추적 버전from collections import deq..

📌문제SILVER2 / 구현 / 그리디 알고리즘https://www.acmicpc.net/problem/1138📌문제 분석 및 설계 문제와 예제를 보니 자신보다 작은 사람이 왼쪽에 몇 명 있는지를 고려해야 한다는 점을 발견했다. 1️⃣ 키가 1인 사람의 자리 결정키가 1인 사람은 자신보다 작은 사람이 없으므로,→ 자신보다 키가 큰 사람 수에 해당하는 인덱스에 배치된다.2️⃣ 키가 큰 사람들의 자리 결정 (키 ≥ 2)키가 2 이상인 사람들은 왼쪽에 있는 작은 사람의 수를 고려해야 한다.자신보다 작은 사람이 이미 배치되어 있다면, 원래 있어야 할 자리보다 더 뒤로 가야 한다.3️⃣ 예제 상황 분석예를 들어, 키가 3번인 친구가 줄을 설 차례이고,왼쪽에 키가 큰 사람이 1명 있다.현재 줄의 상태가 (비어있..

📌문제SILVER2 / 구현 / 시뮬레이션https://www.acmicpc.net/problem/20006📌문제 분석 및 설계이 문제는 나만 그런거같지만 이해가 잘 안됐다..문제 설명에서 시스템순서에서 '입장 가능한 방이 있다면 입장시킨 후 방의 정원이 모두 찰 때까지 대기시킨다'란 말이 혼란을 일으킨것 같았다. 하지만 이 대기시킨다는 것은 모든 플레이어가 입장을 마친 후 방마다 정원확인 후에 하는 과정이었다..그러니까 나는 시스템 설명이 다 순서대로 돌아가며, 입장이 한명씩되는 줄 알았다.. 왜냐면 입력 설명에도 입력된 순서대로 게임을 시작한다길래... 아무튼 대기 및 시작은 모든 플레이어가 방에 들어가고 하는 과정이라는 것..! 문제를 이해한 후에는 순수 구현문제라 쉽게 구현했다. 📌소스 코드..