[BOJ] 백준 1922 네트워크 연결 자바 (Java)
2024. 8. 20. 23:36
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/1922문제를 풀며 고민했던 점가중치가 있으니 다익스트라 알고리즘을 쓰면 되지 않을까?그래프 내에 사이클 판별은 유니온 파인드 알고리즘을 써야할 것 같다최소 스패닝 트리 문제인데 다익스트라 알고리즘과 유니온 파인드를 함께 쓰는게 맞을까?밟았던 단계다익스트라 구현 중 사이클 판별에 대한 의문이 생김유니온 파인드를 사용해야 한다는 점 발견최소 스패닝 트리에 대한 생각완전 탐색으로는 문제를 해결할 수 없다는 생각그리디한 알고리즘을 모색함크루스칼 알고리즘을 떠올림크루스칼로 구현package b1922;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStrea..
[BOJ] 백준 9205 맥주 마시면서 걸어가기 자바 (Java)
2024. 8. 19. 23:53
알고리즘/백준[BaekJoon]
링크 : https://www.acmicpc.net/problem/9205문제를 풀면서 고민했던 점1미터씩 움직이는 그래프를 구현해서 풀어야할까?편의점과 목적지의 정보로만 그래프를 구성해서 풀어야할까?밟았던 단계편의점과 목적지의 정보로만 그래프를 구성하면 ㅍisit 배열을 확인하는게 중복을 체크해버리면 문제가 생기지 않을까?1미터씩 움직이는 그래프를 구현해서 풀어야겠다문제점 : 가로, 세로 약 6만개 > 메모리 초과 발생편의점과 목적지의 정보로만 그래프를 구성해야한다.집에서부터 목적지까지 가까운 곳을 밟아가므로 visit배열 중복, 돌아가는 경우를 생각하지 않아도 된다구현하여 PASSimport java.io.BufferedReader;import java.io.BufferedWriter;import j..
[디자인 패턴] 디자인 패턴이란?
2024. 8. 19. 22:58
기술면접/디자인패턴
디자인 패턴이란?"바퀴를 다시 발명하지 마라(Don't reinvent the wheel)"소프트웨어를 설계할 때 특정 맥락에서 자주 발생하는 고질적인 문제들이 또 발생했을 때 재사용할 수 있는 훌륭한 해결책이미 만들어져서 잘 되는 것은 처음부터 다시 만들 필요가 없다는 의미프로그램을 설계할 때 발생했던 문제점들을 객체 간의 상호 관계 등을 이용하여 해결할 수 있도록 하나의 규약 형태로 만들어 놓은 것GoF 디자인 패턴의 분류"Gang of Fout"라 불리는 사람들이 23가지의 디자인 패턴을 정리하고 각각의 디자인 패턴을 분류생성(Creational), 구조(Structural), 행위(Behavioral) 3가지로 분류생성(Creational) 패턴 - 객체의 생성에 관련된 패턴- 특정 객체가 생..
[BOJ] 백준 11437 LCA 파이썬(Python)
2022. 8. 26. 15:02
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/11437 11437번: LCA첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정www.acmicpc.net트리 문제를 풀다가 트리 DP문제를 접하고 문제를 해결하지 못하고 '다른 트리 DP 문제가 무엇이 있을까?'라는 생각에 찾게 된 문제.초기 구상 과정LCA(Lowest Common Ancestor): 최소 공통 조상트리 내부에서 두 개의 노드 사이의 최소로 갈 수 있는 공통 조상을 찾는 문제이다. 간단하게 초반에는 노드의 깊이들을 계산하여 가지고 있고 그 깊이를 기반으로 한땀한땀 올라가면..
[BOJ] 백준 1003 피보나치함수 파이썬(Python)
2022. 8. 23. 15:57
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.www.acmicpc.net코드import sysinput = sys.stdin.readlinefor tc in range(int(input())): num = int(input()) dp = [(1, 0)] + [0] * num if num >= 1: # 바로 1을 호출하는 경우는 따로 조건분기 필수! dp[1] = (0, 1) for i in range(2, num + 1): dp[i] = (dp[i-1][0] + dp[i-2][0], dp[i-1][1]..
[BOJ] 백준 1463 1로 만들기 파이썬(Python)
2022. 8. 23. 15:53
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/1463 1463번: 1로 만들기첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.www.acmicpc.net코드import sysinput = sys.stdin.readlinenum = int(input())dp = [-1] * (num + 1)dp[1] = 0for i in range(1, num + 1): if dp[i] != -1: # if i + 1 == num or i * 2 == num or i * 3 == num: break if i + 1 느낀점DP도 시간이 많이 걸리는 경우도 있구나, 이때 Memoization이 성능이 좋은데 한번 구현해봐야겠다.[220823] 지금..
[BOJ] 백준 11726 2xN타일링 파이썬 (Python)
2022. 8. 23. 15:49
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.www.acmicpc.net코드import sysinput = sys.stdin.readlinenum = int(input())dp = [0] * 1001dp[1] = 1dp[2] = 2for i in range(3, num + 1): dp[i] = dp[i - 1] + dp[i - 2] # 하나 추가하는 경우는 세로로 붙이는 경우 Only 1 # 두개 추가하는 경우는 가로 세로 두 경우지만 그 경우는 하나 추가하는 경우와 ..
[BOJ] 백준 9095 123더하기 파이썬 (Python)
2022. 8. 23. 15:44
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.www.acmicpc.net코드import sysinput = sys.stdin.readlinefor tc in range(int(input())): num = int(input()) dp = [0, 1, 2, 4] + [0] * (num - 3) for i in range(4, num + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] # i번째에서 i - 1에서 1을 더하면 완성 / i - 2에서 2을 더하면 완성 / i - 3에서 1을 더..