티스토리

종난아! 공부하자!

검색하기

블로그 홈

종난아! 공부하자!

jongnan.tistory.com/m

JOngNan 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

[BOJ 11048] 이동하기 #문제 https://www.acmicpc.net/problem/11048 #풀이굉장히 쉬워보이지만 은근 까다로운 문제인것 같습니다!처음에는 BFS를 사용하여 푸는 생각을 했지만, 해당 문제는 최단 거리를 움직여 구하는 것이 아니며, 모든 경우의 수를 해보아야 하고 이미 지나간 자리도 다시 한번 확인을 해야합니다.또한, N과 M이 1000이 넘어가므로 크기도 어마어마해집니다.따라서 DP(Dynamic Programming)으로 풀었습니다. DP의 경우 엄청 복잡한 알고리즘이 아닙니다.혹시나 DP를 처음 접하시는 분이라면 잠깐 새 탭을 눌러 검색하여 사전 공부를 하시는 것이 좋습니다! :) 다시 문제로 들어가서! 사탕을 최대로 모아야 하며 준규가 움직이는 방향은 오른쪽, 아래, 대각선(오른쪽 아래) 총 3.. 공감수 1 댓글수 0 2019. 3. 5.
[BOJ 12906] 새로운 하노이 탑 #문제 https://www.acmicpc.net/problem/12906 #풀이은근 시간이 많이 걸렸던 문제입니다. 딱 문제를 보자마자 모든 경우의 수를 해봐야겠다! 라는 생각이 들었습니다.저는 모든 경우의 수를 돌릴 때에는 대부분 DFS로 했기 때문에 해당 문제도 그렇게 접근하려 했습니다.하지만, 원판을 내 마음대로 뽑을 수 있는 것이 아니라 무조건 맨 위에있는 원판 만 움직일 수 있으므로 풀이가 쉽지 않았습니다. 결국... 구글링... :)풀이가 많이 있지도 않았습니다... 아직 많이 풀어보지 않은 문제라 그런가 봅니다...딱 한가지 풀이가 있었는데 BFS를 이용하였습니다.(참고 사이트) BFS로 모든 경우의 수를 돌리는 것이 이해가 더 잘 오기에 BFS로 풀게 되었습니다. 큐에 넣을 때는 현재 탑.. 공감수 0 댓글수 0 2019. 3. 3.
[BOJ 3197] 백조의 호수 #문제 https://www.acmicpc.net/problem/3197 #풀이문제를 보면 크게 두가지를 확인해야 합니다.우선 일마다 얼음이 어디가 녹는지 확인을 해야하고, 그 맵에서 언제 백조들이 만날 수 있는가를 확인하면 됩니다. 처음으로 제가 생각해본 방법은 가장 단순하게 하루하루 물과 근접한 얼음들을 녹게하고, 백조들이 만나는지 확인하는 알고리즘을 세웠습니다.얼음을 녹이는 것과 백조들이 만날 수 있는지 확인하는것 모두 BFS를 사용하여 풀었었습니다. 하지만 이게 왠걸...최대 크기를 완전 고려하지 않았습니다...R과 C가 모두 최대 1500...만약 위와 같은 방법으로 했을 경우, 물인 곳을 넣고 퍼지게 하는 것만 O(R * C) 걸리게 되고, 그 안에서 백조들이 만나는지 확인하는데 또 다시 O(.. 공감수 1 댓글수 2 2019. 2. 25.
[BOJ 2234] 성곽 #문제 https://www.acmicpc.net/problem/2234 #풀이해당 문제는 BFS를 사용하면 손쉽게 풀 수 있습니다. 우선 저는 맵에서 칸마다 벽이 있고 없고의 유무를 주었습니다.10진수로 주어진 값을 2진수로 바꾸어 어디 방향에 벽이 있는지 알아야합니다. 예로 11이 들어왔을때, 11은 1011로 나타낼 수 있고 앞자리부터 순서대로 남, 동, 북, 서에 벽이 있는지 없는지 유무를 나타냅니다.따라서 11은 남, 북, 서에 벽이 있으며 동으로 움직일 수 있다는 뜻이 됩니다. 이때, 방향을 잘 기억해 두는 것이 좋습니다.해당 방향의 순서들이 한번 더 사용할 곳이 있습니다! 이는 좀있다가 알아보도록 하죠! 또한 6(0110)과 같이 4자리가 꽉 채워지지 않는 수들은 앞에 '0'을 붙혀 4자리를.. 공감수 0 댓글수 0 2019. 2. 24.
[BOJ 14442] 벽 부수고 이동하기 2 #문제 https://www.acmicpc.net/problem/14442 #풀이BFS를 사용하여 풀어보았습니다. 처음에는 K개의 벽을 선택하고 해당 벽을 지운 후에 BFS를 돌릴려는 생각을 했으나...입력되는 맵의 크기가 1000 * 1000에다가 벽을 지울 수 있는 최대 개수가 10개...굉장히 시간초과 날만합니다... 그런데도 무식하게 진행했다는... 결국 3차원 배열에 저장하는 식으로 방향을 바꾸게 되었습니다.dist[r][c][cnt] -> r : 행 , c : 열 , cnt : 벽을 부순 개수 -> 위치(r,c)에서 cnt만큼 벽을 부셨을 때, 움직인 거리를 저장해주었습니다.최대 1000 * 1000 * 10 배열을 채우게 되므로 시간 안에 풀 수 있게 됩니다. #코드12345678910111.. 공감수 0 댓글수 0 2019. 2. 24.
[BOJ 5213] 과외맨 #문제 https://www.acmicpc.net/problem/5213 #풀이 읽는데 힘들었고(아이언맨에... 닥터후까지 나오는..대서사기...) 굉장히 시간이 많이 걸렸던 문제였습니다.어디가 틀렸는지 제대로 찾지 못하였다가 결국 반례를 찾게 되었습니다... 구글링을 해보니 저처럼 푸신 분은 거의 없었습니다... 이걸 좋아해야하는지... 머리가 나쁜건지... 모르겠습니다... :( 일단, 타일 자체를 받는데 고민을 많이했습니다.기본 맵과는 다르게 홀수 줄에서는 N열, 짝수 줄에서는 N-1열이기 때문입니다. 저는 홀수줄은 1~2N번째 열을 입력 받았고, 짝수줄은 2~(2N-1)열을 입력 받아 칸마다 값들을 넣었습니다.또한 두 칸마다 하나의 타일이므로 2개씩 묶어 타일 번호를 지정해 주었습니다.(아래 자세.. 공감수 1 댓글수 1 2019. 2. 19.
[BOJ 15653] 구슬 탈출 4 #문제 https://www.acmicpc.net/problem/15653 #풀이해당 문제는 이전에 풀어봤던 두 동전 문제와 비슷하게 풀었습니다. 두 문제 다 두개의 물체를 한번에 움직여야 했고, 판을 움직여 특정 한개의 물체만 뽑아내는 문제입니다.안풀어 보셨다면 두 동전이라는 문제도 풀어보시는 것을 추천드립니다. :)또한, 구슬탈출이란 시리즈가 많기 때문에 다른 구슬탈출도 풀어보도록 합시다! 해당 문제에서 주의 깊게 봐야할 것은 구슬의 움직임입니다.두개의 구슬은 기울여 움직이므로 기울인 방향으로 가지 못할때(벽에 부딪히거나, 탈출구에서 빠졌을때)까지 움직입니다.또한 겹치지 않기 때문에 움직였을때 조심해야합니다. 주어진 입력 예제를 통해 확인해 봅시다!####### #...RB# #.##### #...... 공감수 0 댓글수 0 2019. 2. 18.
[BOJ 16197] 두 동전 #문제 https://www.acmicpc.net/problem/16197 #풀이해당 문제는 BFS로 풀었습니다.보통 저는 문제에서 "어디서부터 어디까지의 최단 거리를 구해라!" 라고 한다면 BFS 방식으로 문제를 풉니다.DFS로 풀어도 괜찮습니다! 다른 블로그에서는 DFS로 풀이를 하셨더라구요. DFS로 풀다 모르시면 구글링하시면 될 것 같습니다. :) 눈 여겨 볼 조건은 "이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다." 와"두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오." 입니다.조건들을 잘 보고 생각하며 코딩을 할 수 있도록 습관을 들입시다! 첫 번째로 두 동전이 어느 칸으로 움직였을때 버튼을 누른 수를 저장해야합니다.두개의 동전이.. 공감수 1 댓글수 1 2019. 2. 15.
[BOJ 3019] 테트리스 #문제 https://www.acmicpc.net/problem/3019 #풀이저의 머리가 역시 안좋구나...하게 만든 문제입니다. 처음 풀이 방법은 맵을 직접 2차원 배열에 넣고, 그 안에서 주어진 블럭을 계속해서 만들어 확인하는 방법이었습니다.이렇게 할 경우, 블럭마다 그리는 방법이 전부 다르기 때문에 일일이 만들어줘야하며, 이차원 배열에 계속 그렸다 확인하고 지우고, 다시 그리고 지우고를 반복하는 상황이 만들어졌습니다..뭔가 아니다 싶어서 검색한 결과 세상 똑똑하신 분들이 많구나하는 생각을 하게 되었습니다.. 일단 방법은 이러합니다. 먼저 쌓으려는 블럭의 밑바닥의 높이를 알아합니다.여기서 밑바닥은 아래 그림과 같은 것을 의미합니다.위 그림과 같이 빨간 선이 있는 부분이 밑바닥입니다.여기서 왜!? 왜.. 공감수 2 댓글수 0 2019. 2. 14.
[BOJ 15661] 링크와 스타트 #문제 https://www.acmicpc.net/problem/15661 #풀이이 문제의 경우, 백트래킹을 이용하여 팀을 나누고 그 중에서 2명을 뽑아내는 식으로 하였습니다. 해당 문제를 어디서 많이 보았다 했는데 예전에 풀었던 것과 거의 비슷했습니다.혹시나 하여 링크를 달아드립니다.[BOJ 스타트와 링크] : https://www.acmicpc.net/problem/14889해당 문제와 거의 비슷하지만 한가지 조건이 추가가 되었습니다.바로 전체 인원이 홀수일 수 있다는것! 해당 조건 때문에 뽑을때 고려해야 할 개수가 늘어났습니다... :(전체 인원이 5명일때, 스타트팀이 2명 링크팀이 3명 또는 스타트팀이 3명 링크팀이 2명일 경우로 나누어지게 됩니다.따라서 홀수일 때는 2명과 3명 모두 뽑아주어야 .. 공감수 0 댓글수 0 2019. 2. 12.
[BOJ 1107] 리모컨 #문제 https://www.acmicpc.net/problem/1107 #풀이문제 해결 방법에 대해 감이 잘 오지 않았던 문제였습니다.별에 별 생각을 다했으나.. 쉽게 풀 수 있는 방법이 있어서 충격을...받았습니다.. 가장 쉽게 접근 할 수 있는 방법은 모든 경우의 수를 해보는 경우입니다.즉, 0부터 할 수 있는 모든 채널을 확인하면서 원하는 채널에 가장 적은 버튼 누름으로 가는 방법을 찾아가면 됩니다.말로만 보면 굉장히 어려울 수 있으나 직접 코드를 보면 이해가기 편하실 겁니다. 채널을 이동할 때 매우 여러가지 경우의 수가 있겠지만, 문제에서 원하는 것은 최소의 버튼 누름이란것을 캐치하셔야합니다!즉, + - + - + + + + 처럼 중간에 다른 버튼이 끼여있다면 의미가 없어지며, + - + 350.. 공감수 0 댓글수 1 2019. 2. 12.
[BOJ 3568] iSharp #문제 https://www.acmicpc.net/problem/3568 #풀이해당 문제는 단순히 나와있는대로 그대로~ 하는것이 중요합니다.저는 너무 생각을 많이해서 저어어 멀리까지 갔다 다시 돌아왔습니다. 변수형에서 나오는 배열,참조,포인터 순서대로 알고 있어야되며, 변수명 뒤에 나오는 추가 변수형또한 앞에 변수형의 순서에 맞게 차곡차곡 알아서 쌓이게 만드는줄 알았습니다.예를 들면 int&[]*[]& aADD*[]&; 식의 문장이 있을때는int&&&[][][]** aADD; 로 바뀌는 줄 알았던 것이죠....:(정말로 이해력에 감탄했습니다..ㅎㅎ.. 다시 문제에대해 말하자면, 먼저 빈칸을 기준으로 나누어야 합니다. 제가 주로 쓰는 방식은 sstream을 이용하여 문자들을 나눕니다. 또한 한 줄에 대하여.. 공감수 0 댓글수 0 2019. 2. 11.
[BOJ 15662] 톱니바퀴(2) #문제 https://www.acmicpc.net/problem/15662 #풀이이 문제는 시뮬레이션으로 하여 풀었습니다. 기존 톱니바퀴 문제에서 조금 더 진화된 문제로 4개가 아닌 T개의 톱니를 다 보아야 합니다.해당 조건으로 인해 기준이 되는 톱니바퀴를 돌릴 경우 양쪽으로 전부 혹은 몇개만 돌아갈 수 있습니다. 돌아갈 수 있는 톱니바퀴를 찾을때 BFS 혹은 DFS로 확인하면서 찾을 수 있다고 생각했지만...기준 톱니의 왼쪽 오른쪽을 나누어 따로 확인하는 방식으로 하였습니다. BFS나 DFS로도 풀어 봐야겠습니다 :) 혹시 BFS 혹은 DFS로 푸신 분들은 코드 공유좀 부탁드리겠습니다! 돌아간 톱니를 찾은 뒤에는 톱니 바퀴를 방향에 맞게 돌려주는 것을 총 K번 반복 하면 끝입니다.톱니바퀴 문제에 비해 .. 공감수 0 댓글수 0 2019. 2. 10.
[BOJ 14499] 주사위 굴리기 # 문제https://www.acmicpc.net/problem/14499 # 풀이 이 문제는 시뮬레이션(문제에서 지시하는대로 코딩) 문제입니다. 위 문제의 핵심은 주사위 굴리기 와 굴릴때의 조건 맞추기 입니다. - 주사위 굴리기 - 주사위는 배열을 만들어 주사위 칸을 만들었고, 문제에서 처음 주어진 주사위의 모양을 이용하였습니다. 2 4 1 3 5 6위와 같이 배열의 1 번째가 무조건 위, 아래는 6 번째로 잡고 시작합니다.동으로 갈때는, [1 -> 3] [3 -> 6] [6 -> 4] [4 -> 1] 로 바뀌게 되어 네개의 칸(1,3,4,6)만 한칸씩 밀리게 됩니다.서는 그 반대며, 남과 북도 비슷하게 4칸(1,2,5,6)만 바꾸면 됩니다. - 굴릴때의 조건 맞추기 - 해당 조건은 굉장히 맞추기 쉽습.. 공감수 0 댓글수 0 2019. 2. 8.
[BOJ 16234] 인구 이동 # 문제 https://www.acmicpc.net/problem/16234 # 풀이 dfs를 사용하여 문제를 풀었습니다.(bfs로 하셔도 괜찮습니다.) 총 3개의 2차원 배열을 사용했습니다. 일단, 첫 번째는 초기 국가들의 인구수를 2차원 배열입니다.이 배열을 기반으로 국가간 연합이 가능한지 여부를 매번 따질 수 있게끔 하는 배열입니다. 두 번째는 dfs를 통하여 연합된 국가들을 표시하는 역할을 하는 배열입니다.나중에 인구수를 재배치 할때, 해당 배열을 보며 인구 수를 분배합니다. 세 번째는 dfs를 할때 가장 중요한 visit 배열입니다. 탐색을 배우신 분들이라면 이것이 얼마나 중요한지 아실겁니다. :) 이 문제는 단지번호붙이기 라는 문제에서 약간 심화된 문제라고 생각되어 링크를 걸어 놓았습니다.혹시.. 공감수 0 댓글수 0 2018. 10. 25.
[BOJ 16235] 나무 재테크 # 문제 https://www.acmicpc.net/problem/16235 # 풀이 일단, 굉장히 구현스러운 문제... 그냥 문제 따라서 가면서 코드를 짜면 된다. 여기서 조심할점은..... 나무의 위치를 주어질때! x,y 가아닌 y,x 순으로 주어진다는 것이다.....이점을 명시하자.... 1년차에는 기본적으로 양분이 모두 5로 되어있기 때문에 1년차와 아닐때를 나누어 알고리즘을 짯다.1년차에는 기본적으로 주어진 양분을 사용, 2~K년차까지는 여태 남아있는 양분을 사용!이런식으로 기본적 양분을 넣어줄 2차원 배열, 매년마다 추가로 들어가는 양분을 저장해줄 2차원 배열, 최종으로 남게 되는 양분 2차원 배열 3개를 만들어 사용하였다. 우선 순위 큐를 사용해도 되지만, 벡터를 사용하였다.큐 사용할때 넣고.. 공감수 0 댓글수 0 2018. 10. 24.
[BOJ 16236] 아기 상어 # 문제 https://www.acmicpc.net/problem/16236 # 풀이 문제에 조건들이 은근히 많습니다. 현재 자신의 크기도 판단해야되고, 자기보다 크기가 작은 친구들의 위치를 구할때, 자신과 크기가 같은 친구들은 통과 되지만, 자신 보다 큰 친구들을 못지나가고....또, 자신보다 작은 친구들을 탐색할때, 같은 거리에 있는 친구들이 있다면 맨 위, 왼쪽이 우선순위여야하고....이렇게나 지켜야할 조건들이 은근 있어 까다로운 문제입니다. 저는 아기 상어의 위치와 정보를 구조체로 만들어 전역변수로 선언하여 계속해서 사용했습니다.또, 물고기들의 위치와 사이즈도 구조체로 만들어 위부터 그것도 왼쪽에서 맵 입력을 받을 때마다 넣어 주었습니다.(위로 인하여 위에 조건중 거리가 같은 물고기가 있을때 맨 .. 공감수 0 댓글수 0 2018. 10. 23.
[백준 15683] 감시 # 문제https://www.acmicpc.net/problem/15683 # 풀이완전탐색을 통해 풀었습니다. 일단, CCTV의 종류와 위치를 따로하여서 vector에 저장했습니다.그 후에 모든 CCTV를 돌면서 CCTV가 감시할 수 있는 모든방향을 검사하여 사각지대를 찾습니다. CCTV의 종류마다 감시하는 구역이 중복되는 것을 눈치 채셨나요?저는 1번, 3번,4번 카메라는 4방향 모두 돌려서 확인을 해주어야 되지만, 2번은 두번만 5번은 회전을 하지 않게끔 처리하였습니다. dfs() 에서는 인자로 cnt를 가지고 있습니다. 이 인자는 현재 몇번째 CCTV까지 검사하였는지 나타냅니다. 그렇다면 재귀 함수의 종료 조건은 쉽게 찾아 낼 수 있겠죠? 저는 cnt > (int)cctv.size()-1 일때! 종.. 공감수 3 댓글수 2 2018. 7. 3.
[백준 15686] 치킨 배달 문제 https://www.acmicpc.net/problem/15686 풀이해당 문제는 완전 탐색을 통해 풀었습니다. 문제 해결 방법은 우선 집과 치킨집의 좌표를 vector를 사용하여 받았습니다. 그 뒤에 재귀를 통해 전체 치킨집 중에서 M개를 고르고, 고른 좌표들은 따로 저장을 하였습니다.(거리를 잴때 골라진 치킨집만 계산을 하기 위해!) M개가 다 선택되면 한번에 거리를 계산하고 최소 거리를 구합니다. 핵심적인 부분은 47~51 라인입니다. ＃ select 함수에서 인자로 k를 넘긴 이유는 중복 선택을 없애고, 순서가 상관 없기 때문입니다. 예를 들어 치킨집이 5개가 있다고 하고 이중 3개를 골라야된다고 해봅시다.1,1,1 치킨집은 치킨집이 3개가 아니라 1개이므로 중복을 없애 주었습니다.따라서 .. 공감수 0 댓글수 0 2018. 7. 3.
백준 14503: 로봇 청소기 문제 문제 링크: https://www.acmicpc.net/problem/14503 처음에는 재귀를 이용해서 풀려고 했었지만, 실력부족으로 인하여 while문을 사용해서 움직였습니다.처음에 주어진 입력으로 로봇 움직임을 보려고 개 뻘짓도 해보고... 엑셀에 그려가면서 하나하나 체크 했던것 같습니다.DFS문제들만 풀면 무한 루프에 빠지는게 대다수였던것 같고 이 문제 또한 그랬습니다... ㅠㅠ 엑셀에 그려가면서 했던것입니다.. 다 못할꺼 같아서 무한 루프가 생겼던 점까지 해보았습니다. 문제가 2-3 조건에서 뒤로 갔을때, 이미 체크 되어있는 것을 생각을 못하는 정말 바보같은 실수를 했습니다.가로 안은 로봇이 움직이는 순서입니다. 방향은 해당 위치에서 턴 할때마다 적어 놓았습니다. 움직일 방향 배열의 순서도.. 공감수 0 댓글수 0 2018. 1. 19.
백준 14500: 테트로미노 문제 문제 링크: https://www.acmicpc.net/problem/14500 DFS로 문제를 푸는 것은 인지를 하였으나, 직접적으로 코딩을 하지는 못하였습니다.오늘도 많은 부족함을 느끼는 날입니다. 열심히 하다보면 자연히 늘겠죠...? 문제에 대해 검색해보니 많은 분들이 DFS를 사용하여 풀었습니다. 혹시 문제를 보고 바로 오...하나가 이상하네? 라고 찾으신 분은 DFS에 대해서 정확히 이해 하셨을꺼라 생각됩니다.저는 검색을 하고나서야 알게 되었네요...ㅎㅎㅎ;; ㅗ 모양은 DFS로 탐색이 불가능합니다. 따라서 ㅗ 모양만 다른 방법으로 찾아야합니다.살짝 문제를 꼬아낸것 같습니다. 도형을 탐색 하면서 해당 칸의 수를 더해가면서 최댓값을 구하면 되는 문제였습니다.찾아보면 또..은근 쉬워 보입니다... 공감수 0 댓글수 0 2018. 1. 19.
백준 14501: 퇴사 문제문제 링크: https://www.acmicpc.net/problem/14501 문제를 보면 DP로 풀 수 있다는 것을 알 수 있습니다.검색을 해본 결과 DFS로도 풀 수 있다는 것을 알게되었습니다.문제를 풀때 꼭 한 방법만이 아닌 다른 방법도 생각하는 습관을 들이는 것이 좋을것 같습니다.ㅎㅎ;; 이 문제는 상담을 하거나 안하거나 둘중 하나를 고르는 것이 관건인 문제입니다. DP의 경우는 점화식을 세워서 문제를 풀며, 점화식은 max(dp(day+1), dp(day+T[day])+P[day]) 입니다.전자 의 경우는 상담을 안 하였을때의 식이며, 후자의 경우는 상담을 하였을 때의 식입니다.T[day]는 해당 날짜의 상담을 했을 경우 걸리는 시간이며, P[day]는 그에 따른 보수입니다. DFS 경우에.. 공감수 3 댓글수 2 2018. 1. 19.
백준 14502: 연구소 문제문제 링크: https://www.acmicpc.net/problem/14502문제를 보자마자 "아! 이거는 DFS나 BFS로 풀면 되겠다!" 라고 생각이 들어서 무작정 풀었다가 큰코를 다쳤습니다....해당 문제를 푸는 과정은 다음과 같습니다.연구소 상황을 입력 받는다.받은 연구소 상황을 다른 배열에 복사한다.복사한 연구소에서 안전구역인 곳에 3개의 벽을 세운다.벽을 세운 상태에서 바이러스를 퍼트린다.다 퍼트린 후, 안전 구역의 수를 센다.구역의 수를 기존의 저장값과 비교하여 최대인지 확인한다.모든 벽을 세울 수 있는 경우를 계산 할 때까지 3번과정부터 반복한다.해결 방식을 세우는것은 간단 하였으나... 3번 과정에서 많은 시간을 투자하게 되었습니다... 3개의 벽을 세울때, 입력 받는 연구소의 크기.. 공감수 6 댓글수 6 2018. 1. 18.
백준 2667: 단지번호 붙이기, 4963: 섬의 개수 문제문제 링크: https://www.acmicpc.net/problem/2667 문제 링크: https://www.acmicpc.net/problem/4963위 두 문제는 해결하는데 있어 많이 유사하기 때문에 같이 포스팅을 하게되었습니다. 두 문제 전부 DFS 혹은 BFS를 사용하여 해결 할 수 있습니다. 저의 경우는 DFS 방법으로 문제를 해결하였습니다. 문제 푸는데 있어 핵심은 움직임에 있습니다. 2667번의 경우, 상·하·좌·우로만 움직일 수 있습니다. 따라서 움직일 수 있는 방향을 먼저 지정을 해주어야 합니다.4963번의 경우에는 상·하·좌·우 뿐만아니라 대각선까지 움직일 수 있습니다. 8개의 방향 모두 지정해주어야 합니다. 또, 중요한 것은 주어진 지도를 벗어나면 안된다는 것입니다. 범위를 주.. 공감수 0 댓글수 0 2018. 1. 13.
백준 1707: 이분 그래프 문제문제 링크: https://www.acmicpc.net/problem/1707이분 그래프란?☞모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을포함하도록 색칠 할수 있는 그래프.출처: https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 ▼ 이분 그래프의 예시해당 문제는 주어지는 그래프가 이분 그래프인지를 확인하는 문제입니다. 예시를 보면 "하나의 정점에서 연결된 다른 정점들의 색상은 다르다" 인 것을 확인 할 수 있습니다. 이분 그래프의 특징을 이용하여 문제를 푸는 것이 핵심입니다. DFS 혹은 BFS로 그래프를 탐색을 하여 이미 방문했던 정점을 확인할 때, 만약 자신과 같은 색상을 가지고 있다.. 공감수 0 댓글수 0 2018. 1. 10.
백준 11052: 붕어빵 판매하기 문제문제 링크: https://www.acmicpc.net/problem/11052 해당 문제의 경우는 다이나믹 프로그래밍으로 생각하는 것이 가장 중요합니다.저 또한 문제를 보았을때, 아직까지는 정확히 어떤것을 먼저 해야되고 어떠한 식으로 접근을 해야되는지 감이 오질 않아 많이 힘든 부분도 있습니다. 하지만 언젠가는 익숙 하겠지요? D[i]를 붕어빵 i개를 팔아 얻을 수 있는 최대 수익, P[i]는 붕어빵 i개로 이루어진 세트메뉴의 가격이라고 합시다. 총 i개의 붕어빵 중에서 1개를 P[1]에 판다면 남은 붕어빵의 개수는 i-1개이며 얻을 수 있는 최대 이익은 D[i-1] 입니다.→ 총 수익 : P[1] + D[i-1] 총 i개의 붕어빵 중에서 2개를 P[2]에 판다면, 남은 붕어빵의 개수는 i-2개이며.. 공감수 0 댓글수 0 2018. 1. 6.
백준 1463: 1로 만들기 문제문제 링크: https://www.acmicpc.net/problem/1463 이 문제의 경우, 입력값에 대해 2로 나누어지는 값이라면 2로 나누고, 3으로 나누어 지는 값이라면 3으로 나눕니다. 두가지에도 포함이 되지 않는다면, 1을 빼어 1이 될 때 까지 연산을 합니다. 이때, 연산을 최소한으로 하는 방법을 구하는 문제로, 다이나믹 프로그래밍을 사용하면 간단히 풀 수 있습니다. 저의 경우는 Top-Down 방식으로만 풀어 올렸지만, Bottom-Up 방식으로도 해보는 것을 추천합니다. 다이나믹 프로그래밍에서는 점화식을 찾아내는것이 가장 중요합니다.해당 문제의 점화식의 경우는 3가지로 나눌 수 있으며, 선택지가 많을 경우 저장된 값을 확인 후에 저장 된 값보다 새로운 값이 작다면이를 저장하는 방식으.. 공감수 0 댓글수 0 2018. 1. 5.
백준 10799: 쇠막대기 문제 이 문제는 스택을 이용하여 푸는 문제이다. 문제의 핵심은 ')'를 만났을 때 레이저인지 막대기의 끝인지 구별해 내는 것이다. 먼저 '('를 만났을 때는 스택에 push를 해준다. ')' 를 만났을 때는 스택에서 pop을 해준다. ')'은 막대기의 끝을 나타낼 수도 있고, 레이저를 나타낼 수도 있다.이 2가지의 경우를 나누는 방법은 레이저는 바로 직전의 문자가 '('이라는 것이다. 따라서 이전의 문자를 보면서 이 둘을 구별할 수 있다. 잘려진 막대기의 개수를 구하는 방법은 레이저를 만났을 때는 스택에 쌓여있는 '('의 개수만큼 더해주고, 막대기의 끝을 만났을때는 1만큼만 더해준다.레이저를 만났을 때 막대기가 몇개가 있는가에 따라서 잘려나간 막대기의 수가 정해지며, 막대기의 끝을 만났을 때에는 해당 막.. 공감수 2 댓글수 0 2017. 8. 15.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.