본문 바로가기

백준56

[백준 1916] 최소비용 구하기 (C++) https://www.acmicpc.net/problem/1916다익스트라도시를 연결하는 단방향 버스 (출발점, 도착점, 비용)이 주어지고임의의 출발점과 도착점이 주어졌을 때, 이 둘을 잇는 최소 비용을 출력하는 문제 접근방법 음수인 비용이 없어서 다익스트라로 풀어도 된다. (벨만포드로 안풀어도 됨)이거 풀다가 내가 다익스트라를 제대로 이해하고 있는게 맞나 의심했음..다시 공부해야 할 것 같다..다익스트라 기본 개념은 임의의 출발점 하나에 대해 모든 노드에 대한 최소 거리를 저장하고 있는 1차원 배열이 하나 있고,방문한 노드를 하나씩 추가해 가면서 이 배열을 갱신하는 방식이다. 이 문제를 풀 때는,- 인접행렬 (각 노드에 대해 연결된 버스 노선을 담고 있는 2차원 배열. ex. 1번: {(2번도시, 비용.. 2024. 10. 23.
[백준 1062] 가르침 (C++) https://www.acmicpc.net/problem/1062  Back tracking (백트래킹) k개의 글자를 가르칠 수 있을 때, 주어진 N개의 문자열 중 최대 몇개를 읽을 수 있게 할 수 있는지 출력하는 문제단, N개의 문자열은 모두 anta로 시작하고 tica로 끝난다. = 최소 acnti 는 가르칠 수 있어야 단어를 한개라도 가르칠 수 있음 접근 방법처음에는 N개의 문자열을 dfs로 순회하면서 읽을 수 있는 문자열 그룹의 경우를 모두 확인하려고 했는데,26개의 알파벳 중 가르칠 문자 그룹의 모든 경우에 대해서 각각 그룹이 읽을 수 있는 문자열의 갯수를 구하면서최댓값을 찾는 것이 시간초과가 나지 않는 풀이법이었다. N이 50개까지 밖에 안가지만 그래도 시간복잡도가 26에 비해서는 커질 수 .. 2024. 10. 17.
[백준 18406] 럭키 스트레이트 (C++, Swift) https://www.acmicpc.net/problem/18406 구현, 문자열머선 문제냐 하면123402 라는 문자열이 주어지면, 반갈죽!해서 양쪽 자릿수 합이 같은지 확인하는 문제임같으면 LUCKY 출력, 다르면 READY 출력*문자열은 늘 짝수자릿수 (즉 12345 같은 5자릿수 안들어옴) 1234021+2+3 = 6, 4+0+2 = 6 이니 이건 LUCKY 접근방법C++for 문을 두개 써서 front, back 변수에 각각 앞부분의 합과 뒷부분의 합을 저장하고 둘을 비교함swift배열하나 두고, prefix, suffix로 배열 쪼개서 reduce로 합 구해서 바로 비교하고 출력 (고차함수 쓰고 싶어서 swift로도 풀었는데, string -> int 배열 만들려다가 고군분투함..) 오답노트-.. 2024. 6. 20.
[백준 3190] 뱀 (C++) https://www.acmicpc.net/problem/3190 구현그 snake 게임? 생각하면 될 듯N * N 보드에서 길이 1짜리 뱀으로 시작해서 한칸씩 늘리면서 이동하면서도처에 위치한 사과들을 먹으면 길이가 +1 되고, 못 먹으면 길이가 유지되는 (그래서 꼬리가 이동함 - 사라짐)입력으로는 사과의 위치와 S초후에 바뀌는 방향이 주어진다.-> 머리의 방향을 바꿔가면서 한칸씩 이동하는 스네이크 게임~종료 조건: 벽에 닿거나, 본인과 본인의 머리가 부딪힐 경우 접근방법구현문제여서 시뮬레이션으로 풀었다.- 정사각보드 구성: 2차원배열로 격자판을 만들어 놓고, 빈칸은 0, 뱀은 1, 사과는 2로 설정했다.- 뱀의 이동 방향: 오른쪽, 아래, 왼쪽, 위 순서대로 방향 배열 선언해둠 (dr, dc), 왼쪽으.. 2024. 6. 20.
[백준 1620] 나는야 포켓몬 마스터 이다솜! (Swift) https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 제목부터 킹받는 문제다 지하철에서 문제를 열심히 읽었는데 본문 전체가 문제 푸는데에는 영향을 주지 않는 빌드업이었다 ^_^ 문제를 읽기 전에 이 블로그를 먼저 보는 사람은 없겠지만 혹시 운 좋은 어떤 사람이 문제도 보기 전에 이 블로그를 먼저 봤다면 문제 설명 부분에서 오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가.. 2022. 6. 12.
[백준 14500] #129 : 테트로미노 (C++) https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net C++ 구현, 브루트포스 사진에 보이는 5개의 테트로미노를 회전, 대칭 시켜서 점수가 적혀있는 판에 놓았을 때 테트로미노가 놓여진 칸들의 점수의 합의 최대값을 구하는 문제이다. 접근방법 브루트포스로 풀었다. 나올 수 있는 모든 도형의 모양을 구하고 (0,0) 기준으로 좌표를 구한다음 모든 도형에 대해 일일이 어디에 두면 가장 큰 값이 나오고, 그 중에 어떤 도형이 가장 큰 값을 내는지 찾았다. 도.. 2021. 10. 11.
[백준 9660] 알고리즘 128일차 : 돌게임 6 https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net C++ 게임이론 돌게임 3에서 N의 범위만 (1 ≤ N ≤ 1,000,000,000,000) 이렇게 커진 문제 돌게임3를 DP로 풀고 돌게임6를 규칙을 찾아푸는걸 의도한것 같지만 돌게임3를 이미 규칙을 찾아 풀어서 이것도 똑같이 풀었다. 1 -> SK 2 -> CY 3 -> SK 4 -> SK 5 -> SK 6 -> SK 7 -> CY 이 반복됨 소스코드 #include using namespace std; int main(){ //input long long N; cin >> N; //process & out.. 2021. 8. 31.
[백준 2467] 알고리즘 NCT???일차 : 용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net C++ 투포인터 산성도가 오름차순으로 정렬된 배열에서 두 용액의 산성도를 합했을때 가장 0에 가까운 두 용액을 찾는 문제 2470번 문제와 아주 유사하지만 정렬된 배열이라는 점이 다르다. 접근방법 양 끝 점에서 시작하여 두 수의 합이 0보다 크면 현재 값보다 더 작아져야 하므로 end 점을 1감소시키고 두 수의 합이 0보다 작으면 현재 값보다 더 커져야 하므로 start점을 1증가시킨다. 소.. 2021. 8. 30.
[백준 1068] 알고리즘 126일차 : 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net C++ 트리 트리에서 어느 한 노드를 루트노드로하는 서브트리를 모두 삭제할때 리프노드 개수를 구하는 문제 접근방법 벡터로 인접리스트를 구현하고, 부모노드 정보를 담고 있는 1차원 배열을 생성한다. 인접리스트를 탐색하면서 기존 트리에서의 리프노드 개수를 카운팅한다. 지울 노드를 큐에 넣고 그 하위의 노드들도 큐에 넣어 삭제해주면서 지우는 노드가 리프노드인 경우 기존 리프노드 개수 - 1 한다... 2021. 8. 26.

티스토리툴바