백준\_2178입력을 받을때 공백이 없기때문에 scanf %1d를 이용하였다. 또한 0,0 으로 시작하였기때문에 return 은 N-1,M-1로 해야한다.
DFS/BFS 기본 구조를 연습해볼수있는 문제였다.인접리스트 방식으로 구현하였으며 작은수를 기준으로 탐색을 하여야 했기때문에 메인함수에서 sort함수를 적용하고 시작하였다.
문제링크(수정)스택을 이용한 문제, 괄호를
문제 링크longlong의 크기를 넘어가버리기때문에 string을 이용하여 숫자로 변환후 다시 string을 이용하여 작업할 필요가있다. 앞으로도 longlong 그이상의 연산이 필요할때는 쓸수있도록 알아두자.그외의 파스칼의 삼각형을 이용하였다
문제 링크누적값을 구하는 dp테이블부터 최적의 해를 찾기위해 생각을 했어야하는 dp문제였다.dp테이블의 각 칸을 누적합으로 배치시킨 후, 문제에서 요구하는 범위합이 필요할때는 dp테이블을 구할때와 유사하게 그림을 그려서 생각해보면 편하다.
문제 링크처음에는 그리디로 접근했다가 당연히 반례가 있었다. 다음은 BFS로 접근하였는데 일반적인 BFS는 불가능하다. 왜냐하면 좌우로 이동할때는 시간(비용) 이 동일하지만 순간이동할시 비용이 0 이므로 각 간선에서의 비용이 동일하지 않다.물론 BFS에 가지치기처럼 조
문제 링크동빈북으로 유명한 '이것이 코딩 테스트다' 에 part2 DP문제와 유사하다.그리디로 접근하면 당연히 반례가 있으므로 DP로 접근하여야 한다.각 dp테이블에 최적의 해를 찾는과정으로 1\. i-12\. 2로나뉠경우,3\. 3으로 나뉠경우, case3가지중 최소
문제 링크BFS를 이용하여 기본적으로 풀었다.queue에 넣어줄때와, 처음에 각각 count를 이용하여 가구 수를 구하였으며main문에서 graph에서 1 이지만 아직 방문하지 않은곳이 있다면 houseCnt++ 후 들어가도록 설계했다
문제링크기본적인 BFS문제였으며 조심할점은 1번컴퓨터를 제외한 숫자이므로 처음에 cnt++ 을 해줄필요는없다 ! ( 문제 제대로 읽기!!!) , 또한 링크드리스트를 이용할때와 배열을 이용할때 구분하여 잘 알아두자
백준 문제 링크map에서의 bfs를 돌면서 전체 섬의 개수를 세는것과 유사한 문제이다. 조심해야 할 점은 Testcase의 개수가 정해져있기 때문에 매번 map과 visited배열을 처음상태로 초기화 시켜줘야한다. -> init()을 따로 만들어서 애용하자!
문제 링크이 문제는 Unionfind로 푸는것이 먼저 떠올랐지만, 우선 BFS로 한번 풀고 Unionfind로도 다시 풀어보았다.BFS로 풀때는 main에서 visit배열을 통해 지나지않은 정점(즉 아직 연결 되지 않은)을 찾아서 카운트를 늘려주고 접근해야 한다.또한,
코드 설명 기본적인 틀은 BFS 기본 유형 문제이지만 + 벽을 3개 세워서 세웠을 때 가장 0이많은 경우의수를 찾아야하는 case가 추가되었다. 따라서 BFS의 틀에 전체 map에서 0이 있을경우 모든경우의수를 돌면서 벽3개를 세운다고 생각하였다. 소스 코드
문제 링크대각선 방향도 탐색해야 하므로 방향배열을 8개로 늘려준다.또한 visit배열을 이용하여 main에서 들어갈때, BFS함수내에서도 탐색했던곳은 가지않는것이 중요하다.입력을 받을때에도 while문 내에서 계속해서 map,섬의개수cnt등을 모두 초기화 해주어야한다.
문제 링크DFS를 이용하여, 각각의 비가오는 높이를 하나씩 늘려가며 전체 map을 탐색하였다. 그중 비의 높이에따른 안전영역이 가장 넓은(cnt) 를 계속해서 갱신하였다. DFS를 연습하기 좋은 문제였다.
문제링크직사각형으로 채워진곳은 map을 전부 1로 할당하고 0을 돌면서 영역을 카운트하였다. 기본적인 문제였지만 주의하여야 할점은 처음 y,x좌표가 반대로 꼬여있기때문에 문제를 정확히보고 중간중간 디버깅을 통하여 map에 문제모양대로 되어있는지 확인하는 습관이 중요하다
😊 소스 코드
소스 코드
문제 링크처음에는 어렵게 생각했지만 일반적인 DFS 방법으로 풀린다.문제에선 R,G,B의 알파벳으로 나왔지만 dfs내에서 기존 x,y 와 그다음 nx,ny가 같을때 넣어주고 visit배열을 채워주면된다.main에서 시작점을 넣어주는것도 visit배열에 방문하지만 않으면
문제 링크전형적인 DP 문제여서 고민없이 접근하였다.1x2, 2x1 타일밖에없기 때문에 n번째 타일에서는n-2번에서 구성했던 타일에서 1x2타일들을 추가하고n-1번에서 구성했던 타일에서 2x1타일들을 추가하면 완성된다.즉 점화식은 dpn = dpn-2 + dpn-1
문제 링크문제 난이도에 비해 한번 접해보지않으면 생각하기 힘들었다고 생각한다. 하나씩만 이동할수 있기때문에 분할정복-> 재귀로 풀어야했다.다른 블로그의 풀이들을 참고했는데 죄다 같은 설명을 해놓아서 이해하는데 시간이걸렸다.한줄씩 디버깅해가면서 혼자 이해해보려고했는데 전
문제 링크단순한 그리디문제였다. 문제 예시만 봐도 알수있듯이 정렬후에 작은사람부터 먼저 ATM기를 사용하게 한다면 모든 사람이 최소한의 시간을 기다릴 수있다.
문제 링크삼성 기출의 구현문제 이다. 문제를 따라가면 되지만 제대로 설계하고 풀지 않아서 디버깅하는데 꽤나 오래걸렸다.구조체, 각각의 index를 이용할때 실수하지 않도록하자.
문제 링크전체 while문을 사용하여1.빙하로 이루어진 한덩어리 dfs 돌기 (visited이용)2.덩어리가 2개로 이루어졌으면 while문 탈출후 year 출력3.끝까지 녹일때까지 탈출하지 못한다면 0 출력4.melt()를 이용하여 주변의 바다칸수만큼 녹이기melt시
문제 링크기본적인 BFS 탐색 방법이다. map에 직접 카운트를 해주는 방식진행하였다.이후 도착지에 도착하면 break를 멈춰준후 카운트를 출력해준다.
문제링크10^9을 넘은 연산이 가능하기때문에 long long 변환 이 필요하다 (dfs로 넘겨줄때도 당연히 longlong형으로 해야한다 ...여기서 오류 계속🤣)dfs를 이용하여 모든 연산을 수행하고 B보다 커질시 return한다. longlong변환은 stoll
문제링크처음에는 그냥 vector에 erase,insert로 생각없이 접근했다.시간초과가 나고 n크기와 o(N^3) 가 된다는걸 알았다. (erase,insert는 각각 for문 형태인걸 잊지말자)n이 1,000,000 에 1초제한이므로 2중 for문으로도 안될것 같아
문제 링크투포인터 연습을위해 대표적인 백준문제로 개념을 다시 잡았다.포인터 2개를 이용 (left,right), int cnt(부분합 카운트용), int sum (부분합) 을 이용한다.조건문으로 고려해야할것은 \-> 1. 현재의 부분합이 목표값 이상이거나 right==
문제링크벽 3개를 완전탐색(DFS)를 이용하여 선정한후 vector에 넣는다.이후 BFS를 통해 바이러스를 퍼져나가게한후 0의 갯수를 센다가능한 방법을 전부 탐색하여 0의 갯수가 최대가 될때까지 반복한다.(완전탐색+BFS)
문제링크현재상태를 계속해서 큐에 집어넣어주고 벽을 부쉈는지에대한 visit배열을 한차원 늘려서 확인해준다.이외의 중요팁들은 백준 게시판에서 글을 가져와보았다.